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...
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...
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...
