| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Xiaoyang Gu, John M. Hitchcock, Aduri Pavan |
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses.  |
Theory Comput. Syst.  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan, N. Variyam Vinodchandran |
Kolmogorov Complexity in Randomness Extraction. |
TOCT |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov complexity with applications to dimension zero-one laws. |
Inf. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi |
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan C. Harkins, John M. Hitchcock |
Dimension, Halfspaces, and the Density of Hard Sets. |
Theory Comput. Syst. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan C. Harkins, John M. Hitchcock |
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers |
Unions of Disjoint NP-Complete Sets. |
COCOON |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek |
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Xiaoyang Gu, John M. Hitchcock, Aduri Pavan |
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Xiaoyang Gu, John M. Hitchcock, Aduri Pavan |
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. |
STACS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Lower Bounds for Reducibility to the Kolmogorov Random Strings. |
CiE |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
Kolmogorov Complexity in Randomness Extraction. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
Kolmogorov Complexity in Randomness Extraction. |
FSTTCS |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Hardness Hypotheses, Derandomization, and Circuit Complexity. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q30, 68Q17, Subject classification. 68Q15 |
| 1 | John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
Partial Bi-immunity, Scaled Dimension, and NP-Completeness. |
Theory Comput. Syst. |
2008 |
DBLP DOI BibTeX RDF |
Many-one completeness, Bi-immunity, Scaled dimension, Turing completeness |
| 1 | John M. Hitchcock, María López-Valdés, Elvira Mayordomo |
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. |
Theory Comput. Syst. |
2008 |
DBLP DOI BibTeX RDF |
Effective dimension, Scaled dimension, Turing-hard sets, Kolmogorov complexity |
| 1 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
hard sets, polynomial advice, instance complexity |
| 1 | Ryan C. Harkins, John M. Hitchcock |
Upward separations and weaker hypotheses in resource-bounded measure. |
Theor. Comput. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Comparing reductions to NP-complete sets. |
Inf. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn |
The arithmetical complexity of dimension and randomness. |
ACM Trans. Comput. Log. |
2007 |
DBLP DOI BibTeX RDF |
Schnorr randomness, Wadge reductions, computable randomness, Arithmetical hierarchy, constructive dimension |
| 1 | Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
Effective Strong Dimension in Algorithmic Information and Computational Complexity. |
SIAM J. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. |
SIAM J. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan C. Harkins, John M. Hitchcock |
Dimension, Halfspaces, and the Density of Hard Sets. |
COCOON |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan C. Harkins, John M. Hitchcock, Aduri Pavan |
Strong Reductions and Isomorphism of Complete Sets. |
FSTTCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Hardness Hypotheses, Derandomization, and Circuit Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Comparing Reductions to NP-Complete Sets. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Hausdorff dimension and oracle constructions. |
Theor. Comput. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz |
Why Computational Complexity Requires Stricter Martingales. |
Theory Comput. Syst. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, N. V. Vinodchandran |
Dimension, entropy rates, and compression. |
J. Comput. Syst. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. |
ICALP |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Comparing Reductions to NP-Complete Sets. |
ICALP |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. |
STACS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Resource-bounded strong dimension versus resource-bounded category. |
Inf. Process. Lett. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Chris Bourke, John M. Hitchcock, N. V. Vinodchandran |
Entropy rates and finite-state dimension. |
Theor. Comput. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets |
CoRR |
2005 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Correspondence Principles for Effective Dimensions. |
Theory Comput. Syst. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, María López-Valdés, Elvira Mayordomo |
Scaled dimension and the Kolmogorov complexity of Turing hard sets |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn |
The Arithmetical Complexity of Dimension and Randomness |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam |
Partial Bi-Immunity and NP-Completeness |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Hausdorff Dimension and Oracle Constructions |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
The size of SPP. |
Theor. Comput. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn |
The Arithmetical Complexity of Dimension and Randomness |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
Scaled dimension and nonuniform complexity. |
J. Comput. Syst. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Small Spans in Scaled Dimension. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, María López-Valdés, Elvira Mayordomo |
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. |
MFCS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
Effective Strong Dimension in Algorithmic Information and Computational Complexity. |
STACS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
Partial Bi-immunity and NP-Completeness. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, N. V. Vinodchandran |
Dimension, Entropy Rates, and Compression. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Small Spans in Scaled Dimension. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Aduri Pavan |
Hardness Hypotheses, Derandomization, and Circuit Complexity. |
FSTTCS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Gales suffice for constructive dimension. |
Inf. Process. Lett. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
The Size of SPP |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Fractal dimension and logarithmic loss unpredictability. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Small Spans in Scaled Dimension |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
Scaled Dimension and Nonuniform Complexity. |
ICALP |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn |
The Arithmetical Complexity of Dimension and Randomness. |
CSL |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
MAX3SAT is exponentially hard to approximate if NP has positive dimension. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock |
Gales Suffice for Constructive Dimension |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
Effective Strong Dimension, Algorithmic Information, and Computational Complexity |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | John M. Hitchcock |
Correspondence Principles for Effective Dimensions. |
ICALP |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | John M. Hitchcock, Jack H. Lutz |
Why Computational Complexity Requires Stricter Martingales. |
ICALP |
2002 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")