Articles under category:
Polynomials - Multivariate
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 |