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

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

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)

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

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)