Locally decodable codes
are error correcting codes with the extra property that, in order
to retrieve the correct value of just one position of the input with
high probability, it is
sufficient to read a small number of
positions of the corresponding,
possibly corrupted ... more >>>

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>>

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