Lune

STOC2020Top-tier venue

Fooling Gaussian PTFs via local hyperconcentration

Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan

arXivDOIPublisher
2020Year
6Citations
4Top-tier citations

Abstract

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d O(logd) · logn. All previous generators had a seed length with at least a 2 d dependence on d.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Terminal

Install the CLI
lune papers fulltext f40e5972-c8c4-4444-b8db-1afdde245ccb

Cited by top-tier papers4

Ask how each one uses it

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines