Fetching the paper…

Reading the bibliography…

2009

Pseudorandom Generators for Polynomial Threshold Functions

Meka, Raghu, Zuckerman, David

Original
PDF
Post on X

Understand

We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs).

We give a PRG with seed-length log n/eps^{O(d)} fooling degree d PTFs with error at most eps.
Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error eps.
For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter eps and obtain a PRG with seed-length O(log n + log^2(1/eps)).

Pseudorandom Generators for Polynomial Threshold Functions · Around

Built on

Threshold Logic
1967
Earlier work this paper cites.
An Introduction to Probability Theory and Its Applications, Vol. 2 (Volume 2)
1971
Earlier work this paper cites.
Universal classes of hash functions (extended abstract)
1977
Earlier work this paper cites.
Probability in Banach spaces: isoperimetry and processes
1991
Earlier work this paper cites.
Pseudorandom generators for space-bounded computation
1992
Earlier work this paper cites.
The polynomial method in circuit complexity
1993
Earlier work this paper cites.
Small-bias probability spaces: Efficient constructions and applications
1993
Earlier work this paper cites.
On the size of weights for threshold gates
1994
Earlier work this paper cites.

Similar

How fast can a threshold gate learn?
1994
Cited alongside, same era.
Randomness is linear in space
1996
Cited alongside, same era.
Algorithmic derandomization via complexity theory
Original
2002
Cited alongside, same era.
Derandomized squaring of graphs
2005
Cited alongside, same era.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
2006
Cited alongside, same era.
Every linear threshold function has a low-weight approximator
2006
Cited alongside, same era.
Sharpening of the upper bound of the absolute constant in the Berry–Esséen inequality

Then

Polynomial threshold functions: Structure, approximation and pseudorandomness , 2009
Original
2009
Closest in time.
Finding duplicates in a data stream
2009
Closest in time.
Bounding the sensitivity of polynomial threshold functions , 2009
Original
2009
Closest in time.
Explicit dimension reduction and its applications
2009
Closest in time.
Explicit construction of a small epsilon-net for linear threshold functions
2009
Closest in time.
Bounded independence fools degree-2 threshold functions
2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2007

Cited alongside, same era.

The Chow parameters problem

2008

Cited alongside, same era.

The expressive power of voting polynomials

Cited in the paper.

Quantum lower bounds by polynomials

Cited in the paper.

Distributional and l q l^{q} norm inequalities for polynomials over convex bodies in ℝ n \mathbb{R}^{n}

Cited in the paper.

Bounded independence fools halfspaces

Cited in the paper.

Polynomial-time approximation schemes for knapsack and related counting problems using branching programs , 2010

2010

Closest in time.

An invariance principle for polytopes

——— · 2010

Closest in time.