Hilbert's thirteenth problem and circuit complexity

DOI10.1007/978-3-642-10631-6_17MaRDI QIDQ3652201zbMATHOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10631-6_17

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• The complexity of word circuits
• The complexity of word circuits
• scientific article; zbMATH DE number 1256716
• Powering requires threshold depth 3
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

Cited in

(3)

• The complexity of word circuits
• Kolmogorov complexity as a language
• The complexity of word circuits

This page was built for publication: Hilbert's thirteenth problem and circuit complexity

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