New algorithms and lower bounds for circuits with linear threshold gates

DOI10.1145/2591796.2591858MaRDI QIDQ6829538zbMATH OpenFDO

Authors Ryan Williams

Publication date 26 June 2015

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

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cited in

(2)

• Efficient construction of rigid matrices using an NP oracle
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

This page was built for publication: New algorithms and lower bounds for circuits with linear threshold gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6829538)