All reports by Author Antonina Kolokolova:

__
TR16-144
| 15th September 2016
__

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

Revisions: 2

__
TR16-008
| 26th January 2016
__

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

__
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

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

Marco L. 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, 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 >>>