All reports by Author Ilya Volkovich:

__
TR24-049
| 7th March 2024
__

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich#### Oblivious Classes Revisited: Lower Bounds and Hierarchies

__
TR24-041
| 1st March 2024
__

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich#### Launching Identity Testing into (Bounded) Space

__
TR23-109
| 21st July 2023
__

Pranav Bisht, Nikhil Gupta, Ilya Volkovich#### Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

__
TR23-079
| 31st May 2023
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

__
TR23-032
| 24th March 2023
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Linear Independence, Alternants and Applications

__
TR22-070
| 8th May 2022
__

Pranav Bisht, Ilya Volkovich#### On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

__
TR21-085
| 21st June 2021
__

Ilya Volkovich#### The Final Nail in the Coffin of Statistically-Secure Obfuscator.

__
TR21-045
| 22nd March 2021
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

__
TR21-009
| 1st February 2021
__

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich#### One-way Functions and Partial MCSP

Revisions: 3
,
Comments: 1

__
TR19-104
| 6th August 2019
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction of Depth-$4$ Multilinear Circuits

__
TR19-040
| 19th February 2019
__

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis#### The Complexity of Finding {$S$}-factors in Regular Graphs

__
TR18-130
| 16th July 2018
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

__
TR18-088
| 24th April 2018
__

Ilya Volkovich#### A story of AM and Unique-SAT

Revisions: 1

__
TR17-023
| 15th February 2017
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### The Power of Natural Properties as Oracles

__
TR16-171
| 3rd November 2016
__

Daniel Minahan, Ilya Volkovich#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

__
TR15-115
| 20th July 2015
__

Ilya Volkovich#### A Guide to Learning Arithmetic Circuits

__
TR15-042
| 30th March 2015
__

Ilya Volkovich#### Computations beyond Exponentiation Gates and Applications

__
TR14-168
| 8th December 2014
__

Ilya Volkovich#### Deterministically Factoring Sparse Polynomials into Multilinear Factors

__
TR14-058
| 20th April 2014
__

Ilya Volkovich#### On Learning, Lower Bounds and (un)Keeping Promises

__
TR11-046
| 2nd April 2011
__

Shubhangi Saraf, Ilya Volkovich#### Black-Box Identity Testing of Depth-4 Multilinear Circuits

__
TR10-188
| 8th December 2010
__

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich#### Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

__
TR10-036
| 8th March 2010
__

Amir Shpilka, Ilya Volkovich#### On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

__
TR10-011
| 22nd January 2010
__

Amir Shpilka, Ilya Volkovich#### Read-Once Polynomial Identity Testing

__
TR09-116
| 15th November 2009
__

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich#### Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

In this work we study oblivious complexity classes. Among our results:

1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.

2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ...
more >>>

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).

First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ...
more >>>

Pranav Bisht, Nikhil Gupta, Ilya Volkovich

An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ...
more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.

If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists ...
more >>>

Pranav Bisht, Ilya Volkovich

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>

Ilya Volkovich

We present an elementary, self-contained proof of the result of Goldwasser and Rothblum [GR07] that the existence of a (perfect) statistically secure obfuscator implies a collapse of the polynomial hierarchy. In fact, we show that an existence of a weaker object implies a somewhat stronger statement. In addition, we extend ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.

The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ...
more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d) \log n}$. Prior to our ... more >>>

Ilya Volkovich

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).

We obtain new circuit lower bounds, as well as some hardness results for the relativized version ...
more >>>

Daniel Minahan, Ilya Volkovich

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the

operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ...
more >>>

Ilya Volkovich

An \emph{arithmetic circuit} is a directed acyclic graph in which the operations are $\{+,\times\}$.

In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems.

In particular, we show that:

\begin{enumerate}

\item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds.

Ilya Volkovich

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.

Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).

In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.

That is, beyond an exponentiation gate. As ...
more >>>

Ilya Volkovich

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.

Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.

We achieve ...
more >>>

Ilya Volkovich

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>>

Shubhangi Saraf, Ilya Volkovich

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic

identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the ... more >>>

Amir Shpilka, Ilya Volkovich

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a

formula (a circuit whose underlying graph is a tree) in which the

operations are $\{+,\times\}$ and such that every input variable

labels at most one leaf. A \emph{preprocessed ROF} (PROF for

short) is a ROF in which we are allowed to ...
more >>>

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

We give the first sub-exponential time deterministic polynomial

identity testing algorithm for depth-$4$ multilinear circuits with

a small top fan-in. More accurately, our algorithm works for

depth-$4$ circuits with a plus gate at the top (also known as

$\Spsp$ circuits) and has a running time of

$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ...
more >>>