Amir Shpilka

IEEE Trans. Inf. Theory, April, 2025

On Approximate Symmetric Polynomials and Tightness of Homogenization Results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Improved Debordering of Waring Rank.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

On the Complexity of Hazard-Free Formulas.

[BibT_eX]

[DOI]

Leah London Arazi

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, July, 2024

New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials.

[BibT_eX]

[DOI]

Ido Nahshon

Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, 2024

Tensor Reconstruction Beyond Constant Rank.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Discreteness of Asymptotic Tensor Ranks (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Lower Bounds for Set-Multilinear Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Reed-Muller Codes.

[BibT_eX]

[DOI]

Found. Trends Commun. Inf. Theory, 2023

Exponential Lower Bounds Against Sums of ROABPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials.

[BibT_eX]

[DOI]

Ido Nahshon

CoRR, 2023

Discreteness of asymptotic tensor ranks.

[BibT_eX]

[DOI]

CoRR, 2023

On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.

[BibT_eX]

[DOI]

Suryajith Chillara

Coral Grichener

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

2022

Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.

[BibT_eX]

[DOI]

Yuval Rabani

SIAM J. Comput., December, 2022

Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Reed Solomon Codes Against Adversarial Insertions and Deletions.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2022

Lower Bounds on Stabilizer Rank.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Reed-Muller Codes: Theory and Algorithms.

[BibT_eX]

[DOI]

Emmanuel Abbe

Min Ye

IEEE Trans. Inf. Theory, 2021

Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits.

[BibT_eX]

[DOI]

Dori Medini

Electron. Colloquium Comput. Complex., 2021

Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions.

[BibT_eX]

[DOI]

CoRR, 2021

Hitting Sets and Reconstruction for Dense Orbits in VPe and ΣΠΣ Circuits.

[BibT_eX]

[DOI]

Dori Medini

CoRR, 2021

Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Learnability can be independent of set theory (invited paper).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits.

[BibT_eX]

[DOI]

Dori Medini

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Polynomial time deterministic identity testingalgorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials.

[BibT_eX]

[DOI]

CoRR, 2020

On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures.

[BibT_eX]

[DOI]

Ori Sberlo

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2020

On Some Recent Advances in Algebraic Complexity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Author Correction: Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel.

[BibT_eX]

[DOI]

CoRR, 2019

Sylvester-Gallai type theorems for quadratic polynomials.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.

[BibT_eX]

[DOI]

Theory Comput., 2018

A PSPACE construction of a hitting set for the closure of small algebraic circuits.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

A learning problem that is independent of the set theory ZFC axioms.

[BibT_eX]

[DOI]

CoRR, 2017

Succinct hitting sets and barriers to proving algebraic circuits lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Tight lower bounds for linear 2-query LCCs over finite fields.

[BibT_eX]

[DOI]

Comb., 2016

Efficiently decoding Reed-Muller codes from random errors.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.

[BibT_eX]

[DOI]

Matthew Anderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Complexity Theory Column 88: Challenges in Polynomial Factorization1.

[BibT_eX]

[DOI]

SIGACT News, 2015

Teaching and compressing for low VC-dimension.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.

[BibT_eX]

[DOI]

Matthew Anderson

Electron. Colloquium Comput. Complex., 2015

Decoding high rate Reed-Muller codes from random errors in near linear time.

[BibT_eX]

[DOI]

CoRR, 2015

Equivalence of Polynomial Identity Testing and Polynomial Factorization.

[BibT_eX]

[DOI]

Swastik Kopparty

Shubhangi Saraf

Comput. Complex., 2015

Reed-Muller Codes for Random Erasures and Errors.

[BibT_eX]

[DOI]

Emmanuel Abbe

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Compressing and Teaching for Low VC-Dimension.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.

[BibT_eX]

[DOI]

Rafael Oliveira

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

On Reconstruction and Testing of Read-Once Formulas.

[BibT_eX]

[DOI]

Theory Comput., 2014

High Sum-Rate Three-Write and Nonbinary WOM Codes.

[BibT_eX]

[DOI]

Eitan Yaakobi

IEEE Trans. Inf. Theory, 2014

Capacity-Achieving Multiwrite WOM Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Hitting sets for multilinear read-once algebraic branching programs, in any order.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

On the structure of boolean functions with small spectral norm.

[BibT_eX]

[DOI]

Avishay Tal

Ben lee Volk

Proceedings of the Innovations in Theoretical Computer Science, 2014

Direct sum fails for zero error average communication.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Testing Equivalence of Polynomials under Shifts.

[BibT_eX]

[DOI]

Rafael Oliveira

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.

[BibT_eX]

[DOI]

Swastik Kopparty

Shubhangi Saraf

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

New Constructions of WOM Codes Using the Wozencraft Ensemble.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2013

On the Structure of Boolean Functions with Small Spectral Norm.

[BibT_eX]

[DOI]

Ben lee Volk

Electron. Colloquium Comput. Complex., 2013

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

On identity testing of tensors, low-rank recovery and compressed sensing.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Capacity Achieving Two-Write WOM Codes.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

High sum-rate three-write and non-binary WOM codes.

[BibT_eX]

[DOI]

Eitan Yaakobi

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

On the degree of univariate polynomials over the integers.

[BibT_eX]

[DOI]

Gil Cohen

Avishay Tal

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

On Sunflowers and Matrix Multiplication.

[BibT_eX]

[DOI]

Noga Alon

Christopher Umans

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Optimal Testing of Multivariate Polynomials over Small Prime Fields.

[BibT_eX]

[DOI]

Elad Haramaty

Madhu Sudan

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Tight Lower Bounds for 2-query LCCs over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Recent Results on Polynomial Identity Testing.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

On the Minimal Fourier Degree of Symmetric Boolean Functions.

[BibT_eX]

[DOI]

Avishay Tal

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Explicit Dimension Reduction and Its Applications.

[BibT_eX]

[DOI]

Yuval Rabani

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Symmetric LDPC Codes are not Necessarily Locally Testable.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Arithmetic Circuits: A survey of recent results and open questions.

[BibT_eX]

[DOI]

Amir Yehudayoff

Found. Trends Theor. Comput. Sci., 2010

Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields.

[BibT_eX]

[DOI]

Shachar Lovett

Partha Mukhopadhyay

Electron. Colloquium Comput. Complex., 2010

On the degree of symmetric functions on the Boolean cube.

[BibT_eX]

[DOI]

Gil Cohen

Electron. Colloquium Comput. Complex., 2010

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the structure of cubic and quartic polynomials.

[BibT_eX]

[DOI]

Elad Haramaty

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Shachar Lovett

Partha Mukhopadhyay

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Constructions of Low-degree and Error-Correcting epsilon-Biased Generators.

[BibT_eX]

[DOI]

Comput. Complex., 2009

The Black-Box Query Complexity of Polynomial Summation.

[BibT_eX]

[DOI]

Comput. Complex., 2009

Explicit construction of a small epsilon-net for linear threshold functions.

[BibT_eX]

[DOI]

Yuval Rabani

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Testing Fourier Dimensionality and Sparsity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

On the Complexity of Boolean Functions in Different Characteristics.

[BibT_eX]

[DOI]

Parikshit Gopalan

Shachar Lovett

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Improved Polynomial Identity Testing for Read-Once Formulas.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Read-once polynomial identity testing.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Hardness-randomness tradeoffs for bounded depth arithmetic circuits.

[BibT_eX]

[DOI]

Amir Yehudayoff

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Towards Dimension Expanders over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Noisy Interpolating Sets for Low Degree Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

An Improved Analysis of Linear Mergers.

[BibT_eX]

[DOI]

Comput. Complex., 2007

Interpolation of depth-3 arithmetic circuits with two multiplication gates.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.

[BibT_eX]

[DOI]

Amir Yehudayoff

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Learning Restricted Models of Arithmetic Circuits.

[BibT_eX]

[DOI]

Adam R. Klivans

Theory Comput., 2006

On epsilon-biased generators in NC0.

[BibT_eX]

[DOI]

Elchanan Mossel

Luca Trevisan

Random Struct. Algorithms, 2006

Constructions of Low-Degree and Error-Correcting in-Biased Generators.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Constructions of low-degree and error-correcting epsilon-biased sets

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

An Improved Analysis of Mergers.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2004

Derandomizing homomorphism testing in general groups.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

On the Power of Quantum Proofs.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Deterministic Polynomial Identity Testing in Non-Commutative Models.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

On epsilon-Biased Generators in NC0

[BibT_eX]

[DOI]

Elchanan Mossel

Luca Trevisan

Electron. Colloquium Comput. Complex., 2003

On e-Biased Generators in NC0.

[BibT_eX]

[DOI]

Elchanan Mossel

Luca Trevisan

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Locally Testable Cyclic Codes.

[BibT_eX]

[DOI]

László Babai

Daniel Stefankovic

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Learning Arithmetic Circuits via Partial Derivatives.

[BibT_eX]

[DOI]

Adam R. Klivans

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2001

Lower bounds for small depth arithmetic and Boolean circuits. (חסמים תחתונים למעגלים אריתמטים ובוליאנים מעומק חסום.).

[BibT_eX]

[DOI]

PhD thesis, 2001

Depth-3 arithmetic circuits over fields of characteristic zero.

[BibT_eX]

[DOI]

Comput. Complex., 2001

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Lower Bounds for Matrix Product.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Affine Projections of Symmetric Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

1999

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.

[BibT_eX]

[DOI]