FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

DOI10.1007/B104325MaRDI QIDQ5465865zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Aduri Pavan

Publication date 12 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b104325

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)

Recommendations

• Hardness hypotheses, derandomization, and circuit complexity
• On pseudorandomness and resource-bounded measure
• Hardness vs randomness
• NP-completeness notions under strong hypotheses
• scientific article; zbMATH DE number 1104167

Cited in

(15)

• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Non-uniform reductions
• Nondeterminisic sublinear time has measure 0 in P
• Hardness assumptions in the foundations of theoretical computer science
• A zero-one law for RP and derandomization of AM if NP is not small
• Upward separations and weaker hypotheses in resource-bounded measure
• Partial bi-immunity, scaled dimension, and NP-completeness
• Some new consequences of the hypothesis that P has fixed polynomial-size circuits
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• scientific article; zbMATH DE number 5044336 (Why is no real title available?)
• Comparing reductions to NP-complete sets
• Hardness hypotheses, derandomization, and circuit complexity
• Pushdown dimension

This page was built for publication: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

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