3 citations · 8 across the 11 of their papers we have counts for
Showing quant-phShow all
2 papers · 1 filter
quant-ph2026
Noisy Quantum Query Complexity via Fractional Block Sensitivity
Mehil Agarwal, Shravas Rao, Fang Song
We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\oper…
quant-ph2020
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…