All reports by Author Ben Lee Volk:

__
TR20-129
| 5th September 2020
__

Mrinal Kumar, Ben Lee Volk#### A Lower Bound on Determinantal Complexity

__
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

__
TR19-170
| 27th November 2019
__

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk#### A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

__
TR17-124
| 6th August 2017
__

Mrinal Kumar, Ben Lee Volk#### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revisions: 2

__
TR17-122
| 28th July 2017
__

Rohit Gurjar, Ben Lee Volk#### Pseudorandom Bits for Oblivious Branching Programs

__
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

__
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

__
TR14-157
| 27th November 2014
__

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk#### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

__
TR13-049
| 1st April 2013
__

Amir Shpilka, Ben Lee Volk, Avishay Tal#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

Mrinal Kumar, Ben Lee Volk

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 >>>

Mrinal Kumar, Ben Lee Volk

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 >>>

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

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 >>>

Mrinal Kumar, Ben Lee Volk

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 >>>

Rohit Gurjar, Ben Lee Volk

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 >>>

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

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

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 >>>

Rafael Mendes de 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 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 >>>

Amir Shpilka, Ben Lee Volk, Avishay Tal

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 >>>