Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SMALL BIAS SPACES:
Reports tagged with Small bias spaces:
TR09-105 | 27th October 2009
Vikraman Arvind, Srikanth Srinivasan

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Using \epsilon-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an NC^2 algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>


TR09-141 | 19th December 2009
Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

Improved Pseudorandom Generators for Depth 2 Circuits

We prove the existence of a poly(n,m)-time computable
pseudorandom generator which ``1/poly(n,m)-fools'' DNFs with n variables
and m terms, and has seed length O(\log^2 nm \cdot \log\log nm).
Previously, the best pseudorandom generator for depth-2 circuits had seed
length O(\log^3 nm), and was due to Bazzi (FOCS 2007).

It ... more >>>




ISSN 1433-8092 | Imprint