On the Correlation of Parity and Small-Depth Circuits

DOI10.1137/120897432zbMath1320.68092OpenAlexW2091937735WikidataQ56958749 ScholiaQ56958749MaRDI QIDQ5173252

Johan T. Håstad

Publication date: 9 February 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/945d683a9419a0750f2a938cd82804e6bd556d8d

zbMATH Keywords

paritysmall-depth circuitsswitching lemmacircuits complexity

Mathematics Subject Classification ID

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

Related Items (22)

Expander-based cryptography meets natural proofs ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Unconditionally secure NIZK in the fine-grained setting ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ On polynomial approximations to AC ⋮ Bounded Independence Plus Noise Fools Products ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ Unconditionally secure computation against low-complexity leakage ⋮ Limits of preprocessing ⋮ Correction to: ``Unconditionally secure computation against low-complexity leakage ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Criticality of regular formulas ⋮ Fine-Grained Cryptography ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item

This page was built for publication: On the Correlation of Parity and Small-Depth Circuits