Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EPSILON-BIASED SETS:
Reports tagged with epsilon-biased sets:
TR05-155 | 10th December 2005
Amir Shpilka

#### Constructions of low-degree and error-correcting epsilon-biased sets

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

TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

#### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

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

ISSN 1433-8092 | Imprint