We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good
coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and
$n$ is the number of vertices):

... more >>>