Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
DOI10.1137/050640941zbMath1124.68037OpenAlexW1999474022MaRDI QIDQ5422492
Publication date: 22 October 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/050640941
lower boundderandomizationcommunication complexityaverage-case hardnessconstant-depth circuitswitching lemmasymmetric gatePseudorandom generator
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
This page was built for publication: Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates