Hilbert's thirteenth problem and circuit complexity

DOI10.1007/978-3-642-10631-6_17zbMATH Open1211.68200OpenAlexW2107376109MaRDI QIDQ3652201FDOQ3652201

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

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

Mathematics Subject Classification ID

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

Cited In (3)

• Kolmogorov complexity as a language
• The complexity of word circuits
• 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)