8 citations · 16 across the 15 of their papers we have counts for
21 papers
A Quadratic Lower Bound on Determinantal Complexity
Mrinal Kumar, Ben Lee Volk
We prove an lower bound on the determinantal complexity of the power sum polynomial over the field of complex numbers. A similar result was claimed in…
Improved Algorithms for the Remote Point Problem
Ben Lee Volk
The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace of dimension , to deterministically find a vector $v \in \…
A Lower Bound for Read-Once Parity Branching Programs
Ben Lee Volk
We prove an lower bound for read-once parity branching programs computing an explicit boolean function on variables. The previous best lower bound was $\tildeΩ(n…
On Deterministically Finding an Element of High Order Modulo a Composite
Ziv Oznovich, Ben Lee Volk
We give a deterministic algorithm that, given a composite number and a target order , runs in time and finds either an element $a \in \mathbb{Z}_N…
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi +1
We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial computed by a constant-depth circuit over rational numbers, and outputs a…
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
Ashish Dwivedi, Zeyu Guo, Ben Lee Volk
We construct explicit pseudorandom generators that fool -variate polynomials of degree at most over a finite field . The seed length of our generators is $O(d…
Recursive Error Reduction for Regular Branching Programs
Eshan Chattopadhyay, Jyun-Jie Liao
In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Thei…
Determinants vs. Algebraic Branching Programs
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
We show that for every homogeneous polynomial of degree , if it has determinantal complexity at most , then it can be computed by a homogeneous algebraic branching program (A…
Extractors for Images of Varieties
Zeyu Guo, Ben Lee Volk, Akhil Jalan +1
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \m…
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…
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…
A Lower Bound on Determinantal Complexity
Mrinal Kumar, Ben Lee Volk
The determinantal complexity of a polynomial over a field is the dimension of the smallest matrix whose entries are affine fun…
A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits
Mrinal Kumar, Ben Lee Volk
We show that there is a defining equation of degree at most for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large…
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
Prerona Chatterjee, Mrinal Kumar, Adrian She +1
We show that any Algebraic Branching Program (ABP) computing the polynomial has at least vertices. This improves upon the lower bound of $Ω(n\log n)…
Lower Bounds for Matrix Factorization
Mrinal Kumar, Ben Lee Volk
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical ques…
Pseudorandom Bits for Oblivious Branching Programs
Rohit Gurjar, Ben Lee Volk
We construct a pseudorandom generator which fools read- oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequen…
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…
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…
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…