ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
DOI10.1142/S1793830910000851zbMATH Open1211.68201OpenAlexW1969961332MaRDI QIDQ3084685FDOQ3084685
Authors: Chi-Jen Lu, Hsin-Lung Wu 
Publication date: 25 March 2011
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s1793830910000851
Recommendations
- On the hardness against constant-depth linear-size circuits
- scientific article; zbMATH DE number 1833418
- Linear-size constant-depth polylog-threshold circuits
- Lower bounds and separations for constant depth multilinear circuits
- Hardness amplification and the approximate degree of constant-depth circuits
- scientific article; zbMATH DE number 7250153
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- scientific article; zbMATH DE number 3852437
- On complexity of linear operators on the class of circuits of depth 2
- scientific article; zbMATH DE number 1379303
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
Cited In (7)
- On derandomization and average-case complexity of monotone functions
- On the computational hardness based on linear fpt-reductions
- Lower bounds for constant-depth circuits in the presence of help bits
- Linear-size constant-depth polylog-threshold circuits
- Computing and Combinatorics
- On the hardness against constant-depth linear-size circuits
- Title not available (Why is that?)
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 Q3084685)
