Marco Leandro Carmosino

I am a Research Scientist at IBM Yorktown. I obtained my PhD from the University of California, San Diego in August of 2019, advised by Russell Impagliazzo. This page is a brief summary of my research agenda and a list of my papers.


Computational limitations are simultaneously frustrating and useful; we are dismayed by the apparent difficulty of learning, but we need hard problems for secure cryptography. I study computational complexity theory to understand and exploit the inherent structure of efficient algorithms and devices. I seek formal answers to three fundamental questions, presented below with partial answers from my work:

(Q1) How are efficient algorithms and complexity limits related?

A: Natural complexity lower bounds imply learning algorithms. (Best Paper, CCC 2016)

(Q2) Which natural phenomena can be efficiently and convincingly simulated by computation?

A: Simple algorithmic hardness assumptions imply that random coin tosses can be simulated.

(Q3) What rich properties (e.g., privacy, fairness, transparency) can algorithm designers enforce?

A: Boosting algorithms rooted in complexity theory can impose privacy on learning tasks.