ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS

DOI10.1142/S1793830910000851zbMath1211.68201OpenAlexW1969961332MaRDI QIDQ3084685

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

zbMATH Keywords

parity functionconstant-depth circuitsaverage-case hardness

Mathematics Subject Classification ID

Cites Work

• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• On converting CNF to DNF
• Pseudo-random generators for all hardnesses
• Pseudorandom generators without the XOR lemma

This page was built for publication: ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS