“Satisfiability (SAT) related topics have attracted researchers from various disciplines: logic,
applied areas such as planning, scheduling, operations research and combinatorial …

But, perhaps, we should start with a few words about graphs in general. They are, of course,
one of the prime objects of study in Discrete Mathematics. However, graphs are among the …

Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …

We solve a 20-year old problem posed by Yannakakis and prove that there exists no
polynomial-size linear program (LP) whose associated polytope projects to the traveling …

We show that for kges3 even the Omega (n) level of the Lasserre hierarchy cannot disprove
a random k-CSP instance over any predicate type implied by k-XOR constraints, for example …

We study the problem of agnostically learning halfspaces which is defined by a fixed but
unknown distribution D on Q^ n X {-1, 1}. We define Err_H (D) as the least error of a …

Let P:{0, 1} k→{0, 1} be a nontrivial k-ary predicate. Consider a random instance of the
constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied …

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size
linear program (LP) exists whose associated polytope projects to the traveling salesman …

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the
hierarchy of SDPs defined by Lasserre. Schoenebeck [23] recently showed the first …

Using the recently developed framework of Daniely, Linial and Shalev-Shwartz, we show
that under a natural assumption on the complexity of random K-SAT, learning DNF formulas …