New algorithms and lower bounds for circuits with linear threshold gates

DOI10.4086/toc.2018.v014a017zbMath1410.68127arXiv1401.2444MaRDI QIDQ4612481

R. Ryan Williams

Publication date: 31 January 2019

Published in: Theory of Computing, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

circuit complexity; linear threshold functions; satisfiability algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Uses Software

• SuLQ