On the Sample Complexity of Robust PCA. - Matthew Coudron; Gilad Lerman (NIPS, 2012)

Robust Randomness Amplifiers: Upper and Lower Bounds. - Matthew Coudron; Thomas Vidick; Henry Yuen (APPROX-RANDOM, 2013)

Infinite randomness expansion with a constant number of devices. - Matthew Coudron; Henry Yuen (STOC, 2014)

Interactive Proofs with Approximately Commuting Provers. - Matthew Coudron; Thomas Vidick (ICALP (1), 2015)

Entangled protocols and non-local games for testing quantum systems. - Matthew Coudron (2017)

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. - Matthew Coudron; Aram W. Harrow (CCC, 2019)

Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. - Matthew Coudron; William Slofstra (CCC, 2019)

Computations with greater quantum depth are strictly more powerful (relative to an oracle). - Matthew Coudron; Sanketh Menda (STOC, 2020)

Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits. - Nolan J. Coble; Matthew Coudron (CoRR, 2020)

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits. - Nolan J. Coble; Matthew Coudron (FOCS, 2021)

Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension. - Suchetan Dontha; Shi Jie Samuel Tan; Stephen Smith; Sangheon Choi; Matthew Coudron (TQC, 2022)

Quantum Algorithms and the Power of Forgetting. - Andrew M. Childs; Matthew Coudron; Amin Shiraz Gilani (ITCS, 2023)

Quantum Depth in the Random Oracle Model. - Atul Singh Arora; Andrea Coladangelo; Matthew Coudron; Alexandru Gheorghiu; Uttam Singh; Hendrik Waldner (STOC, 2023)

Local Hamiltonians with No Low-Energy Stabilizer States. - Nolan J. Coble; Matthew Coudron; Jon Nelson; Seyed Sajjad Nezhadi (TQC, 2023)

Hamiltonians whose low-energy states require Ω(n) T gates. - Nolan J. Coble; Matthew Coudron; Jon Nelson; Seyed Sajjad Nezhadi (CoRR, 2023)

Provably Overwhelming Transformer Models with Designed Inputs. - Lev Stambler; Seyed Sajjad Nezhadi; Matthew Coudron (CoRR, 2025)