On derandomization and average-case complexity of monotone functions

DOI10.1016/J.TCS.2012.02.017MaRDI QIDQ428873zbMATHOpenAlexFDO

Authors George Karakostas, Jeff Kinne, 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

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)

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

Cites work

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

Cited in

(4)

• 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
• Monotone circuits: one-way functions versus pseudorandom generators

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)