28 citations · 79 across the 28 of their papers we have counts for
18 papers · 1 filter
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…
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…
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…
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…
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…
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…
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our a…
On the Structure of Boolean Functions with Small Spectral Norm
Amir Shpilka, Avishay Tal, Ben lee Volk
In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is ). Specifically, we prove the follo…
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
Michael A. Forbes, Amir Shpilka
Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are d…
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
Michael A. Forbes, Amir Shpilka
We study the problem of obtaining deterministic black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. Thi…
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
Michael A. Forbes, Amir Shpilka
We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This clas…
Lower Bounds for Matrix Product
Amir Shpilka
We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two $n \cross n$ matrices over finite fields. In particular we o…