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.
Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap, Marco L. Carmosino and Stefan Grosser: Preprint.
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. Best Paper Award at CCC 2016, ECCC 2016.
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.