On the hardness against constant-depth linear-size circuits

DOI10.1007/978-3-642-14031-0_4zbMATH Open1286.68203OpenAlexW1998415931MaRDI QIDQ3578298FDOQ3578298

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

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

Mathematics Subject Classification ID

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

Cited In (7)

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

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)