On the derandomization of constant depth circuits

DOI10.1007/3-540-44666-4_28MaRDI QIDQ4780799zbMATH OpenFDO

Authors Adam R. Klivans

Publication date 21 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2129/21290249

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• scientific article; zbMATH DE number 1559537
• Hardness vs randomness
• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• Pseudorandom bits for constant depth circuits

Cited in

(17)

• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• On derandomizing Yao's weak-to-strong OWF construction
• Outputs in random f-ary recursive circuits
• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• On the hardness against constant-depth linear-size circuits
• Pseudorandom generators for combinatorial checkerboards
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Randomness buys depth for approximate counting
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• A technique for hardness amplification against AC^0
• Majority vs. approximate linear sum and average-case complexity below NC^1
• A technique for hardness amplification against \(\mathsf{AC}^0\)
• Randomness-efficient sampling within NC\(^{1}\)
• Hardness hypotheses, derandomization, and circuit complexity

This page was built for publication: On the derandomization of constant depth circuits

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