Research
Here is some of my work (click for abstract):
On the Advantage of Adaptivity for Sampling with Cell Probes - with Farzan Byramji, Daniel Kane, and Anthony Ostuni
We construct an explicit distribution $\mathbf{D}$ over $\{0,1\}^N$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distribution can be sampled exactly when each output bit is allowed two adaptive probes to an arbitrarily long sequence of independent uniform symbols from $[N]$. In contrast, any non-adaptive sampler requires $\tilde{\Omega}(N)$ non-adaptive cell probes to generate a distribution with total variation distance less than $1-o(1)$ from $\mathbf{D}$. This provides a $2$-vs-$\tilde{\Omega}(N)$ separation for sampling with adaptive versus non-adaptive cell probes, improving upon the $2$-vs-$\tilde{\Omega}(\log N)$ separation of Yu and Zhan (ITCS '24) and the $(\log N)^{O(1)}$-vs-$N^{\Omega(1)}$ separation of Alekseev, G\"o\"os, Myasnikov, Riazanov, and Sokolov (STOC '26).Hard-to-Sample Distributions from Robust Extractors - with Farzan Byramji, Daniel Kane, and Anthony Ostuni
We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of \emph{robust extractors}, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance $1 - o(1)$ from our target distribution, qualitatively recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error. As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance $1 - o(1)$ from the output of any low-degree $\mathbb{F}_2$-polynomial source. We also describe a potential avenue toward proving a similar hardness result for $\mathsf{AC^0}[\oplus]$ circuits.$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) - with Daniel Grier and Kewen Wu
$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing \emph{any} non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for \emph{decision} problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals - with Daniel Grier, Daniel Kane, Anthony Ostuni, and Kewen Wu, QIP 2026, ITCS 2026
We construct a family of distributions $\{\mathcal{D}_n\}_n$ with $\mathcal{D}_n$ over $\{0, 1\}^n$ and a family of depth-$7$ quantum circuits $\{C_n\}_n$ such that $\mathcal{D}_n$ is produced exactly by $C_n$ with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance $1 - e^{-\Omega(n)}$ from $\mathcal{D}_n$. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and K\"onig (Science, 2018) to separate shallow quantum and classical circuits for relational problems.Quantum Threshold is Powerful - with Daniel Grier, CCC 2025 - Best Paper Award, TQC 2025
In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful--there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.Simple vertex coloring algorithms - with Fang Song, QIP 2021
Given a graph G with n vertices and maximum degree $∆$, it is known that $G$ admits a vertex coloring with $∆ + 1$ colors such that no edge of $G$ is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time $O(n∆)$. Very recently, a sequence of results (e.g., [Assadi et. al. SODA’19, Bera et. al. ICALP’20, AlonAssadi Approx/Random’20]) show randomized algorithms for $(1 + ε)∆$-coloring in the query model making $\tilde{O}(n√n)$ queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of $Ω(n√n)$ for any $O(∆)$-coloring is established on general graphs. In this work, we give a simple algorithm for $C$-coloring where $C > ∆ + 1$. This algorithm makes $O(\frac{n}{C−∆})$ queries. This matches the classical lower bound for $C ≥ c∆$ with $c ≫ 1$ and a new upper bound of $O(n^{\frac{k+2}{k + 1}})$ for $C = ∆^k ≥ ∆^2$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(n^{\frac{k + 3}{k + 2}})$ queries, bypassing the classical lower bound when $C = c∆$ for $c ≫ 1$. Further, we show that the algorithm presented in Assadi et. al. SODA’19 for ($∆ + 1)$-coloring can be adapted to a quantum algorithm making $\tilde{O}(n^{4/3})$ queries. We also show initial upper and lower bounds for the very closely related problem of $\textit{verifying}$ whether or not a given graph coloring is valid.arXiv version slightly outdated, up to date version here arXiv Poster