On derandomization and average-case complexity of monotone functions

DOI10.1016/J.TCS.2012.02.017zbMath1251.68119OpenAlexW2047406446MaRDI 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 circuitsrandomized algorithmderandomizationpseudorandom generatorsmonotone functionsaverage-case complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

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

This page was built for publication: On derandomization and average-case complexity of monotone functions