On derandomization and average-case complexity of monotone functions

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

zbMATH Keywords

monotone circuits; randomized algorithm; derandomization; pseudorandom generators; monotone functions; average-case complexity

Mathematics Subject Classification ID

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

Mining circuit lower bound proofs for meta-algorithms

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