We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).
Kopparty ... more >>>