Pseudorandom Generators for Polynomial Threshold Functions

DOI10.1137/100811623zbMath1272.68132arXiv0910.4122OpenAlexW2568404849MaRDI QIDQ2848221

Raghu Meka, David Zuckerman

Publication date: 25 September 2013

Published in: SIAM Journal on Computing, Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.4122

zbMATH Keywords

polynomialsinvariance principlesthreshold functionspseudorandom generatorsbranching programshalfspaces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Random number generation in numerical analysis (65C10) Functional limit theorems; invariance principles (60F17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Making the Long Code Shorter ⋮ A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy ⋮ Fooling Polytopes ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Amplification and Derandomization without Slowdown ⋮ A Faster FPTAS for #Knapsack ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ Black-Box Reductions in Mechanism Design ⋮ Simple and efficient pseudorandom generators from gaussian processes ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Concentration and Moment Inequalities for Polynomials of Independent Random Variables ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3