Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BEN LEE VOLK:
All reports by Author Ben Lee Volk:

TR24-043 | 4th March 2024
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>


TR24-028 | 19th February 2024
Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>


TR23-115 | 8th August 2023
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Determinants vs. Algebraic Branching Programs

Revisions: 1

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>


TR22-169 | 26th November 2022
Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

Extractors for Images of Varieties

Revisions: 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 \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>


TR22-125 | 9th September 2022
Shir Peleg, Amir Shpilka, Ben Lee Volk

Tensor Reconstruction Beyond Constant Rank

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 tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>


TR21-077 | 6th June 2021
Shir Peleg, Amir Shpilka, Ben Lee Volk

Lower Bounds on Stabilizer Rank

The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that $\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_j$. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the ... more >>>


TR20-129 | 5th September 2020
Mrinal Kumar, Ben Lee Volk

A Lower Bound on Determinantal Complexity

The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ ... more >>>


TR20-041 | 29th March 2020
Mrinal Kumar, Ben Lee Volk

A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 2

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>


TR19-170 | 27th November 2019
Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>


TR19-047 | 2nd April 2019
Mrinal Kumar, Ben Lee Volk

Lower Bounds for Matrix Factorization

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 question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of ... more >>>


TR17-124 | 6th August 2017
Mrinal Kumar, Ben Lee Volk

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revisions: 2

We prove a lower bound of $\Omega(n^2/\log^2 n)$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial $f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of $\Omega(n^{4/3}/\log^2 n)$ for the same ... more >>>


TR17-122 | 28th July 2017
Rohit Gurjar, Ben Lee Volk

Pseudorandom Bits for Oblivious Branching Programs

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>


TR17-007 | 19th January 2017
Michael Forbes, Amir Shpilka, Ben Lee Volk

Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

Revisions: 1

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 bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>


TR15-184 | 21st November 2015
Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

Read-$k$ 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 give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ... more >>>


TR14-157 | 27th November 2014
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

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 lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>


TR13-049 | 1st April 2013
Amir Shpilka, Ben Lee Volk, Avishay Tal

On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>




ISSN 1433-8092 | Imprint