Zobrazeno 1 - 10
of 41
pro vyhledávání: '"Volk, Ben Lee"'
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 ga
Externí odkaz:
http://arxiv.org/abs/2403.01965
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 characte
Externí odkaz:
http://arxiv.org/abs/2402.11915
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{mos
Externí odkaz:
http://arxiv.org/abs/2308.04599
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$-dim
Externí odkaz:
http://arxiv.org/abs/2211.14497
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 ac
Externí odkaz:
http://arxiv.org/abs/2209.04177
Publikováno v:
Quantum 6, 652 (2022)
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
Externí odkaz:
http://arxiv.org/abs/2106.03214
Autor:
Kumar, Mrinal, Volk, Ben Lee
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 pr
Externí odkaz:
http://arxiv.org/abs/2009.02452
Autor:
Kumar, Mrinal, Volk, Ben Lee
We show that there is a defining equation of degree at most $\mathsf{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 polynomi
Externí odkaz:
http://arxiv.org/abs/2003.12938
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 Stras
Externí odkaz:
http://arxiv.org/abs/1911.11793
Autor:
Kumar, Mrinal, Volk, Ben Lee
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 compu
Externí odkaz:
http://arxiv.org/abs/1904.01182