Amir Shpilka

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 70

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

IEEE Trans. Inf. Theory

STOC

Publications

Roni Con, Amir Shpilka, Itzhak Tamo
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions. IEEE Trans. Inf. Theory 70 (7) (2024)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Lower Bounds for Set-Multilinear Branching Programs. CCC (2024)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Tensor Reconstruction Beyond Constant Rank. ITCS (2024)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
Discreteness of Asymptotic Tensor Ranks (Extended Abstract). ITCS (2024)
Ido Nahshon, Amir Shpilka
New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials. ISSAC (2024)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Lower Bounds for Set-Multilinear Branching Programs. CoRR (2023)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Exponential Lower Bounds Against Sums of ROABPs. Electron. Colloquium Comput. Complex. (2023)
Ido Nahshon, Amir Shpilka
New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials. CoRR (2023)
Roni Con, Amir Shpilka, Itzhak Tamo
Reed Solomon Codes Against Adversarial Insertions and Deletions. IEEE Trans. Inf. Theory 69 (5) (2023)
Roni Con, Amir Shpilka, Itzhak Tamo
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions. CoRR (2023)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
Discreteness of asymptotic tensor ranks. CoRR (2023)
Emmanuel Abbe, Ori Sberlo, Amir Shpilka, Min Ye
Reed-Muller Codes. Found. Trends Commun. Inf. Theory 20 (1-2) (2023)
Suryajith Chillara, Coral Grichener, Amir Shpilka
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. STACS (2023)
Yuval Rabani, Amir Shpilka
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 51 (5) (2022)
Suryajith Chillara, Coral Grichener, Amir Shpilka
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. Electron. Colloquium Comput. Complex. (2022)
Shir Peleg, Amir Shpilka
Robust Sylvester-Gallai type theorem for quadratic polynomials. CoRR (2022)
Roni Con, Amir Shpilka, Itzhak Tamo
Reed Solomon Codes Against Adversarial Insertions and Deletions. ISIT (2022)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Tensor Reconstruction Beyond Constant Rank. Electron. Colloquium Comput. Complex. (2022)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Tensor Reconstruction Beyond Constant Rank. CoRR (2022)
Shir Peleg, Amir Shpilka
Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. SoCG (2022)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Lower Bounds on Stabilizer Rank. Quantum 6 (2022)
Roni Con, Amir Shpilka, Itzhak Tamo
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions. IEEE Trans. Inf. Theory 68 (10) (2022)
Roni Con, Amir Shpilka
Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel. IEEE Trans. Inf. Theory 68 (5) (2022)
Shir Peleg, Ben Lee Volk, Amir Shpilka
Lower Bounds on Stabilizer Rank. ITCS (2022)
Suryajith Chillara, Coral Grichener, Amir Shpilka
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. CoRR (2022)
Roni Con, Amir Shpilka, Itzhak Tamo
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions. CoRR (2022)
Dori Medini, Amir Shpilka
Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be independent of set theory (invited paper). STOC (2021)
Emmanuel Abbe, Amir Shpilka, Min Ye
Reed-Muller Codes: Theory and Algorithms. IEEE Trans. Inf. Theory 67 (6) (2021)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. 17 (2021)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Lower Bounds on Stabilizer Rank. CoRR (2021)
Dori Medini, Amir Shpilka
and ΣΠΣ Circuits. CoRR (2021)
Dori Medini, Amir Shpilka
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. Computational Complexity Conference (2021)
Shir Peleg, Amir Shpilka
circuits via Edelstein-Kelly type theorem for quadratic polynomials. STOC (2021)
Shir Peleg, Amir Shpilka, Ben Lee Volk
Lower Bounds on Stabilizer Rank. Electron. Colloquium Comput. Complex. 28 (2021)
Roni Con, Amir Shpilka, Itzhak Tamo
Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions. CoRR (2021)
Amir Shpilka
On Some Recent Advances in Algebraic Complexity (Invited Talk). FSTTCS (2020)
Roni Con, Amir Shpilka
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel. ISIT (2020)
Emmanuel Abbe, Amir Shpilka, Min Ye
Reed-Muller Codes: Theory and Algorithms. CoRR (2020)
Shir Peleg, Amir Shpilka
A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. Computational Complexity Conference (2020)
Shir Peleg, Amir Shpilka
A generalized Sylvester-Gallai type theorem for quadratic polynomials. CoRR (2020)
Ori Sberlo, Amir Shpilka
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. SODA (2020)
Shir Peleg, Amir Shpilka
circuits via Edelstein-Kelly type theorem for quadratic polynomials. CoRR (2020)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Comput. Complex. 28 (1) (2019)
Roni Con, Amir Shpilka
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel. CoRR (2019)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be undecidable. Nat. Mach. Intell. 1 (1) (2019)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Author Correction: Learnability can be undecidable. Nat. Mach. Intell. 1 (2) (2019)
Amir Shpilka
Sylvester-Gallai type theorems for quadratic polynomials. CoRR (2019)
Amir Shpilka
Sylvester-Gallai type theorems for quadratic polynomials. STOC (2019)
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory Comput. 14 (1) (2018)
Michael A. Forbes, Amir Shpilka
A PSPACE construction of a hitting set for the closure of small algebraic circuits. STOC (2018)
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Oblivious Algebraic Branching Programs. ACM Trans. Comput. Theory 10 (1) (2018)
Ori Sberlo, Amir Shpilka
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. CoRR (2018)
Gil Cohen, Amir Shpilka, Avishay Tal
On the degree of univariate polynomials over the integers. Comb. 37 (3) (2017)
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Efficiently Decoding Reed-Muller Codes From Random Errors. IEEE Trans. Inf. Theory 63 (4) (2017)
Amir Shpilka, Avishay Tal, Ben lee Volk
On the Structure of Boolean Functions with Small Spectral Norm. Comput. Complex. 26 (1) (2017)
Michael A. Forbes, Amir Shpilka
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. CoRR (2017)
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
Succinct hitting sets and barriers to proving algebraic circuits lower bounds. STOC (2017)
Michael A. Forbes, Amir Shpilka
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. Electron. Colloquium Comput. Complex. 24 (2017)
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. CoRR (2017)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
A learning problem that is independent of the set theory ZFC axioms. CoRR (2017)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Computational Complexity Conference (2016)
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. Computational Complexity Conference (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR (2016)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct Sum Fails for Zero-Error Average Communication. Algorithmica 76 (3) (2016)
Rafael Mendes de Oliveira, Amir Shpilka, Ben lee Volk
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Comput. Complex. 25 (2) (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
Tight lower bounds for linear 2-query LCCs over finite fields. Comb. 36 (1) (2016)
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Efficiently decoding Reed-Muller codes from random errors. STOC (2016)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. CoRR (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. Electron. Colloquium Comput. Complex. 22 (2015)
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Decoding high rate Reed-Muller codes from random errors in near linear time. CoRR (2015)
Amir Shpilka, Ilya Volkovich
Read-once polynomial identity testing. Comput. Complex. 24 (3) (2015)
Michael A. Forbes, Amir Shpilka
Complexity Theory Column 88: Challenges in Polynomial Factorization1. SIGACT News 46 (4) (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Compressing and Teaching for Low VC-Dimension. FOCS (2015)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller Codes for Random Erasures and Errors. IEEE Trans. Inf. Theory 61 (10) (2015)
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs. CoRR (2015)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller Codes for Random Erasures and Errors. STOC (2015)
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Oblivious Algebraic Branching Programs. Electron. Colloquium Comput. Complex. 22 (2015)
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Computational Complexity Conference (2015)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Polynomial Factorization. Comput. Complex. 24 (2) (2015)
Amir Shpilka
Capacity-Achieving Multiwrite WOM Codes. IEEE Trans. Inf. Theory 60 (3) (2014)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Computational Complexity Conference (2014)
Amir Shpilka, Avishay Tal, Ben lee Volk
On the structure of boolean functions with small spectral norm. ITCS (2014)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller codes for random erasures and errors. CoRR (2014)
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. CoRR (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound. ICALP (1) (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Electron. Colloquium Comput. Complex. 21 (2014)
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka
Testing Equivalence of Polynomials under Shifts. ICALP (1) (2014)
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka
Testing Equivalence of Polynomials under Shifts. CoRR (2014)
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka
Testing Equivalence of Polynomials under Shifts. Electron. Colloquium Comput. Complex. 21 (2014)
Eitan Yaakobi, Amir Shpilka
High Sum-Rate Three-Write and Nonbinary WOM Codes. IEEE Trans. Inf. Theory 60 (11) (2014)
Amir Shpilka, Ilya Volkovich
On Reconstruction and Testing of Read-Once Formulas. Theory Comput. 10 (2014)
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
Hitting sets for multilinear read-once algebraic branching programs, in any order. STOC (2014)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Electron. Colloquium Comput. Complex. 21 (2014)
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Electron. Colloquium Comput. Complex. 21 (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct sum fails for zero error average communication. ITCS (2014)
Amir Shpilka, Avishay Tal
On the minimal fourier degree of symmetric Boolean functions. Comb. 34 (3) (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct Sum Fails for Zero Error Average Communication. Electron. Colloquium Comput. Complex. 20 (2013)

Amir Shpilka.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Amir Shpilka