Articles under category:
Polynomials
ToC Library Graduate Surveys 2 (2011) 54 pages
Quantum Proofs for Classical Theorems
by Andrew Drucker and Ronald de Wolf
Vol 12, Article 16 (pp 1-34)
Dual Polynomials for Collision and Element Distinctness
by Mark Bun and Justin Thaler
Vol 12, Article 12 (pp 1-38)
Lower Bounds for Non-Commutative Skew Circuits
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Vol 12, Article 11 (pp 1-17)
Anti-concentration for Polynomials of Independent Random Variables
by Raghu Meka, Oanh Nguyen, and Van Vu
Vol 12, Article 7 (pp 1-27)
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
by Swastik Kopparty, Mrinal Kumar, and Michael Saks
Vol 11, Article 6 (pp 183-219)
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg
Vol 11, Article 5 (pp 149-182)
List-Decoding Multiplicity Codes
by Swastik Kopparty
Vol 10, Article 2 (pp 27-53)
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
Vol 10, Article 1 (pp 1-26) [Boolean Spec Issue]
Bounding the Sensitivity of Polynomial Threshold Functions
by Prahladh Harsha, Adam Klivans, and Raghu Meka
Vol 9, Article 27 (pp 845-862) [Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$
by Johan Håstad
Vol 9, Article 21 (pp 665-683) [APRX-RND12 Spec Issue]
Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic
by Eli Ben-Sasson and Ariel Gabizon
Vol 9, Article 20 (pp 653-663)
Approximating the AND-OR Tree
by Alexander A. Sherstov
Vol 9, Article 18 (pp 593-615) [Boolean Spec Issue]
Making Polynomials Robust to Noise
by Alexander A. Sherstov
Vol 9, Article 10 (pp 403-411)
On the Real $\tau$-Conjecture and the Distribution of Complex Roots
by Pavel Hrubeš
Vol 9, Article 9 (pp 349-401)
Quantum Money from Hidden Subspaces
by Scott Aaronson and Paul Christiano
Vol 9, Article 7 (pp 283-293)
Pseudorandomness for Width-2 Branching Programs
by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff
Vol 7, Article 13 (pp 185-188) [NOTE]
Computing Polynomials with Few Multiplications
by Shachar Lovett
Vol 7, Article 1 (pp 1-18)
Noisy Interpolating Sets for Low-Degree Polynomials
by Zeev Dvir and Amir Shpilka
Vol 6, Article 7 (pp 135-177)
Elusive Functions and Lower Bounds for Arithmetic Circuits
by Ran Raz
Vol 5, Article 3 (pp 69-82)
Unconditional Pseudorandom Generators for Low Degree Polynomials
by Shachar Lovett
Vol 4, Article 7 (pp 137-168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols
by Emanuele Viola and Avi Wigderson
Vol 2, Article 6 (pp 121-135)
Separation of Multilinear Circuit and Formula Size
by Ran Raz
Vol 1, Article 3 (pp 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
by Andris Ambainis