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

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 $\dim(X) \geq (1-\eta)N$ ... 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. more >>>

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 of ... 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 $2^{\Omega(\min\{d_1, d_2/s\})}$, where $d_1$ and $d_2$ are the minimal ... 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 general ... 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 >>>