The small-set expansion conjecture introduced by Raghavendra and
Steuerer is a natural hardness assumption concerning the problem of
approximating edge expansion of small sets (of size $\delta n$) in
graphs. It was shown to be intimately...
The Stepanov method is an elementary method for proving bounds
on the number of roots of polynomials. At its core is the following
idea. To upper bound the number of roots of a polynomial f(x) in a
field, one sets up an auxiliary polynomial F...
An epsilon-biased set X in {0,1}n is a set so that for every
non-empty set T in [n] the following holds. The random bit B(T)
obtained by selecting at random a vector x in X, and computing the
mod-2 sum of its T-coordinates, has bias at most...
A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko
states that if H is a bipartite graph, then the random
graph with edge density p has in expectation
asymptotically the minimum number of copies of H over all
graphs of the same order and...