The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>>

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>