On derandomization and average-case complexity of monotone functions

DOI10.1016/J.TCS.2012.02.017zbMATH Open1251.68119OpenAlexW2047406446MaRDI QIDQ428873FDOQ428873

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

Recommendations

• Can every randomized algorithm be derandomized?
• Monotone circuits: one-way functions versus pseudorandom generators
• On the hardness against constant-depth linear-size circuits
• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• Bounds for the average-case complexity of monotone Boolean functions

zbMATH Keywords

randomized algorithmmonotone functionsderandomizationpseudorandom generatorsaverage-case complexitymonotone circuits

Mathematics Subject Classification ID

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

Cites Work

• Computational Complexity
• Hardness vs randomness
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Monotone Boolean functions
• Title not available (Why is that?)
• Learning Boolean formulas
• Simple extractors for all min-entropies and a new pseudorandom generator
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Negation is Powerless for Boolean Slice Functions
• On the Fourier spectrum of monotone functions
• Pseudo-random generators for all hardnesses
• Lower bounds on monotone complexity of the logical permanent
• Optimal bounds for the approximation of Boolean functions and some applications
• The gap between monotone and non-monotone circuit complexity is exponential
• General pseudo-random generators from weaker models of computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hardness amplification within NP
• Space hierarchy results for randomized and other semantic models

Cited In (3)

• Mining circuit lower bound proofs for meta-algorithms
• Bounds for the average-case complexity of monotone Boolean functions
• On the hardness against constant-depth linear-size circuits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428873)