{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable). Kopparty ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) {\em many} small weight codewords. ... more >>>

The k-DNF resolution proof systems are a family of systems indexed by the integer k, where the kth member is restricted to operating with formulas in disjunctive normal form with all terms of bounded arity k (k-DNF formulas). This family was introduced in [Krajicek 2001] as an extension of the ... more >>>

For current state-of-the-art satisfiability algorithms based on the DPLL procedure and clause learning, the two main bottlenecks are the amounts of time and memory used. Understanding time and memory consumption, and how they are related to one another, is therefore a question of considerable practical importance. In the field of ... more >>>

We continue the study of {\em robust} tensor codes and expand the class of base codes that can be used as a starting point for the construction of locally testable codes via robust two-wise tensor products. In particular, we show that all unique-neighbor expander codes and all locally correctable codes, ... more >>>

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space. In this paper we resolve the question by answering ... more >>>

We initiate the study of the tradeoff between the {\em length} of a probabilistically checkable proof of proximity (PCPP) and the maximal {\em soundness} that can be guaranteed by a $3$-query verifier with oracle access to the proof. Our main observation is that a verifier limited to querying a short ... more >>>

We give constructions of PCPs of length n*polylog(n) (with respect to circuits of size n) that can be verified by making polylog(n) queries to bits of the proof. These PCPs are not only shorter than previous ones, but also simpler. Our (only) building blocks are Reed-Solomon codes and the bivariate ... more >>>

We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically ... more >>>

We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size $n$): We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ Boolean queries. ... more >>>

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the first ... more >>>

We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any $2$-locally testable code with minimal distance $\delta n$ over a finite field $F$ cannot have more than $|F|^{3/\delta}$ codewords. This result holds even for ... more >>>

We present a simple proof of the bounded-depth Frege lower bounds of Pitassi et. al. and Krajicek et. al. for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudlak and Buss. Our lower bound is conceptually simpler than previous ones, and relies ... more >>>

We present the first example of a natural distribution on instances of an NP-complete problem, with the following properties. With high probability a random formula from this distribution (a) is unsatisfiable, (b) has a short proof that can be found easily, and (c) does not have a short (general) resolution ... more >>>

We study the space complexity of refuting unsatisfiable random $k$-CNFs in the Resolution proof system. We prove that for any large enough $\Delta$, with high probability a random $k$-CNF over $n$ variables and $\Delta n$ clauses requires resolution clause space of $\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$, for any $0<\epsilon<1/2$. For constant $\Delta$, ... 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 present the best known separation between tree-like and general resolution, improving on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}. This is done by constructing a natural family of contradictions, of size $n$, that have $O(n)$-size resolution refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations. This result implies that the most ... 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 >>>

The width of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a ... more >>>