Pseudorandomness for Regular Branching Programs via Fourier Analysis

DOI10.1007/978-3-642-40328-6_45zbMath1359.68054arXiv1306.3004OpenAlexW2152993492MaRDI QIDQ2851892

Omer Reingold, Thomas Steinke, Salil P. Vadhan

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Unnamed Item ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Bounded Independence Plus Noise Fools Products ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 ⋮ Pseudorandom Functions: Three Decades Later