Bootstrapping results for threshold circuits “just beyond” known lower bounds

DOI10.1145/3313276.3316333zbMath1433.68137OpenAlexW2952032520MaRDI QIDQ5212745

Roei Tell, Lijie Chen

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316333

zbMATH Keywords

circuit complexityderandomizationthreshold circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (5)

Quantified Derandomization: How to Find Water in the Ocean ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On hitting-set generators for polynomials that vanish rarely

This page was built for publication: Bootstrapping results for threshold circuits “just beyond” known lower bounds