A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordström 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.
The aim of this note is to present a simplified version of his proof.

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X
\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and ... more >>>

A two server private information retrieval (PIR) scheme
allows a user U to retrieve the i-th bit of an
n-bit string x replicated between two servers while each
server individually learns no information about i. The main
parameter of interest in a PIR scheme is its communication
complexity, namely the ... more >>>

We show that every resolution proof of the {\em functional} version
$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split
between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log
m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number
of pigeons $m$ is arbitrary.

Recently, Raz established exponential lower bounds on the size
of resolution proofs of the weak pigeonhole principle. We give another
proof of this result which leads to better numerical bounds. Specifically,
we show that every resolution proof of $PHP^m_n$ must have size
$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an
$\exp\of{\Omega(n^{1/3})}$ bound when ... more >>>

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em
hard} for a propositional proof system $P$ if $P$ can not efficiently
prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for
{\em any} string $b\in\{0,1\}^m$. We consider a variety of
``combinatorial'' pseudorandom generators inspired by the
Nisan-Wigderson generator on the one hand, and ... more >>>

We study space complexity in the framework of
propositional proofs. We consider a natural model analogous to
Turing machines with a read-only input tape, and such
popular propositional proof systems as Resolution, Polynomial
Calculus and Frege systems. We propose two different space measures,
corresponding to the maximal number of bits, ... more >>>

Assume that A, B are finite families of n-element sets.
We prove that there is an element that simultaneously
belongs to at least |A|/2n sets
in A and to at least |B|/2n sets in B. We use this result to prove
that for any inconsistent DNF's F,G with OR ... more >>>

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
... more >>>

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

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets
representable in a theory $T$ of Bounded Arithmetic in the sense that
$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$
we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the
class of disjoint ... more >>>