Mathematical Foundations of Computer Science 2004
From MaRDI portal
Publication:5311109
DOI10.1007/b99679zbMath1096.68062OpenAlexW2488008928MaRDI QIDQ5311109
Peter Bro Miltersen, Kristoffer Arnsfelt Hansen
Publication date: 22 August 2005
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/b99679
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item ⋮ On the correlation between parity and modular polynomials ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression