We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathrm{E}^{\mathrm{prMA}}/_1$, corresponding to exponential time with access to a promise-$\mathrm{MA}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen--Lu--Oliveira--Ren--Santhanam, FOCS'23), the reduction from the Range Avoidance problem to circuit lower bounds ... more >>>

We study one-way quantum communication lower bounds for search problems.Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of ... more >>>

We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some natural number $m$.
Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach ... more >>>