28 citations · 79 across the 28 of their papers we have counts for
33 papers
A New Bound on Cofactors of Sparse Polynomials
Ido Nahshon, Amir Shpilka
We prove that for polynomials satisfying and , the -norm of the cofactor is bounded by $\|h\|_2 \leq \|f\|_1 \cdot\lef…
Discreteness of asymptotic tensor ranks
Jop Briët, Matthias Christandl, Itai Leigh +2
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic…
Tensor Reconstruction Beyond Constant Rank
Shir Peleg, Amir Shpilka, Ben Lee Volk
We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tens…
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
Suryajith Chillara, Coral Grichener, Amir Shpilka
We say that two given polynomials , over a ring , are equivalent under shifts if there exists a vector such that . Grigoriev and Karpin…
Robust Sylvester-Gallai type theorem for quadratic polynomials
Shir Peleg, Amir Shpilka
In this work, we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quad…
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions
Roni Con, Amir Shpilka, Itzhak Tamo
In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linea…
Reed Solomon Codes Against Adversarial Insertions and Deletions
Roni Con, Amir Shpilka, Itzhak Tamo
In this work, we study the performance of Reed--Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size there are …
Lower Bounds on Stabilizer Rank
Shir Peleg, Amir Shpilka, Ben Lee Volk
The stabilizer rank of a quantum state is the minimal such that for and stabilizer…
Hitting Sets and Reconstruction for Dense Orbits in and Circuits
Dori Medini, Amir Shpilka
In this paper we study polynomials in (polynomial-sized formulas) and in (polynomial-size depth- circuits) whose orbits, under the action of the affine group…
Polynomial time deterministic identity testingalgorithm for circuits via Edelstein-Kelly type theorem for quadratic polynomials
Shir Peleg, Amir Shpilka
In this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS13] and Gupta [Gup14], by proving an analog of a theorem of Edelstein and Kelly for quadratic polynomials. As…
A generalized Sylvester-Gallai type theorem for quadratic polynomials
Shir Peleg, Amir Shpilka
In this work we prove a version of the Sylvester-Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for t…
Reed-Muller Codes: Theory and Algorithms
Emmanuel Abbe, Amir Shpilka, Min Ye
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and c…
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel
Roni Con, Amir Shpilka
This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel wi…
Sylvester-Gallai type theorems for quadratic polynomials
Amir Shpilka
We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a finite collection , of irreducible polynomials of degree at most …
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
Ori Sberlo, Amir Shpilka
This work proves new results on the ability of binary Reed-Muller codes to decode from random errors and erasures. We obtain these results by proving improved bounds on the weight…
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes, Amir Shpilka
In this paper we study the complexity of constructing a hitting set for the closure of VP, the class of polynomials that can be infinitesimally approximated by polynomials that are…
A learning problem that is independent of the set theory ZFC axioms
Shai Ben-David, Pavel Hrubes, Shay Moran +2
We consider the following statistical estimation problem: given a family F of real valued functions over some domain X and an i.i.d. sample drawn from an unknown distribution P ove…
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bound…
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Michael A. Forbes, Amir Shpilka, Iddo Tzameret +1
We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits c…
Identity Testing and Lower Bounds for Read- Oblivious Algebraic Branching Programs
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi +2
Read- oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we…
Efficiently decoding Reed-Muller codes from random errors
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Reed-Muller codes encode an -variate polynomial of degree by evaluating it on all points in . We denote this code by . The minimal distance of …
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain…
Reed-Muller codes for random erasures and errors
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
This paper studies the parameters for which Reed-Muller (RM) codes over can correct random erasures and random errors with high probability, and in particular when can they…
Testing Equivalence of Polynomials under Shifts
Zeev Dvir, Rafael Oliveira, Amir Shpilka
Two polynomials are called shift-equivalent if there exists a vector such that the polynomial identity…