On derandomization and average-case complexity of monotone functions
Publication:428873
DOI10.1016/j.tcs.2012.02.017zbMath1251.68119MaRDI QIDQ428873
Jeff Kinne, George Karakostas, Dieter van Melkebeek
Publication date: 25 June 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.017
monotone circuits; randomized algorithm; derandomization; pseudorandom generators; monotone functions; average-case complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W20: Randomized algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space hierarchy results for randomized and other semantic models
- Lower bounds on monotone complexity of the logical permanent
- Hardness vs randomness
- Optimal bounds for the approximation of Boolean functions and some applications
- The gap between monotone and non-monotone circuit complexity is exponential
- Simple extractors for all min-entropies and a new pseudorandom generator
- General Pseudo-random Generators from Weaker Models of Computation
- Learning Boolean formulas
- On the Fourier spectrum of monotone functions
- Negation is Powerless for Boolean Slice Functions
- Monotone Boolean functions
- Computational Complexity
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Hardness amplification within NP
- Pseudo-random generators for all hardnesses