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 imposeprivacyon learning tasks.

**Efficient, Noise-Tolerant, and Private Learning via Boosting.**Mark Bun, Marco L. Carmosino, and Jessica Sorrell.*To Appear*, COLT2020. arXiv:2002.01100.**Adaptive Rubrics.**Marco L. Carmosino and Mia Minnes. SIGCSE 2020, with Video Talk.**Fine-Grained Derandomization: From Problem-Centric Complexity to Resource-Centric Complexity.**Marco L. Carmosino, Russell Impagliazzo and Manuel Sabin. ICALP 2018, ECCC TR18-092.**Hardness Amplification for Non-Commutative Arithmetic Circuits.**Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett and Ivan Mihajlin. CCC 2018, ECCC TR18-095.**Agnostic Learning from Tolerant Natural Proofs.**Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova. APPROX-RANDOM 2017.**Learning Algorithms from Natural Proofs.**Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova.at CCC 2016, ECCC 2016.*Best Paper Award***Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility:**Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider. ECCC 2015, ITCS 2016.**Tighter Connections between Derandomization and Circuit Lower Bounds:**Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova. APPROX-RANDOM 2015.**A study of machine learning regression methods for major elemental analysis of rocks using laser-induced breakdown spectroscopy.**Thomas F. Boucher, Marie V. Ozanne, Marco L. Carmosino, M. Darby Dyar, Sridhar Mahadevan, Elly A. Breves, Kate H. Lepore and Samuel M. Clegg. Spectrochimica Acta Part B: Atomic Spectroscopy, vol 107, 2015.**Remote laser-induced breakdown spectroscopy analysis of East African Rift sedimentary samples under Mars conditions.**M. Dyar, M.L. Carmosino, J.M. Tucker, E.A. Brown, S.M. Clegg, R.C. Wiens, J.E. Barefield, J.S. Delaney, G.M. Ashley and S.G. Driese. Chemical Geology, vol 294-295, 2012.**Comparison of partial least squares and lasso regression techniques as applied to laser-induced breakdown spectroscopy of geological samples.**M. Dyar, M.L. Carmosino, E.A. Breves, M.V. Ozanne, S.M. Clegg and R.C. Wiens. Spectrochimica Acta Part B: Atomic Spectroscopy, vol 70, 2012.**Experimental Descriptive Complexity:**Marco Carmosino, Neil Immerman, Charles Jordan. Logic and Program Semantics 2012.