All reports by Author Valentine Kabanets:

__
TR24-120
| 15th July 2024
__

Halley Goldberg, Valentine Kabanets#### Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

__
TR24-059
| 4th April 2024
__

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

__
TR23-080
| 1st June 2023
__

Halley Goldberg, Valentine Kabanets#### Improved Learning from Kolmogorov Complexity

__
TR23-079
| 31st May 2023
__

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

__
TR22-072
| 15th May 2022
__

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

__
TR22-007
| 14th January 2022
__

Halley Goldberg, Valentine Kabanets#### A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information

__
TR21-095
| 8th July 2021
__

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira#### LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

__
TR20-018
| 18th February 2020
__

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

__
TR19-022
| 23rd February 2019
__

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Revisions: 1

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR18-115
| 11th June 2018
__

Valentine Kabanets, Zhenjian Lu#### Satisfiability and Derandomization for Small Polynomial Threshold Circuits

__
TR18-012
| 20th January 2018
__

Valentine Kabanets, Zhenjian Lu#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR17-026
| 17th February 2017
__

Valentine Kabanets, Daniel Kane, Zhenjian Lu#### A Polynomial Restriction Lemma with Applications

__
TR17-023
| 15th February 2017
__

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

__
TR16-144
| 15th September 2016
__

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky#### Expander Construction in VNC${}^1$

Revisions: 2

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
TR16-008
| 26th January 2016
__

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova#### Algorithms from Natural Lower Bounds

__
TR14-184
| 29th December 2014
__

Ruiwen Chen, Valentine Kabanets#### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

__
TR14-176
| 16th December 2014
__

Eric Allender, Dhiraj Holden, Valentine Kabanets#### The Minimum Oracle Circuit Size Problem

__
TR13-163
| 28th November 2013
__

Russell Impagliazzo, Valentine Kabanets#### Fourier Concentration from Shrinkage

Revisions: 2

__
TR13-150
| 4th November 2013
__

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh#### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR13-024
| 7th February 2013
__

Valentine Kabanets, Antonina Kolokolova#### Compression of Boolean Functions

__
TR12-007
| 28th January 2012
__

Ruiwen Chen, Valentine Kabanets#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

__
TR11-151
| 9th November 2011
__

Valentine Kabanets, Osamu Watanabe#### Is the Valiant-Vazirani Isolation Lemma Improvable?

Revisions: 2

__
TR10-072
| 19th April 2010
__

Russell Impagliazzo, Valentine Kabanets#### Constructive Proofs of Concentration Bounds

__
TR09-090
| 6th October 2009
__

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson#### New Direct-Product Testers and 2-Query PCPs

__
TR08-079
| 31st August 2008
__

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson#### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

__
TR07-125
| 11th October 2007
__

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka#### The black-box query complexity of polynomial summation

__
TR06-154
| 13th December 2006
__

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam#### Uniform Hardness Amplification in NP via Monotone Codes

__
TR05-057
| 19th May 2005
__

Venkatesan Guruswami, Valentine Kabanets#### Hardness amplification via space-efficient direct products

__
TR02-055
| 13th September 2002
__

Valentine Kabanets, Russell Impagliazzo#### Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

__
TR02-008
| 11th January 2002
__

Valentine Kabanets#### Derandomization: A Brief Overview

__
TR00-034
| 5th June 2000
__

Valentine Kabanets, Charles Rackoff, Stephen Cook#### Efficiently Approximable Real-Valued Functions

__
TR99-045
| 16th November 1999
__

Valentine Kabanets, Jin-Yi Cai#### Circuit Minimization Problem

__
TR99-004
| 3rd February 1999
__

Valentine Kabanets#### Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

Halley Goldberg, Valentine Kabanets

A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, ... more >>>

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a ... more >>>

Halley Goldberg, Valentine Kabanets

Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in $\P/\poly$, under the uniform distribution and with membership queries. It is ... 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 >>>

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

Halley Goldberg, Valentine Kabanets

We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in ... more >>>

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the ... more >>>

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Valentine Kabanets, Zhenjian Lu

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

Valentine Kabanets, Zhenjian Lu

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... 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 >>>

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [Annals of Mathematics, 2002], and show that this analysis can be formalized in the bounded-arithmetic system $VNC^1$ (corresponding to the ``$NC^1$ reasoning''). As a corollary, we prove the ... more >>>

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

Ruiwen Chen, Valentine Kabanets

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

Eric Allender, Dhiraj Holden, Valentine Kabanets

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>

Russell Impagliazzo, Valentine Kabanets

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that

\[

\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ...
more >>>

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

Valentine Kabanets, Antonina Kolokolova

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

Ruiwen Chen, Valentine Kabanets

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if

there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,

given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one

to interpolate between complete uniformity (when $\gamma(n)=0$) ...
more >>>

Valentine Kabanets, Osamu Watanabe

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>

Russell Impagliazzo, Valentine Kabanets

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,

our proof does not use the method of higher moments, but rather uses a simple ...
more >>>

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and ...
more >>>

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

The classical Direct-Product Theorem for circuits says

that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard

to compute on average by small circuits, then the corresponding

$k$-wise direct product function

$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each

$x_i\in\{0,1\}^n$) is significantly harder to compute on average by

slightly smaller ...
more >>>

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can

efficiently construct (using \emph{arithmetization}) a low-degree

polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all

points in the Boolean cube $\{0,1\}^n$; the constructed polynomial

$p$ can be interpreted as a polynomial over an arbitrary field

$\mathbb{F}$. The problem ...
more >>>

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

We consider the problem of amplifying uniform average-case hardness

of languages in $\NP$, where hardness is with respect to $\BPP$

algorithms. We introduce the notion of \emph{monotone}

error-correcting codes, and show that hardness amplification for

$\NP$ is essentially equivalent to constructing efficiently

\emph{locally} encodable and \emph{locally} list-decodable monotone

codes. The ...
more >>>

Venkatesan Guruswami, Valentine Kabanets

We prove a version of the derandomized Direct Product Lemma for

deterministic space-bounded algorithms. Suppose a Boolean function

$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$

fraction of inputs by any deterministic time $T$ and space $S$

algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step

walks $w=(v_1,\dots, v_t)$ ...
more >>>

Valentine Kabanets, Russell Impagliazzo

We show that derandomizing Polynomial Identity Testing is,

essentially, equivalent to proving circuit lower bounds for

NEXP. More precisely, we prove that if one can test in polynomial

time (or, even, nondeterministic subexponential time, infinitely

often) whether a given arithmetic circuit over integers computes an

identically zero polynomial, then either ...
more >>>

Valentine Kabanets

This survey focuses on the recent (after 1998) developments in

the area of derandomization, with the emphasis on the derandomization of

time-bounded randomized complexity classes.

Valentine Kabanets, Charles Rackoff, Stephen Cook

We consider a class, denoted APP, of real-valued functions

f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to

within any epsilon>0, by a probabilistic Turing machine running in

time poly(n,1/epsilon). We argue that APP can be viewed as a

generalization of BPP, and show that APP contains a natural

complete ...
more >>>

Valentine Kabanets, Jin-Yi Cai

We study the complexity of the circuit minimization problem:

given the truth table of a Boolean function f and a parameter s, decide

whether f can be realized by a Boolean circuit of size at most s. We argue

why this problem is unlikely to be in P (or ...
more >>>

Valentine Kabanets

Andreev et al.~\cite{ABCR97} give constructions of Boolean

functions (computable by polynomial-size circuits) that require large

read-once branching program (1-b.p.'s): a function in P that requires

1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial

time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a

function in LINSPACE ...
more >>>