Boolean functions are perhaps the most basic objects of study in theoretical computer
science. They also arise in other areas of mathematics, including combinatorics, statistical …

In this paper we show a reduction from the Unique Games problem to the problem of
approximating MAX-CUT to within a factor of GW+ϵ for all ϵ>0; here GW≈.878567 denotes …

In this paper, we study functions with low influences on product probability spaces. The
analysis of Boolean functions f {-1, 1}/sup n//spl rarr/{-1, 1} with low influences has become a …

Common information is ubiquitous in information theory and related areas such as
theoretical computer science and discrete probability. However, because there are multiple …

Given a metric space (X, dX), c≥ 1, r> 0, and p, q≡[0, 1], a distribution over map**s H:
X→ N is called a (r, cr, p, q)-sensitive hash family if any two points in X at distance at most r …

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we
show that a gadget-composed version of F is hard to refute in any proof system whose lines …

This paper ties the line of work on algorithms that find an O (¿(log n))-approximation to the
SPARSEST CUT together with the line of work on algorithms that run in subquadratic time by …

We study the notion of reverse hypercontractivity. We show that reverse hypercontractive
inequalities are implied by standard hypercontractive inequalities as well as by the modified …

Abstract A graph G=(V, E) is called an expander if every vertex subset U of size up to| V|/2
has an external neighborhood whose size is comparable to| U|. Expanders have been a …

We propose a novel approach to concentration for non-independent random variables. The
main idea is to “pretend” that the random variables are independent and pay a multiplicative …