research
∙
08/07/2023
New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials
A sparse polynomial (also called a lacunary polynomial) is a polynomial ...
share
research
∙
06/02/2023
Discreteness of asymptotic tensor ranks
Tensor parameters that are amortized or regularized over large tensor po...
research
∙
09/09/2022
Tensor Reconstruction Beyond Constant Rank
We give reconstruction algorithms for subclasses of depth-3 arithmetic c...
research
∙
07/21/2022
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
We say that two given polynomials f, g ∈ R[X], over a ring R, are equiva...
research
∙
02/10/2022
Robust Sylvester-Gallai type theorem for quadratic polynomials
In this work, we extend the robust version of the Sylvester-Gallai theor...
research
∙
01/16/2022
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions
In this work, we study linear error-correcting codes against adversarial...
research
∙
07/12/2021
Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions
In this work, we study linear error-correcting codes against adversarial...
research
∙
06/06/2021
Lower Bounds on Stabilizer Rank
The stabilizer rank of a quantum state ψ is the minimal r such that | ψ⟩...
research
∙
02/10/2021
Hitting Sets and Reconstruction for Dense Orbits in VP_e and ΣΠΣ Circuits
In this paper we study polynomials in VP_e (polynomial-sized formulas) a...
research
∙
06/15/2020
Polynomial time deterministic identity testingalgorithm for Σ^[3]ΠΣΠ^[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials
In this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS1...
research
∙
03/11/2020
A generalized Sylvester-Gallai type theorem for quadratic polynomials
In this work we prove a version of the Sylvester-Gallai theorem for quad...
research
∙
02/09/2020
Reed-Muller Codes: Theory and Algorithms
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most u...
research
∙
09/23/2019
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel
This work gives an explicit construction of a family of error correcting...
research
∙
04/12/2019
Sylvester-Gallai type theorems for quadratic polynomials
We prove Sylvester-Gallai type theorems for quadratic polynomials. Speci...
research
∙
11/29/2018
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
This work proves new results on the ability of binary Reed-Muller codes ...
research
∙
12/28/2017