On the hardness against constant-depth linear-size circuits

DOI10.1007/978-3-642-14031-0_4MaRDI QIDQ3578298zbMATHOpenAlexFDO

Authors Chi-Jen Lu, Hsin-Lung Wu

Publication date 20 July 2010

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

Full work available at URL https://doi.org/10.1007/978-3-642-14031-0_4

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• scientific article; zbMATH DE number 1833418
• On derandomization and average-case complexity of monotone functions
• The complexity of constructing pseudorandom generators from hard functions
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates

Cited in

(8)

• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• Lower bounds for constant-depth circuits in the presence of help bits
• On derandomization and average-case complexity of monotone functions
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Linear-size constant-depth polylog-threshold circuits
• Computing and Combinatorics
• On the computational hardness based on linear fpt-reductions
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis

This page was built for publication: On the hardness against constant-depth linear-size circuits

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