John M. Hitchcock

	2012
64		Xiaoyang Gu, John M. Hitchcock, Aduri Pavan: Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses. Theory Comput. Syst. 51(2): 248-265 (2012)
	2011
63		Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers: Unions of Disjoint NP-Complete Sets. COCOON 2011: 240-251
62		Ryan C. Harkins, John M. Hitchcock: Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. ICALP (1) 2011: 416-423
61		Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi: Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. Computational Complexity 20(2): 329-366 (2011)
60		Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. 209(4): 627-636 (2011)
59		John M. Hitchcock, Aduri Pavan, N. Variyam Vinodchandran: Kolmogorov Complexity in Randomness Extraction. TOCT 3(1): 1 (2011)
58		Ryan C. Harkins, John M. Hitchcock: Dimension, Halfspaces, and the Density of Hard Sets. Theory Comput. Syst. 49(3): 601-614 (2011)
	2010
57		John M. Hitchcock: Lower Bounds for Reducibility to the Kolmogorov Random Strings. CiE 2010: 195-200
56		Xiaoyang Gu, John M. Hitchcock, Aduri Pavan: Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. STACS 2010: 429-440
55		Xiaoyang Gu, John M. Hitchcock, Aduri Pavan: Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses CoRR abs/1001.0117: (2010)
54		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) 17: 174 (2010)
	2009
53		John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran: Kolmogorov Complexity in Randomness Extraction. FSTTCS 2009: 215-226
52		John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran: Kolmogorov Complexity in Randomness Extraction. Electronic Colloquium on Computational Complexity (ECCC) 16: 71 (2009)
	2008
51		Harry Buhrman, John M. Hitchcock: NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. IEEE Conference on Computational Complexity 2008: 1-7
50		John M. Hitchcock, Aduri Pavan: Hardness Hypotheses, Derandomization, and Circuit Complexity. Computational Complexity 17(1): 119-146 (2008)
49		Harry Buhrman, John M. Hitchcock: NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electronic Colloquium on Computational Complexity (ECCC) 15(022): (2008)
48		John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran: Partial Bi-immunity, Scaled Dimension, and NP-Completeness. Theory Comput. Syst. 42(2): 131-142 (2008)
47		John M. Hitchcock, María López-Valdés, Elvira Mayordomo: Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. Theory Comput. Syst. 43(3-4): 471-497 (2008)
	2007
46		Ryan C. Harkins, John M. Hitchcock: Dimension, Halfspaces, and the Density of Hard Sets. COCOON 2007: 129-139
45		Ryan C. Harkins, John M. Hitchcock, Aduri Pavan: Strong Reductions and Isomorphism of Complete Sets. FSTTCS 2007: 168-178
44		John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn: The arithmetical complexity of dimension and randomness. ACM Trans. Comput. Log. 8(2): (2007)
43		John M. Hitchcock, Aduri Pavan: Comparing reductions to NP-complete sets. Inf. Comput. 205(5): 694-706 (2007)
42		John M. Hitchcock: Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. SIAM J. Comput. 36(6): 1696-1708 (2007)
41		Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Effective Strong Dimension in Algorithmic Information and Computational Complexity. SIAM J. Comput. 37(3): 671-705 (2007)
40		Ryan C. Harkins, John M. Hitchcock: Upward separations and weaker hypotheses in resource-bounded measure. Theor. Comput. Sci. 389(1-2): 162-171 (2007)
	2006
39		Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) 2006: 335-345
38		John M. Hitchcock, Aduri Pavan: Comparing Reductions to NP-Complete Sets. ICALP (1) 2006: 465-476
37		John M. Hitchcock: Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. STACS 2006: 408-419
36		John M. Hitchcock, Aduri Pavan: Comparing Reductions to NP-Complete Sets. Electronic Colloquium on Computational Complexity (ECCC) 13(039): (2006)
35		John M. Hitchcock, Aduri Pavan: Hardness Hypotheses, Derandomization, and Circuit Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(071): (2006)
34		John M. Hitchcock, N. V. Vinodchandran: Dimension, entropy rates, and compression. J. Comput. Syst. Sci. 72(4): 760-782 (2006)
33		John M. Hitchcock: Hausdorff dimension and oracle constructions. Theor. Comput. Sci. 355(3): 382-388 (2006)
32		John M. Hitchcock, Jack H. Lutz: Why Computational Complexity Requires Stricter Martingales. Theory Comput. Syst. 39(2): 277-296 (2006)
	2005
31		John M. Hitchcock: Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets CoRR abs/cs/0512053: (2005)
30		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)(105): (2005)
29		John M. Hitchcock: Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets Electronic Colloquium on Computational Complexity (ECCC)(161): (2005)
28		John M. Hitchcock, Aduri Pavan: Resource-bounded strong dimension versus resource-bounded category. Inf. Process. Lett. 95(3): 377-381 (2005)
27		Chris Bourke, John M. Hitchcock, N. V. Vinodchandran: Entropy rates and finite-state dimension. Theor. Comput. Sci. 349(3): 392-406 (2005)
26		John M. Hitchcock: Correspondence Principles for Effective Dimensions. Theory Comput. Syst. 38(5): 559-571 (2005)
	2004
25		John M. Hitchcock, Aduri Pavan: Hardness Hypotheses, Derandomization, and Circuit Complexity. FSTTCS 2004: 336-347
24		John M. Hitchcock: Small Spans in Scaled Dimension. IEEE Conference on Computational Complexity 2004: 104-112
23		John M. Hitchcock, N. V. Vinodchandran: Dimension, Entropy Rates, and Compression. IEEE Conference on Computational Complexity 2004: 174-183
22		John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran: Partial Bi-immunity and NP-Completeness. IEEE Conference on Computational Complexity 2004: 198-203
21		John M. Hitchcock, María López-Valdés, Elvira Mayordomo: Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. MFCS 2004: 476-487
20		Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Effective Strong Dimension in Algorithmic Information and Computational Complexity. STACS 2004: 632-643
19		John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn: The Arithmetical Complexity of Dimension and Randomness CoRR cs.LO/0408043: (2004)
18		John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam: Partial Bi-Immunity and NP-Completeness Electronic Colloquium on Computational Complexity (ECCC)(025): (2004)
17		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)(029): (2004)
16		John M. Hitchcock: Hausdorff Dimension and Oracle Constructions Electronic Colloquium on Computational Complexity (ECCC)(072): (2004)
15		John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn: The Arithmetical Complexity of Dimension and Randomness Electronic Colloquium on Computational Complexity (ECCC)(079): (2004)
14		John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Scaled dimension and nonuniform complexity. J. Comput. Syst. Sci. 69(2): 97-122 (2004)
13		John M. Hitchcock: Small Spans in Scaled Dimension. SIAM J. Comput. 34(1): 170-194 (2004)
12		John M. Hitchcock: The size of SPP. Theor. Comput. Sci. 320(2-3): 495-503 (2004)
	2003
11		John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn: The Arithmetical Complexity of Dimension and Randomness. CSL 2003: 241-254
10		John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Scaled Dimension and Nonuniform Complexity. ICALP 2003: 278-290
9		John M. Hitchcock: Small Spans in Scaled Dimension CoRR cs.CC/0304030: (2003)
8		John M. Hitchcock: The Size of SPP Electronic Colloquium on Computational Complexity (ECCC)(063): (2003)
7		John M. Hitchcock: Gales suffice for constructive dimension. Inf. Process. Lett. 86(1): 9-12 (2003)
6		John M. Hitchcock: Fractal dimension and logarithmic loss unpredictability. Theor. Comput. Sci. 1-3(304): 431-441 (2003)
	2002
5		John M. Hitchcock, Jack H. Lutz: Why Computational Complexity Requires Stricter Martingales. ICALP 2002: 549-560
4		John M. Hitchcock: Correspondence Principles for Effective Dimensions. ICALP 2002: 561-571
3		John M. Hitchcock: Gales Suffice for Constructive Dimension CoRR cs.CC/0208043: (2002)
2		Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Effective Strong Dimension, Algorithmic Information, and Computational Complexity CoRR cs.CC/0211025: (2002)
1		John M. Hitchcock: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theor. Comput. Sci. 289(1): 861-869 (2002)

Coauthor Index

1	Scott Aaronson	[54]
2	Krishna B. Athreya	[2] [20] [41]
3	Baris Aydinlioglu	[54] [61]
4	Chris Bourke	[27]
5	Harry Buhrman	[49] [51] [54]
6	Lance Fortnow	[30] [39] [60]
7	Christian Glaßer (Christian Glasser)	[63]
8	Xiaoyang Gu	[55] [56] [64]
9	Dan Gutfreund (Danny Gutfreund)	[61]
10	Ryan C. Harkins	[40] [45] [46] [58] [62]
11	Akinori Kawachi	[61]
12	María López-Valdés	[17] [21] [47]
13	Jack H. Lutz	[2] [5] [10] [11] [14] [15] [19] [20] [32] [41] [44]
14	Elvira Mayordomo	[2] [10] [14] [17] [20] [21] [41] [47]
15	Dieter van Melkebeek	[54]
16	Aduri Pavan	[18] [22] [25] [28] [30] [35] [36] [38] [39] [43] [45] [48] [50] [52] [53] [55] [56] [59] [60] [63] [64]
17	Sebastiaan Terwijn (Sebastiaan A. Terwijn)	[11] [15] [19] [44]
18	Stephen D. Travers	[63]
19	Pramodchandran N. Variyam	[18]
20	N. V. Vinodchandran (N. Variyam Vinodchandran)	[22] [23] [27] [30] [34] [39] [48] [52] [53] [59] [60]
21	Fengming Wang	[30] [39] [60]

Last update Thu May 31 18:55:10 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page