Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sreejata Bhattacharya:

TR24-035 | 20th February 2024
Sreejata Bhattacharya

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Revisions: 1

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial ... more >>>

TR24-022 | 6th February 2024
Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak

Exponential Separation Between Powers of Regular and General Resolution Over Parities

Revisions: 1

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities, is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret (2008). Very recently, Efremenko, Garlik and Itsykson (2023) proved the first exponential lower bounds ... more >>>

ISSN 1433-8092 | Imprint