Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates

DOI10.1137/050640941zbMath1124.68037OpenAlexW1999474022MaRDI QIDQ5422492

Emanuele Viola

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

zbMATH Keywords

lower boundderandomizationcommunication complexityaverage-case hardnessconstant-depth circuitswitching lemmasymmetric gatePseudorandom generator

Mathematics Subject Classification ID

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

Pseudorandom generators for combinatorial checkerboards ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Unnamed Item ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ The communication complexity of addition ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Unnamed Item ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item

This page was built for publication: Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates