45 papers
This paper proves that the Aaronson-Ambainis conjecture holds for a non-negligible fraction of random restrictions applied to bounded-degree polynomials with sufficient variance, demonstrating that such restrictions typically yield a coordinate with significant influence.
This paper presents a randomized polynomial-time algorithm for learning read-once determinants by establishing its equivalence to a black-box version of the Principal Minor Assignment Problem and resolving the latter through the introduction of the rank-one extension property.
This book surveys recent significant advances in the list decoding of Reed-Solomon and related polynomial-based codes, highlighting developments that achieve information-theoretic capacity with optimal list sizes using efficient, nearly-linear, and sublinear-time algorithms.
This paper demonstrates that any non-adaptive -query relaxed locally decodable code (RLDC) with sufficiently small soundness error can be converted into a standard -query locally decodable code (LDC) with comparable parameters, thereby generalizing previous separation results and yielding improved lower bounds for RLDCs, relaxed locally correctable codes (RLCCs), and probabilistically checkable proofs of proximity (PCPPs).
This paper presents a quantum algorithm for approximate graph isomorphism testing based on MNRS quantum walk search that achieves a query complexity of , establishing a polynomial speedup over the classical lower bound.