Alexander Razborov, Steven Rudich

We introduce the notion of {\em natural} proof.

We argue that the known proofs of lower bounds on the complexity of explicit

Boolean functions in non-monotone models

fall within our definition of natural.

We show based on a hardness assumption

that natural proofs can't prove superpolynomial lower bounds ...
more >>>

Luca Trevisan

We introduce a new approach to construct extractors -- combinatorial

objects akin to expander graphs that have several applications.

Our approach is based on error correcting codes and on the Nisan-Wigderson

pseudorandom generator. An application of our approach yields a

construction that is simple to ...
more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>

Jan Krajicek

We consider tautologies formed from a pseudo-random

number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}

and in Alekhnovich et.al. \cite{ABRW}.

We explain a strategy of proving their hardness for EF via

a conjecture about bounded arithmetic formulated

in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a

purely finitary statement, in a ...
more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>

Chin Ho Lee, Emanuele Viola

We construct pseudorandom generators with improved seed length for

several classes of tests. First we consider the class of read-once

polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed

length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order

terms. This is optimal up to the factor ...
more >>>

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

Lijie Chen, Ofer Grossman

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>