Amir Shpilka

229 papers A* 32A 29B 5Misc 1Journal 152Unranked 9
YearRankTypeTitle / Venue / Authors
2026 J jnl
On Factorization of Sparse Polynomials of Bounded Individual Degree.
CoRR
Aminadav Chuyoon, Amir Shpilka
2026 J jnl
On Factorization of Sparse Polynomials of Bounded Individual Degree.
Electron. Colloquium Comput. Complex.
Aminadav Chuyoon, Amir Shpilka
2026 J jnl
Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree.
CoRR
Amir Shpilka, Yann Tal
2026 J jnl
Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Yann Tal
2025 J jnl
Corrections to "Reed Solomon Codes Against Adversarial Insertions and Deletions".
IEEE Trans. Inf. Theory
Roni Con, Amir Shpilka, Itzhak Tamo
2025 J jnl
Improved Debordering of Waring Rank.
CoRR
Amir Shpilka
2025 J jnl
Improved Debordering of Waring Rank.
Electron. Colloquium Comput. Complex.
Amir Shpilka
2025 J jnl
On Approximate Symmetric Polynomials and Tightness of Homogenization Results.
Electron. Colloquium Comput. Complex.
Amir Shpilka
2025 A* conf
On the Complexity of Hazard-Free Formulas.
ICALP
Leah London Arazi, Amir Shpilka
2024 A conf
Discreteness of Asymptotic Tensor Ranks (Extended Abstract).
ITCS
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
2024 A conf
Lower Bounds for Set-Multilinear Branching Programs.
CCC
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2024 B conf
New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials.
ISSAC
Ido Nahshon, Amir Shpilka
2024 J jnl
On the Complexity of Hazard-Free Formulas.
CoRR
Leah London Arazi, Amir Shpilka
2024 J jnl
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions.
IEEE Trans. Inf. Theory
Roni Con, Amir Shpilka, Itzhak Tamo
2024 A conf
Tensor Reconstruction Beyond Constant Rank.
ITCS
Shir Peleg, Amir Shpilka, Ben Lee Volk
2023 J jnl
Discreteness of asymptotic tensor ranks.
CoRR
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
2023 J jnl
Exponential Lower Bounds Against Sums of ROABPs.
Electron. Colloquium Comput. Complex.
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
Lower Bounds for Set-Multilinear Branching Programs.
CoRR
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials.
CoRR
Ido Nahshon, Amir Shpilka
2023 A conf
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.
STACS
Suryajith Chillara, Coral Grichener, Amir Shpilka
2023 J jnl
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions.
CoRR
Roni Con, Amir Shpilka, Itzhak Tamo
2023 J jnl
Reed Solomon Codes Against Adversarial Insertions and Deletions.
IEEE Trans. Inf. Theory
Roni Con, Amir Shpilka, Itzhak Tamo
2023 J jnl
Reed-Muller Codes.
Found. Trends Commun. Inf. Theory
Emmanuel Abbe, Ori Sberlo, Amir Shpilka, Min Ye
2022 J jnl
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.
SIAM J. Comput.
Yuval Rabani, Amir Shpilka
2022 J jnl
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions.
IEEE Trans. Inf. Theory
Roni Con, Amir Shpilka, Itzhak Tamo
2022 J jnl
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions.
CoRR
Roni Con, Amir Shpilka, Itzhak Tamo
2022 J jnl
Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel.
IEEE Trans. Inf. Theory
Roni Con, Amir Shpilka
2022 A conf
Lower Bounds on Stabilizer Rank.
ITCS
Shir Peleg, Ben Lee Volk, Amir Shpilka
2022 J jnl
Lower Bounds on Stabilizer Rank.
Quantum
Shir Peleg, Amir Shpilka, Ben Lee Volk
2022 J jnl
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.
CoRR
Suryajith Chillara, Coral Grichener, Amir Shpilka
2022 J jnl
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.
Electron. Colloquium Comput. Complex.
Suryajith Chillara, Coral Grichener, Amir Shpilka
2022 B conf
Reed Solomon Codes Against Adversarial Insertions and Deletions.
ISIT
Roni Con, Amir Shpilka, Itzhak Tamo
2022 A* conf
Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials.
SoCG
Shir Peleg, Amir Shpilka
2022 J jnl
Robust Sylvester-Gallai type theorem for quadratic polynomials.
CoRR
Shir Peleg, Amir Shpilka
2022 J jnl
Tensor Reconstruction Beyond Constant Rank.
CoRR
Shir Peleg, Amir Shpilka, Ben Lee Volk
2022 J jnl
Tensor Reconstruction Beyond Constant Rank.
Electron. Colloquium Comput. Complex.
Shir Peleg, Amir Shpilka, Ben Lee Volk
2021 J jnl
Hitting Sets and Reconstruction for Dense Orbits in VP
CoRR
Dori Medini, Amir Shpilka
2021 J jnl
Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits.
Electron. Colloquium Comput. Complex.
Dori Medini, Amir Shpilka
2021 A conf
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits.
CCC
Dori Medini, Amir Shpilka
2021 A* conf
Learnability can be independent of set theory (invited paper).
STOC
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2021 J jnl
Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions.
CoRR
Roni Con, Amir Shpilka, Itzhak Tamo
2021 J jnl
Lower Bounds on Stabilizer Rank.
CoRR
Shir Peleg, Amir Shpilka, Ben Lee Volk
2021 J jnl
Lower Bounds on Stabilizer Rank.
Electron. Colloquium Comput. Complex.
Shir Peleg, Amir Shpilka, Ben Lee Volk
2021 A* conf
Polynomial time deterministic identity testing algorithm for Σ
STOC
Shir Peleg, Amir Shpilka
2021 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Theory Comput.
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2021 J jnl
Reed-Muller Codes: Theory and Algorithms.
IEEE Trans. Inf. Theory
Emmanuel Abbe, Amir Shpilka, Min Ye
2020 A conf
A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials.
CCC
Shir Peleg, Amir Shpilka
2020 J jnl
A generalized Sylvester-Gallai type theorem for quadratic polynomials.
CoRR
Shir Peleg, Amir Shpilka
2020 B conf
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel.
ISIT
Roni Con, Amir Shpilka
2020 — conf
On Some Recent Advances in Algebraic Complexity (Invited Talk).
FSTTCS
Amir Shpilka
2020 A* conf
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures.
SODA
Ori Sberlo, Amir Shpilka
2020 J jnl
Polynomial time deterministic identity testingalgorithm for Σ
CoRR
Shir Peleg, Amir Shpilka
2020 J jnl
Reed-Muller Codes: Theory and Algorithms.
CoRR
Emmanuel Abbe, Amir Shpilka, Min Ye
2019 A ed.
34th Computational Complexity Conference, CCC 2019, New Brunswick, NJ, USA, July 18-20, 2019
CCC
Amir Shpilka
2019 J jnl
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.
Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 J jnl
Author Correction: Learnability can be undecidable.
Nat. Mach. Intell.
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 J jnl
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel.
CoRR
Roni Con, Amir Shpilka
2019 J jnl
Learnability can be undecidable.
Nat. Mach. Intell.
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 A* conf
Sylvester-Gallai type theorems for quadratic polynomials.
STOC
Amir Shpilka
2019 J jnl
Sylvester-Gallai type theorems for quadratic polynomials.
CoRR
Amir Shpilka
2018 A* conf
A PSPACE construction of a hitting set for the closure of small algebraic circuits.
STOC
Michael A. Forbes, Amir Shpilka
2018 J jnl
Identity Testing and Lower Bounds for Read-
ACM Trans. Comput. Theory
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2018 J jnl
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures.
CoRR
Ori Sberlo, Amir Shpilka
2018 J jnl
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.
Theory Comput.
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 J jnl
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.
CoRR
Michael A. Forbes, Amir Shpilka
2017 J jnl
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2017 J jnl
A learning problem that is independent of the set theory ZFC axioms.
CoRR
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2017 J jnl
Efficiently Decoding Reed-Muller Codes From Random Errors.
IEEE Trans. Inf. Theory
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2017 J jnl
On the Structure of Boolean Functions with Small Spectral Norm.
Comput. Complex.
Amir Shpilka, Avishay Tal, Ben Lee Volk
2017 J jnl
On the degree of univariate polynomials over the integers.
Comb.
Gil Cohen, Amir Shpilka, Avishay Tal
2017 J jnl
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds.
CoRR
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 J jnl
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 A* conf
Succinct hitting sets and barriers to proving algebraic circuits lower bounds.
STOC
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2016 J jnl
Direct Sum Fails for Zero-Error Average Communication.
Algorithmica
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2016 A* conf
Efficiently decoding Reed-Muller codes from random errors.
STOC
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2016 A conf
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.
CCC
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2016 A conf
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
CCC
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
CoRR
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016 J jnl
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.
Comput. Complex.
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
2016 J jnl
Tight lower bounds for linear 2-query LCCs over finite fields.
Comb.
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
2015 J jnl
Complexity Theory Column 88: Challenges in Polynomial Factorization1.
SIGACT News
Michael A. Forbes, Amir Shpilka
2015 A* conf
Compressing and Teaching for Low VC-Dimension.
FOCS
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015 J jnl
Decoding high rate Reed-Muller codes from random errors in near linear time.
CoRR
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2015 J jnl
Equivalence of Polynomial Identity Testing and Polynomial Factorization.
Comput. Complex.
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2015 J jnl
Identity Testing and Lower Bounds for Read-
Electron. Colloquium Comput. Complex.
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2015 J jnl
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs.
CoRR
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2015 J jnl
Read-once polynomial identity testing.
Comput. Complex.
Amir Shpilka, Ilya Volkovich
2015 A* conf
Reed-Muller Codes for Random Erasures and Errors.
STOC
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2015 J jnl
Reed-Muller Codes for Random Erasures and Errors.
IEEE Trans. Inf. Theory
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2015 A conf
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.
CCC
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
2015 J jnl
Teaching and compressing for low VC-dimension.
CoRR
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015 J jnl
Teaching and compressing for low VC-dimension.
Electron. Colloquium Comput. Complex.
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2014 — conf
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.
ICALP (1)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 J jnl
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.
Electron. Colloquium Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 J jnl
Capacity-Achieving Multiwrite WOM Codes.
IEEE Trans. Inf. Theory
Amir Shpilka
2014 A conf
Direct sum fails for zero error average communication.
ITCS
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 A conf
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.
CCC
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2014 J jnl
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2014 J jnl
High Sum-Rate Three-Write and Nonbinary WOM Codes.
IEEE Trans. Inf. Theory
Eitan Yaakobi, Amir Shpilka
2014 A* conf
Hitting sets for multilinear read-once algebraic branching programs, in any order.
STOC
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2014 J jnl
On Reconstruction and Testing of Read-Once Formulas.
Theory Comput.
Amir Shpilka, Ilya Volkovich
2014 J jnl
On the minimal fourier degree of symmetric Boolean functions.
Comb.
Amir Shpilka, Avishay Tal
2014 A conf
On the structure of boolean functions with small spectral norm.
ITCS
Amir Shpilka, Avishay Tal, Ben Lee Volk
2014 J jnl
Reed-Muller codes for random erasures and errors.
CoRR
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2014 J jnl
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.
CoRR
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
2014 J jnl
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.
Electron. Colloquium Comput. Complex.
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
2014 — conf
Testing Equivalence of Polynomials under Shifts.
ICALP (1)
Zeev Dvir, Rafael Oliveira, Amir Shpilka
2014 J jnl
Testing Equivalence of Polynomials under Shifts.
CoRR
Zeev Dvir, Rafael Oliveira, Amir Shpilka
2014 J jnl
Testing Equivalence of Polynomials under Shifts.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Rafael Oliveira, Amir Shpilka
2013 J jnl
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in.
SIAM J. Comput.
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2013 J jnl
Direct Sum Fails for Zero Error Average Communication.
Electron. Colloquium Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2013 J jnl
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
CoRR
Michael A. Forbes, Amir Shpilka
2013 — conf
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.
APPROX-RANDOM
Michael A. Forbes, Amir Shpilka
2013 J jnl
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2013 J jnl
New Constructions of WOM Codes Using the Wozencraft Ensemble.
IEEE Trans. Inf. Theory
Amir Shpilka
2013 J jnl
On sunflowers and matrix multiplication.
Comput. Complex.
Noga Alon, Amir Shpilka, Christopher Umans
2013 J jnl
On the Structure of Boolean Functions with Small Spectral Norm
CoRR
Amir Shpilka, Ben Lee Volk
2013 J jnl
On the Structure of Boolean Functions with Small Spectral Norm.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Ben Lee Volk
2013 J jnl
Optimal Testing of Multivariate Polynomials over Small Prime Fields.
SIAM J. Comput.
Elad Haramaty, Amir Shpilka, Madhu Sudan
2013 J jnl
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields.
Comput. Complex.
Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka
2013 J jnl
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.
CoRR
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2013 J jnl
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2013 A* conf
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs.
FOCS
Michael A. Forbes, Amir Shpilka
2012 B conf
Capacity Achieving Two-Write WOM Codes.
LATIN
Amir Shpilka
2012 J jnl
Capacity achieving multiwrite WOM codes
CoRR
Amir Shpilka
2012 J jnl
Explicit Dimension Reduction and Its Applications.
SIAM J. Comput.
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
2012 B conf
High sum-rate three-write and non-binary WOM codes.
ISIT
Eitan Yaakobi, Amir Shpilka
2012 A conf
On Sunflowers and Matrix Multiplication.
CCC
Noga Alon, Amir Shpilka, Christopher Umans
2012 A* conf
On identity testing of tensors, low-rank recovery and compressed sensing.
STOC
Michael A. Forbes, Amir Shpilka
2012 A conf
On the degree of univariate polynomials over the integers.
ITCS
Gil Cohen, Amir Shpilka, Avishay Tal
2012 J jnl
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
CoRR
Michael A. Forbes, Amir Shpilka
2012 J jnl
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2011 J jnl
Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in.
Comb.
Zohar Shay Karnin, Amir Shpilka
2011 A conf
Explicit Dimension Reduction and Its Applications.
CCC
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
2011 J jnl
New constructions of WOM codes using the Wozencraft ensemble
CoRR
Amir Shpilka
2011 J jnl
Noisy Interpolating Sets for Low-Degree Polynomials.
Theory Comput.
Zeev Dvir, Amir Shpilka
2011 J jnl
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
CoRR
Michael A. Forbes, Amir Shpilka
2011 J jnl
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2011 — conf
On Sums of Locally Testable Affine Invariant Properties.
APPROX-RANDOM
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011 J jnl
On Sums of Locally Testable Affine Invariant Properties.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011 J jnl
On Sunflowers and Matrix Multiplication.
Electron. Colloquium Comput. Complex.
Noga Alon, Amir Shpilka, Christopher Umans
2011 J jnl
On the Degree of Univariate Polynomials Over the Integers.
Electron. Colloquium Comput. Complex.
Gil Cohen, Amir Shpilka, Avishay Tal
2011 A conf
On the Minimal Fourier Degree of Symmetric Boolean Functions.
CCC
Amir Shpilka, Avishay Tal
2011 A* conf
Optimal Testing of Multivariate Polynomials over Small Prime Fields.
FOCS
Elad Haramaty, Amir Shpilka, Madhu Sudan
2011 J jnl
Optimal testing of multivariate polynomials over small prime fields.
Electron. Colloquium Comput. Complex.
Elad Haramaty, Amir Shpilka, Madhu Sudan
2011 Misc conf
Recent Results on Polynomial Identity Testing.
CSR
Amir Shpilka
2011 A conf
Symmetric LDPC Codes are not Necessarily Locally Testable.
CCC
Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011 J jnl
Testing Fourier Dimensionality and Sparsity.
SIAM J. Comput.
Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2011 A* conf
Tight Lower Bounds for 2-query LCCs over Finite Fields.
FOCS
Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf
2011 J jnl
Tight lower bounds for 2-query LCCs over finite fields.
Electron. Colloquium Comput. Complex.
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
2011 J jnl
Towards dimension expanders over finite fields.
Comb.
Zeev Dvir, Amir Shpilka
2010 J jnl
Arithmetic Circuits: A survey of recent results and open questions.
Found. Trends Theor. Comput. Sci.
Amir Shpilka, Amir Yehudayoff
2010 A* conf
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in.
STOC
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2010 J jnl
Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.
SIAM J. Comput.
Yuval Rabani, Amir Shpilka
2010 J jnl
On the Minimal Fourier Degree of Symmetric Boolean Functions.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Avishay Tal
2010 — conf
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.
ICALP (1)
Amir Shpilka, Ilya Volkovich
2010 J jnl
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Ilya Volkovich
2010 J jnl
On the degree of symmetric functions on the Boolean cube.
Electron. Colloquium Comput. Complex.
Gil Cohen, Amir Shpilka
2010 A* conf
On the structure of cubic and quartic polynomials.
STOC
Elad Haramaty, Amir Shpilka
2010 A* conf
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields.
FOCS
Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka
2010 J jnl
Pseudorandom generators for CC
Electron. Colloquium Comput. Complex.
Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka
2010 J jnl
Read-Once Polynomial Identity Testing.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Ilya Volkovich
2010 J jnl
Symmetric LDPC codes are not necessarily locally testable.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2010 J jnl
The Complexity of Boolean Functions in Different Characteristics.
Comput. Complex.
Parikshit Gopalan, Amir Shpilka, Shachar Lovett
2009 J jnl
Constructions of Low-degree and Error-Correcting epsilon-Biased Generators.
Comput. Complex.
Amir Shpilka
2009 J jnl
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in.
Electron. Colloquium Comput. Complex.
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2009 J jnl
Explicit Dimension Reduction and Its Applications.
Electron. Colloquium Comput. Complex.
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
2009 A* conf
Explicit construction of a small epsilon-net for linear threshold functions.
STOC
Yuval Rabani, Amir Shpilka
2009 J jnl
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.
SIAM J. Comput.
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2009 — conf
Improved Polynomial Identity Testing for Read-Once Formulas.
APPROX-RANDOM
Amir Shpilka, Ilya Volkovich
2009 J jnl
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates.
SIAM J. Comput.
Amir Shpilka
2009 A conf
On the Complexity of Boolean Functions in Different Characteristics.
CCC
Parikshit Gopalan, Shachar Lovett, Amir Shpilka
2009 J jnl
On the Complexity of Boolean Functions in Different Characteristics.
Electron. Colloquium Comput. Complex.
Parikshit Gopalan, Shachar Lovett, Amir Shpilka
2009 J jnl
On the Structure of Cubic and Quartic Polynomials.
Electron. Colloquium Comput. Complex.
Elad Haramaty, Amir Shpilka
2009 A conf
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in.
CCC
Zohar Shay Karnin, Amir Shpilka
2009 J jnl
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
SIAM J. Comput.
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2009 — conf
Testing Fourier Dimensionality and Sparsity.
ICALP (1)
Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2009 J jnl
The Black-Box Query Complexity of Polynomial Summation.
Comput. Complex.
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
2008 J jnl
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
SIAM J. Comput.
Ran Raz, Amir Shpilka, Amir Yehudayoff
2008 A conf
Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In.
CCC
Zohar Shay Karnin, Amir Shpilka
2008 A* conf
Hardness-randomness tradeoffs for bounded depth arithmetic circuits.
STOC
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2008 A conf
Noisy Interpolating Sets for Low Degree Polynomials.
CCC
Zeev Dvir, Amir Shpilka
2008 J jnl
Noisy Interpolating Sets for Low Degree Polynomials.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka
2008 A* conf
Read-once polynomial identity testing.
STOC
Amir Shpilka, Ilya Volkovich
2008 A conf
Towards Dimension Expanders over Finite Fields.
CCC
Zeev Dvir, Amir Shpilka
2007 A* conf
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
FOCS
Ran Raz, Amir Shpilka, Amir Yehudayoff
2007 J jnl
An Improved Analysis of Linear Mergers.
Comput. Complex.
Zeev Dvir, Amir Shpilka
2007 J jnl
Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in.
Electron. Colloquium Comput. Complex.
Zohar Shay Karnin, Amir Shpilka
2007 J jnl
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2007 A* conf
Interpolation of depth-3 arithmetic circuits with two multiplication gates.
STOC
Amir Shpilka
2007 J jnl
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits.
SIAM J. Comput.
Zeev Dvir, Amir Shpilka
2007 A* conf
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
FOCS
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2007 J jnl
The black-box query complexity of polynomial summation.
Electron. Colloquium Comput. Complex.
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
2007 J jnl
Towards Dimension Expanders Over Finite Fields.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka
2006 J jnl
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Ran Raz, Amir Shpilka, Amir Yehudayoff
2006 A conf
Constructions of Low-Degree and Error-Correcting in-Biased Generators.
CCC
Amir Shpilka
2006 J jnl
Derandomizing Homomorphism Testing in General Groups.
SIAM J. Comput.
Amir Shpilka, Avi Wigderson
2006 J jnl
Learning Restricted Models of Arithmetic Circuits.
Theory Comput.
Adam R. Klivans, Amir Shpilka
2006 J jnl
On epsilon-biased generators in NC
Random Struct. Algorithms
Elchanan Mossel, Amir Shpilka, Luca Trevisan
2005 J jnl
An Improved Analysis of Mergers
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka
2005 — conf
An Improved Analysis of Mergers.
APPROX-RANDOM
Zeev Dvir, Amir Shpilka
2005 J jnl
Constructions of low-degree and error-correcting epsilon-biased sets
Electron. Colloquium Comput. Complex.
Amir Shpilka
2005 J jnl
Deterministic polynomial identity testing in non-commutative models.
Comput. Complex.
Ran Raz, Amir Shpilka
2005 J jnl
Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka
2005 A* conf
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.
STOC
Zeev Dvir, Amir Shpilka
2005 J jnl
Locally testable cyclic codes.
IEEE Trans. Inf. Theory
László Babai, Amir Shpilka, Daniel Stefankovic
2005 J jnl
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electron. Colloquium Comput. Complex.
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith
2004 A* conf
Derandomizing homomorphism testing in general groups.
STOC
Amir Shpilka, Avi Wigderson
2004 A conf
Deterministic Polynomial Identity Testing in Non-Commutative Models.
CCC
Ran Raz, Amir Shpilka
2004 A conf
On the Power of Quantum Proofs.
CCC
Ran Raz, Amir Shpilka
2003 A* conf
Learning Arithmetic Circuits via Partial Derivatives.
COLT
Adam R. Klivans, Amir Shpilka
2003 A* conf
Locally Testable Cyclic Codes.
FOCS
László Babai, Amir Shpilka, Daniel Stefankovic
2003 J jnl
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates.
SIAM J. Comput.
Ran Raz, Amir Shpilka
2003 J jnl
Lower Bounds for Matrix Product.
SIAM J. Comput.
Amir Shpilka
2003 A* conf
On e-Biased Generators in NC0.
FOCS
Elchanan Mossel, Amir Shpilka, Luca Trevisan
2003 J jnl
On epsilon-Biased Generators in NC0
Electron. Colloquium Comput. Complex.
Elchanan Mossel, Amir Shpilka, Luca Trevisan
2002 J jnl
Affine projections of symmetric polynomials.
J. Comput. Syst. Sci.
Amir Shpilka
2002 J jnl
Lower Bounds for Matrix Product
CoRR
Amir Shpilka
2001 J jnl
Affine Projections of Symmetric Polynomials
Electron. Colloquium Comput. Complex.
Amir Shpilka
2001 A conf
Affine Projections of Symmetric Polynomials.
CCC
Amir Shpilka
2001 J jnl
Depth-3 arithmetic circuits over fields of characteristic zero.
Comput. Complex.
Amir Shpilka, Avi Wigderson
2001 A* conf
Lower Bounds for Matrix Product.
FOCS
Amir Shpilka
2001 J jnl
Lower bounds for matrix product
Electron. Colloquium Comput. Complex.
Amir Shpilka
2001 A* conf
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.
STOC
Ran Raz, Amir Shpilka
2001 — —
Lower bounds for small depth arithmetic and Boolean circuits. (חסמים תחתונים למעגלים אריתמטים ובוליאנים מעומק חסום.).
Amir Shpilka
2000 J jnl
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates
Electron. Colloquium Comput. Complex.
Ran Raz, Amir Shpilka
1999 J jnl
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Electron. Colloquium Comput. Complex.
Amir Shpilka, Avi Wigderson
1999 A conf
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.
CCC
Amir Shpilka, Avi Wigderson