Pseudorandom generators for low sensitivity functions
From MaRDI portal
Publication:4993293
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3829252 (Why is no real title available?)
- scientific article; zbMATH DE number 6789278 (Why is no real title available?)
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Analysis of Boolean Functions
- Hardness vs randomness
- On the degree of Boolean functions as real polynomials
- On the minimal Fourier degree of symmetric Boolean functions
- Polylogarithmic independence can fool DNF formulas
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom generators for space-bounded computation
- Pseudorandomness for regular branching programs via Fourier analysis
- Simple Constructions of Almost k-wise Independent Random Variables
- Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
- Tighter relations between sensitivity and other complexity measures
Cited in
(3)
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)
