John M. Hitchcock

92 papers A* 3A 10B 5C 1Misc 2Journal 64Unranked 7

Year	Rank	Type	Title / Venue / Authors
2025	A	`conf`	Counting Martingales for Measure and Dimension in Complexity Classes. CCC John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025	J	`jnl`	Counting Martingales for Measure and Dimension in Complexity Classes. CoRR John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025	J	`jnl`	Counting Martingales for Measure and Dimension in Complexity Classes. Electron. Colloquium Comput. Complex. John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025	B	`conf`	Random Permutations in Computational Complexity. MFCS John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025	J	`jnl`	Random Permutations in Computational Complexity. CoRR John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025	J	`jnl`	Random Permutations in Computational Complexity. Electron. Colloquium Comput. Complex. John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2022	J	`jnl`	Nonuniform Reductions and NP-Completeness. Theory Comput. Syst. John M. Hitchcock, Hadi Shafei
2021	J	`jnl`	Polynomial-Time Random Oracles and Separating Complexity Classes. ACM Trans. Comput. Theory John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2019	J	`jnl`	Nondeterminisic Sublinear Time Has Measure 0 in P. Theory Comput. Syst. John M. Hitchcock, Adewale Sekoni
2018	J	`jnl`	Autoreducibility of NP-Complete Sets under Strong Hypotheses. Comput. Complex. John M. Hitchcock, Hadi Shafei
2018	J	`jnl`	Nondeterminisic Sublinear Time Has Measure 0 in P. CoRR John M. Hitchcock, Adewale Sekoni
2018	J	`jnl`	Nondeterminisic Sublinear Time Has Measure 0 in P. Electron. Colloquium Comput. Complex. John M. Hitchcock, Adewale Sekoni
2018	A	`conf`	Nonuniform Reductions and NP-Completeness. STACS John M. Hitchcock, Hadi Shafei
2018	J	`jnl`	Nonuniform Reductions and NP-Completeness. CoRR John M. Hitchcock, Hadi Shafei
2018	J	`jnl`	Nonuniform Reductions and NP-Completeness. Electron. Colloquium Comput. Complex. John M. Hitchcock, Hadi Shafei
2018	J	`jnl`	Polynomial-Time Random Oracles and Separating Complexity Classes. CoRR John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2018	J	`jnl`	Polynomial-Time Random Oracles and Separating Complexity Classes. Electron. Colloquium Comput. Complex. John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2016	A	`conf`	Autoreducibility of NP-Complete Sets. STACS John M. Hitchcock, Hadi Shafei
2016	J	`jnl`	Autoreducibility of NP-Complete Sets. CoRR John M. Hitchcock, Hadi Shafei
2016	J	`jnl`	Autoreducibility of NP-Complete Sets. Electron. Colloquium Comput. Complex. John M. Hitchcock, Hadi Shafei
2015	—	`conf`	On the NP-Completeness of the Minimum Circuit Size Problem. FSTTCS John M. Hitchcock, Aduri Pavan
2014	J	`jnl`	Strong Reductions and Isomorphism of Complete Sets. Comput. Ryan C. Harkins, John M. Hitchcock, Aduri Pavan
2014	J	`jnl`	Unions of Disjoint NP-Complete Sets. ACM Trans. Comput. Theory Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
2013	J	`jnl`	Base invariance of feasible dimension. Inf. Process. Lett. John M. Hitchcock, Elvira Mayordomo
2013	J	`jnl`	Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. ACM Trans. Comput. Theory Ryan C. Harkins, John M. Hitchcock
2013	B	`conf`	Learning Reductions to Sparse Sets. MFCS Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
2013	B	`conf`	Length-Increasing Reductions for PSPACE-Completeness. MFCS John M. Hitchcock, Aduri Pavan
2012	J	`jnl`	Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses. Theory Comput. Syst. Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
2012	J	`jnl`	Limitations of Efficient Reducibility to the Kolmogorov Random Strings. Comput. John M. Hitchcock
2011	J	`jnl`	Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. Comput. Complex. Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi
2011	J	`jnl`	Dimension, Halfspaces, and the Density of Hard Sets. Theory Comput. Syst. Ryan C. Harkins, John M. Hitchcock
2011	—	`conf`	Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. ICALP (1) Ryan C. Harkins, John M. Hitchcock
2011	J	`jnl`	Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2011	J	`jnl`	Kolmogorov Complexity in Randomness Extraction. ACM Trans. Comput. Theory John M. Hitchcock, Aduri Pavan, N. Variyam Vinodchandran
2011	Misc	`conf`	Unions of Disjoint NP-Complete Sets. COCOON Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
2010	J	`jnl`	A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek
2010	J	`jnl`	Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses CoRR Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
2010	A	`conf`	Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. STACS Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
2010	C	`conf`	Lower Bounds for Reducibility to the Kolmogorov Random Strings. CiE John M. Hitchcock
2009	—	`conf`	Kolmogorov Complexity in Randomness Extraction. FSTTCS John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
2009	J	`jnl`	Kolmogorov Complexity in Randomness Extraction. Electron. Colloquium Comput. Complex. John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
2008	J	`jnl`	Hardness Hypotheses, Derandomization, and Circuit Complexity. Comput. Complex. John M. Hitchcock, Aduri Pavan
2008	A	`conf`	NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. CCC Harry Buhrman, John M. Hitchcock
2008	J	`jnl`	NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electron. Colloquium Comput. Complex. Harry Buhrman, John M. Hitchcock
2008	J	`jnl`	Partial Bi-immunity, Scaled Dimension, and NP-Completeness. Theory Comput. Syst. John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
2008	J	`jnl`	Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. Theory Comput. Syst. John M. Hitchcock, María López-Valdés, Elvira Mayordomo
2007	J	`jnl`	Comparing reductions to NP-complete sets. Inf. Comput. John M. Hitchcock, Aduri Pavan
2007	Misc	`conf`	Dimension, Halfspaces, and the Density of Hard Sets. COCOON Ryan C. Harkins, John M. Hitchcock
2007	J	`jnl`	Effective Strong Dimension in Algorithmic Information and Computational Complexity. SIAM J. Comput. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo
2007	J	`jnl`	Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. SIAM J. Comput. John M. Hitchcock
2007	—	`conf`	Strong Reductions and Isomorphism of Complete Sets. FSTTCS Ryan C. Harkins, John M. Hitchcock, Aduri Pavan
2007	J	`jnl`	The arithmetical complexity of dimension and randomness. ACM Trans. Comput. Log. John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn
2007	J	`jnl`	Upward separations and weaker hypotheses in resource-bounded measure. Theor. Comput. Sci. Ryan C. Harkins, John M. Hitchcock
2006	—	`conf`	Comparing Reductions to NP-Complete Sets. ICALP (1) John M. Hitchcock, Aduri Pavan
2006	J	`jnl`	Comparing Reductions to NP-Complete Sets. Electron. Colloquium Comput. Complex. John M. Hitchcock, Aduri Pavan
2006	J	`jnl`	Dimension, entropy rates, and compression. J. Comput. Syst. Sci. John M. Hitchcock, N. V. Vinodchandran
2006	—	`conf`	Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2006	J	`jnl`	Hardness Hypotheses, Derandomization, and Circuit Complexity. Electron. Colloquium Comput. Complex. John M. Hitchcock, Aduri Pavan
2006	J	`jnl`	Hausdorff dimension and oracle constructions. Theor. Comput. Sci. John M. Hitchcock
2006	A	`conf`	Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. STACS John M. Hitchcock
2006	J	`jnl`	Why Computational Complexity Requires Stricter Martingales. Theory Comput. Syst. John M. Hitchcock, Jack H. Lutz
2005	J	`jnl`	Correspondence Principles for Effective Dimensions. Theory Comput. Syst. John M. Hitchcock
2005	J	`jnl`	Entropy rates and finite-state dimension. Theor. Comput. Sci. Chris Bourke, John M. Hitchcock, N. V. Vinodchandran
2005	J	`jnl`	Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws Electron. Colloquium Comput. Complex. Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2005	J	`jnl`	Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets CoRR John M. Hitchcock
2005	J	`jnl`	Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets Electron. Colloquium Comput. Complex. John M. Hitchcock
2005	J	`jnl`	Resource-bounded strong dimension versus resource-bounded category. Inf. Process. Lett. John M. Hitchcock, Aduri Pavan
2004	A	`conf`	Dimension, Entropy Rates, and Compression. CCC John M. Hitchcock, N. V. Vinodchandran
2004	A	`conf`	Effective Strong Dimension in Algorithmic Information and Computational Complexity. STACS Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo
2004	—	`conf`	Hardness Hypotheses, Derandomization, and Circuit Complexity. FSTTCS John M. Hitchcock, Aduri Pavan
2004	J	`jnl`	Hausdorff Dimension and Oracle Constructions Electron. Colloquium Comput. Complex. John M. Hitchcock
2004	J	`jnl`	Partial Bi-Immunity and NP-Completeness Electron. Colloquium Comput. Complex. John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam
2004	A	`conf`	Partial Bi-immunity and NP-Completeness. CCC John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
2004	B	`conf`	Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. MFCS John M. Hitchcock, María López-Valdés, Elvira Mayordomo
2004	J	`jnl`	Scaled dimension and nonuniform complexity. J. Comput. Syst. Sci. John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo
2004	J	`jnl`	Scaled dimension and the Kolmogorov complexity of Turing hard sets Electron. Colloquium Comput. Complex. John M. Hitchcock, María López-Valdés, Elvira Mayordomo
2004	A	`conf`	Small Spans in Scaled Dimension. CCC John M. Hitchcock
2004	J	`jnl`	Small Spans in Scaled Dimension. SIAM J. Comput. John M. Hitchcock
2004	J	`jnl`	The Arithmetical Complexity of Dimension and Randomness CoRR John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn
2004	J	`jnl`	The Arithmetical Complexity of Dimension and Randomness Electron. Colloquium Comput. Complex. John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn
2004	J	`jnl`	The size of SPP. Theor. Comput. Sci. John M. Hitchcock
2003	J	`jnl`	Fractal dimension and logarithmic loss unpredictability. Theor. Comput. Sci. John M. Hitchcock
2003	J	`jnl`	Gales suffice for constructive dimension. Inf. Process. Lett. John M. Hitchcock
2003	A*	`conf`	Scaled Dimension and Nonuniform Complexity. ICALP John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo
2003	J	`jnl`	Small Spans in Scaled Dimension CoRR John M. Hitchcock
2003	B	`conf`	The Arithmetical Complexity of Dimension and Randomness. CSL John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn
2003	J	`jnl`	The Size of SPP Electron. Colloquium Comput. Complex. John M. Hitchcock
2002	A*	`conf`	Correspondence Principles for Effective Dimensions. ICALP John M. Hitchcock
2002	J	`jnl`	Effective Strong Dimension, Algorithmic Information, and Computational Complexity CoRR Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo
2002	J	`jnl`	Gales Suffice for Constructive Dimension CoRR John M. Hitchcock
2002	J	`jnl`	MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theor. Comput. Sci. John M. Hitchcock
2002	A*	`conf`	Why Computational Complexity Requires Stricter Martingales. ICALP John M. Hitchcock, Jack H. Lutz