We prove the existence of a $poly(n,m)$-time computable pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$. Previously, the best pseudorandom generator for depth-2 circuits had seed length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007). It follows ... more >>>

In this paper we will be concerned with a large class of packing and covering problems which includes Vertex Cover and Independent Set. Typically, for NP-hard problems among them, one can write an LP relaxation and then round the solution. For instance, for Vertex Cover, one can obtain a 2-approximation ... more >>>

We study the power of non-uniform attacks against one-way functions and pseudorandom generators. Fiat and Naor show that for every function $f: [N]\to [N]$ there is an algorithm that inverts $f$ everywhere using (ignoring lower order factors) time, space and advice at most $N^{3/4}$. We show that an algorithm using ... more >>>

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as 2 ... more >>>

We show that every high-entropy distribution is indistinguishable from an efficiently samplable distribution of the same entropy. Specifically, we prove that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$, then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most $S\cdot ... more >>>

A theorem of Green, Tao, and Ziegler can be stated (roughly) as follows: if R is a pseudorandom set, and D is a dense subset of R, then D may be modeled by a set M that is dense in the entire domain such that D and M are indistinguishable. ... more >>>

We study linear programming relaxations of Vertex Cover and Max Cut arising from repeated applications of the ``lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that the integrality gap remains at least $2-\epsilon$ after $\Omega_\epsilon(\log n)$ ... more >>>

We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ ``lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>