Amir Shpilka

In this work we give two new constructions of $\epsilon$-biased

generators. Our first construction answers an open question of

Dodis and Smith, and our second construction

significantly extends a result of Mossel et al.

In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>