FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
DOI10.1007/B104325zbMATH Open1117.68036OpenAlexW2950473912MaRDI QIDQ5465865FDOQ5465865
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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
- Title not available (Why is that?)
- Upward separations and weaker hypotheses in resource-bounded measure
- Pushdown dimension
- Title not available (Why is that?)
- Non-uniform reductions
- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- Title not available (Why is that?)
- Some new consequences of the hypothesis that P has fixed polynomial-size circuits
- 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)
