Pseudorandom generators for low sensitivity functions
From MaRDI portal
Publication:4993293
DOI10.4230/LIPICS.ITCS.2018.29zbMATH Open1462.68051MaRDI QIDQ4993293FDOQ4993293
Authors: Pooya Hatami, Avishay Tal 
Publication date: 15 June 2021
Recommendations
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Boolean functions (94D10)
Cites Work
- Hardness vs randomness
- Simple Constructions of Almost k-wise Independent Random Variables
- Analysis of Boolean Functions
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- On the degree of Boolean functions as real polynomials
- On the minimal Fourier degree of symmetric Boolean functions
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Polylogarithmic independence can fool DNF formulas
- Pseudorandom generators for space-bounded computation
- Title not available (Why is that?)
- Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
- Tighter Relations between Sensitivity and Other Complexity Measures
- Title not available (Why is that?)
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
Cited In (2)
This page was built for publication: Pseudorandom generators for low sensitivity functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993293)
