Quantified derandomization of linear threshold circuits

DOI10.1145/3188745.3188822zbMath1428.68169arXiv1709.07635OpenAlexW2964024530MaRDI QIDQ5230343

Roei Tell

Publication date: 22 August 2019

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

Full work available at URL: https://arxiv.org/abs/1709.07635

zbMATH Keywords

derandomizationcircuit lower boundslinear threshold circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (6)

Quantified Derandomization: How to Find Water in the Ocean ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Unnamed Item ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ On hitting-set generators for polynomials that vanish rarely

This page was built for publication: Quantified derandomization of linear threshold circuits