Articles under category:
Polynomials - Multivariate
Vol 16, Article 17 (pp 1-29)
Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials
by Parikshit Gopalan and Amir Yehudayoff
Vol 16, Article 10 (pp 1-71)
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
by Mark Bun, Robin Kothari, and Justin Thaler
Vol 15, Article 13 (pp 1-34)
Closure Results for Polynomial Factorization
by Chi-Ning Chou, Mrinal Kumar, and Noam Solomon
Vol 15, Article 7 (pp 1-36)
Randomized Polynomial-Time Identity Testing for Noncommutative Circuits
by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja
Vol 14, Article 18 (pp 1-45)
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits
by Michael A. Forbes, Amir Shpilka, and Ben Lee Volk
Vol 14, Article 12 (pp 1-24)
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
by Swastik Kopparty and Srikanth Srinivasan
Vol 14, Article 3 (pp 1-21) [CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
Vol 13, Article 6 (pp 1-33) [CCC16 Spec Issue]
Arithmetic Circuits with Locally Low Algebraic Rank
by Mrinal Kumar and Shubhangi Saraf
Vol 13, Article 2 (pp 1-21) [CCC16 Spec Issue]
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
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 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 18 (pp 465-514)
On Reconstruction and Testing of Read-Once Formulas
by Amir Shpilka and Ilya Volkovich
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 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 12 (pp 177-184) [NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
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