Lucas Gretta

PhD Student, UC Berkeley EECS

Headshot of Lucas Gretta

About

I am a PhD student in the EECS Department at UC Berkeley, where I am fortunate to be advised by Alistair Sinclair. Before coming to UC Berkeley, I completed my undergraduate degree at UT Austin. I am grateful for the advice and mentorship of Eric Price.

My research broadly studies the power and limitations of efficient computation, especially in randomized algorithms, quantum computation, and modern machine learning systems.

I am interested in Markov chains and mixing times, with a focus on understanding how structural properties of stochastic processes lead to efficient sampling algorithms. I also study low-depth quantum circuits and near-term quantum computation, including the computational power of shallow quantum circuit models. More recently, I have been interested in efficiency questions for large language models and related systems.

Publications & Preprints

Shor's Algorithm Requires Fanout
Lucas Gretta, Malvika Raj Joshi
arXiv preprint, 2026.
Super-Constant Weight Dicke States in Constant Depth Without Fanout
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
arXiv preprint, 2026.
Parity ∉ QAC0 iff QAC0 is Fourier-Concentrated
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
FOCS 2026.
JASPER: Joint Autoscaling and Shard Placement via Efficient Reinforcement learning
Lucas Gretta, Yonatan Naamad, Nina Mishra, Huibin Shen, Paul White
More Efficient Approximate k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Lucas Gretta, William He, Angelos Pelecanos
SODA 2025.
Sharp Noisy Binary Search with Monotonic Probabilities
Lucas Gretta, Eric Price
ICALP 2024.
An Improved Online Reduction from PAC Learning to Mistake-Bounded Learning
Lucas Gretta, Eric Price
SOSA 2023.

Contact

Email: firstname _ lastname at berkeley dot edu