Explicit functions on {0,1}^n require exact ReLU computation to satisfy w^d = Ω(2^n) for depth d, establishing all-depths separation beyond prior depth-2-vs-3 results.
An Average-Case Depth Hierarchy Theorem for Boolean Circuits , year =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.CC 3years
2026 3verdicts
UNVERDICTED 3representative citing papers
For every Boolean f, bounded-error quantum and classical deterministic communication complexity of f ∘ AND₂ are polynomially related up to polylog n, both characterized by log of De Morgan sparsity of f.
An oracle exists relative to which TAUT has neither optimal proof systems nor recursive jump operators (even with infinite PH), showing Khaniki's question is not relativizably provable.
citing papers explorer
-
Depth Lower Bounds for ReLU Networks with Binary Inputs
Explicit functions on {0,1}^n require exact ReLU computation to satisfy w^d = Ω(2^n) for depth d, establishing all-depths separation beyond prior depth-2-vs-3 results.
-
Quantum-Classical Equivalence for AND-Functions
For every Boolean f, bounded-error quantum and classical deterministic communication complexity of f ∘ AND₂ are polynomially related up to polylog n, both characterized by log of De Morgan sparsity of f.
-
Recursive Jump Operators and Optimal Proof Systems
An oracle exists relative to which TAUT has neither optimal proof systems nor recursive jump operators (even with infinite PH), showing Khaniki's question is not relativizably provable.