Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Eric Miles, Emanuele Viola

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous

constructions. In particular, we ...
more >>>

Sergei Lozhkin, Alexander Shiganov

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]

that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most

$$

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

$$

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Emanuele Viola

We draw two incomplete, biased maps of challenges in

computational complexity lower bounds. Our aim is to put

these challenges in perspective, and to present some

connections which do not seem widely known.

Eli Ben-Sasson, Emanuele Viola

We construct a PCP for NTIME(2$^n$) with constant

soundness, $2^n \poly(n)$ proof length, and $\poly(n)$

queries where the verifier's computation is simple: the

queries are a projection of the input randomness, and the

computation on the prover's answers is a 3CNF. The

previous upper bound for these two computations was

more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

Chin Ho Lee, Emanuele Viola

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>

Mateus de Oliveira Oliveira, Pavel Pudlak

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of

computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.

2. MLP circuits are exponentially stronger than monotone span programs.

3. ...
more >>>