Amir Shpilka

According to our database, Amir Shpilka authored at least 121 papers between 1999 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Improved Debordering of Waring Rank.

Amir Shpilka

CoRR, February, 2025

2024

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

Roni Con, Amir Shpilka, Itzhak Tamo

IEEE Trans. Inf. Theory, July, 2024

On the Complexity of Hazard-Free Formulas.

Leah London Arazi, Amir Shpilka

CoRR, 2024

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

Ido Nahshon, Amir Shpilka

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

Discreteness of Asymptotic Tensor Ranks (Extended Abstract).

Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam

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

Lower Bounds for Set-Multilinear Branching Programs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Reed Solomon Codes Against Adversarial Insertions and Deletions.

Roni Con, Amir Shpilka, Itzhak Tamo

IEEE Trans. Inf. Theory, May, 2023

Reed-Muller Codes.

Emmanuel Abbe, Ori Sberlo, Amir Shpilka, Min Ye

Found. Trends Commun. Inf. Theory, 2023

Exponential Lower Bounds Against Sums of ROABPs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2023

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

Ido Nahshon, Amir Shpilka

CoRR, 2023

Discreteness of asymptotic tensor ranks.

Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam

CoRR, 2023

2022

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

Yuval Rabani, Amir Shpilka

SIAM J. Comput., December, 2022

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

Roni Con, Amir Shpilka, Itzhak Tamo

IEEE Trans. Inf. Theory, 2022

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

Roni Con, Amir Shpilka

IEEE Trans. Inf. Theory, 2022

Lower Bounds on Stabilizer Rank.

Shir Peleg, Amir Shpilka, Ben Lee Volk

Quantum, 2022

Tensor Reconstruction Beyond Constant Rank.

Shir Peleg, Amir Shpilka, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2022

On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.

Suryajith Chillara, Coral Grichener, Amir Shpilka

Electron. Colloquium Comput. Complex., 2022

Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials.

Shir Peleg, Amir Shpilka

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

2021

Reed-Muller Codes: Theory and Algorithms.

Emmanuel Abbe, Amir Shpilka, Min Ye

IEEE Trans. Inf. Theory, 2021

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

Dori Medini, Amir Shpilka

Electron. Colloquium Comput. Complex., 2021

Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions.

Roni Con, Amir Shpilka, Itzhak Tamo

CoRR, 2021

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

Dori Medini, Amir Shpilka

CoRR, 2021

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

Shir Peleg, Amir Shpilka

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

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

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

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.

Dori Medini, Amir Shpilka

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.

Shir Peleg, Amir Shpilka

CoRR, 2020

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

Ori Sberlo, Amir Shpilka

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

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

Roni Con, Amir Shpilka

Proceedings of the IEEE International Symposium on Information Theory, 2020

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

Amir Shpilka

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.

Shir Peleg, Amir Shpilka

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Author Correction: Learnability can be undecidable.

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

Nat. Mach. Intell., 2019

Learnability can be undecidable.

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

Nat. Mach. Intell., 2019

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

Roni Con, Amir Shpilka

CoRR, 2019

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Comput. Complex., 2019

Sylvester-Gallai type theorems for quadratic polynomials.

Amir Shpilka

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.

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Theory Comput., 2018

2017

Efficiently Decoding Reed-Muller Codes From Random Errors.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

IEEE Trans. Inf. Theory, 2017

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

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2017

A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.

Michael A. Forbes, Amir Shpilka

Electron. Colloquium Comput. Complex., 2017

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

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

CoRR, 2017

On the Structure of Boolean Functions with Small Spectral Norm.

Amir Shpilka, Avishay Tal, Ben lee Volk

Comput. Complex., 2017

2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

Electron. Colloquium Comput. Complex., 2016

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Comb., 2016

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.

Rafael Oliveira, Amir Shpilka, Ben lee Volk

Comput. Complex., 2016

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

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Reed-Muller Codes for Random Erasures and Errors.

Emmanuel Abbe, Amir Shpilka, Avi Wigderson

IEEE Trans. Inf. Theory, 2015

Complexity Theory Column 88: Challenges in Polynomial Factorization1.

Michael A. Forbes, Amir Shpilka

SIGACT News, 2015

Teaching and compressing for low VC-dimension.

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2015

Identity Testing and Lower Bounds for Read-<i>k</i> Oblivious Algebraic Branching Programs.

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2015

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

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

CoRR, 2015

Read-once polynomial identity testing.

Amir Shpilka, Ilya Volkovich

Comput. Complex., 2015

Equivalence of Polynomial Identity Testing and Polynomial Factorization.

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Comput. Complex., 2015

Compressing and Teaching for Low VC-Dimension.

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

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

2014

On Reconstruction and Testing of Read-Once Formulas.

Amir Shpilka, Ilya Volkovich

Theory Comput., 2014

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

Eitan Yaakobi, Amir Shpilka

IEEE Trans. Inf. Theory, 2014

Capacity-Achieving Multiwrite WOM Codes.

Amir Shpilka

IEEE Trans. Inf. Theory, 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2014

Testing Equivalence of Polynomials under Shifts.

Zeev Dvir, Rafael Oliveira, Amir Shpilka

Electron. Colloquium Comput. Complex., 2014

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

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Proceedings of the Symposium on Theory of Computing, 2014

2013

New Constructions of WOM Codes Using the Wozencraft Ensemble.

Amir Shpilka

IEEE Trans. Inf. Theory, 2013

Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in.

Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

SIAM J. Comput., 2013

Optimal Testing of Multivariate Polynomials over Small Prime Fields.

Elad Haramaty, Amir Shpilka, Madhu Sudan

SIAM J. Comput., 2013

On the Structure of Boolean Functions with Small Spectral Norm.

Amir Shpilka, Ben lee Volk

Electron. Colloquium Comput. Complex., 2013

Direct Sum Fails for Zero Error Average Communication.

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2013

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

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Electron. Colloquium Comput. Complex., 2013

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.

Michael A. Forbes, Amir Shpilka

Electron. Colloquium Comput. Complex., 2013

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

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Comput. Complex., 2013

On sunflowers and matrix multiplication.

Noga Alon, Amir Shpilka, Christopher Umans

Comput. Complex., 2013

2012

Explicit Dimension Reduction and Its Applications.

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka

SIAM J. Comput., 2012

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.

Michael A. Forbes, Amir Shpilka

Electron. Colloquium Comput. Complex., 2012

Capacity Achieving Two-Write WOM Codes.

Amir Shpilka

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

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

Eitan Yaakobi, Amir Shpilka

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

2011

Testing Fourier Dimensionality and Sparsity.

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer

SIAM J. Comput., 2011

On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.

Michael A. Forbes, Amir Shpilka

Electron. Colloquium Comput. Complex., 2011

On the Degree of Univariate Polynomials Over the Integers.

Gil Cohen, Amir Shpilka, Avishay Tal

Electron. Colloquium Comput. Complex., 2011

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2011

On Sums of Locally Testable Affine Invariant Properties.

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2011

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in.

Zohar Shay Karnin, Amir Shpilka

Comb., 2011

Recent Results on Polynomial Identity Testing.

Amir Shpilka

Proceedings of the Computer Science - Theory and Applications, 2011

2010

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

Yuval Rabani, Amir Shpilka

SIAM J. Comput., 2010

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

Amir Shpilka, Amir Yehudayoff

Found. Trends Theor. Comput. Sci., 2010

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

Amir Shpilka, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2010

On the Minimal Fourier Degree of Symmetric Boolean Functions.

Amir Shpilka, Avishay Tal

Electron. Colloquium Comput. Complex., 2010

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

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Electron. Colloquium Comput. Complex., 2010

On the degree of symmetric functions on the Boolean cube.

Gil Cohen, Amir Shpilka

Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC codes are not necessarily locally testable.

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

The Complexity of Boolean Functions in Different Characteristics.

Parikshit Gopalan, Amir Shpilka, Shachar Lovett

Comput. Complex., 2010

2009

Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates.

Amir Shpilka

SIAM J. Comput., 2009

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

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith

SIAM J. Comput., 2009

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

SIAM J. Comput., 2009

On the Structure of Cubic and Quartic Polynomials.

Elad Haramaty, Amir Shpilka

Electron. Colloquium Comput. Complex., 2009

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

Amir Shpilka

Comput. Complex., 2009

The Black-Box Query Complexity of Polynomial Summation.

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

Comput. Complex., 2009

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

Zohar Shay Karnin, Amir Shpilka

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

Improved Polynomial Identity Testing for Read-Once Formulas.

Amir Shpilka, Ilya Volkovich

Proceedings of the Approximation, 2009

2008

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

Ran Raz, Amir Shpilka, Amir Yehudayoff

SIAM J. Comput., 2008

Noisy Interpolating Sets for Low Degree Polynomials.

Zeev Dvir, Amir Shpilka

Electron. Colloquium Comput. Complex., 2008

2007

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

Zeev Dvir, Amir Shpilka

SIAM J. Comput., 2007

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

Zohar Shay Karnin, Amir Shpilka

Electron. Colloquium Comput. Complex., 2007

Towards Dimension Expanders Over Finite Fields.

Zeev Dvir, Amir Shpilka

Electron. Colloquium Comput. Complex., 2007

An Improved Analysis of Linear Mergers.

Zeev Dvir, Amir Shpilka

Comput. Complex., 2007

2006

Learning Restricted Models of Arithmetic Circuits.

Adam R. Klivans, Amir Shpilka

Theory Comput., 2006

Derandomizing Homomorphism Testing in General Groups.

Amir Shpilka, Avi Wigderson

SIAM J. Comput., 2006

On epsilon-biased generators in NC⁰.

Elchanan Mossel, Amir Shpilka, Luca Trevisan

Random Struct. Algorithms, 2006

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

Amir Shpilka

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

2005

Locally testable cyclic codes.

László Babai, Amir Shpilka, Daniel Stefankovic

IEEE Trans. Inf. Theory, 2005

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

Amir Shpilka

Electron. Colloquium Comput. Complex., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith

Electron. Colloquium Comput. Complex., 2005

An Improved Analysis of Mergers

Zeev Dvir, Amir Shpilka

Electron. Colloquium Comput. Complex., 2005

Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

Zeev Dvir, Amir Shpilka

Electron. Colloquium Comput. Complex., 2005

Deterministic polynomial identity testing in non-commutative models.

Ran Raz, Amir Shpilka

Comput. Complex., 2005

2004

On the Power of Quantum Proofs.

Ran Raz, Amir Shpilka

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

2003

Lower Bounds for Matrix Product.

Amir Shpilka

SIAM J. Comput., 2003

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates.

Ran Raz, Amir Shpilka

SIAM J. Comput., 2003

On epsilon-Biased Generators in NC0

Elchanan Mossel, Amir Shpilka, Luca Trevisan

Electron. Colloquium Comput. Complex., 2003

On e-Biased Generators in NC0.

Elchanan Mossel, Amir Shpilka, Luca Trevisan

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

Learning Arithmetic Circuits via Partial Derivatives.

Adam R. Klivans, Amir Shpilka

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Affine projections of symmetric polynomials.

Amir Shpilka

J. Comput. Syst. Sci., 2002

2001

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

Amir Shpilka

PhD thesis, 2001

Depth-3 arithmetic circuits over fields of characteristic zero.

Amir Shpilka, Avi Wigderson

Comput. Complex., 2001

1999

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

Amir Shpilka, Avi Wigderson

Electron. Colloquium Comput. Complex., 1999