50 citations · 140 across the 23 of their papers we have counts for
4 papers · 1 filter
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
Yuval Filmus, Or Meir, Avishay Tal
Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restriction…
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +2
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , : The degree of…
Rigid Matrices From Rectangular PCPs
Amey Bhangale, Prahladh Harsha, Orr Paradise +1
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned…
Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +1
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , the deterministic query complexity, , is at most quartic in the quantum que…