All reports by Author John Hitchcock:

__
TR18-018
| 22nd January 2018
__

John Hitchcock, Adewale Sekoni, Hadi Shafei#### Polynomial-Time Random Oracles and Separating Complexity Classes

__
TR18-013
| 18th January 2018
__

John Hitchcock, Adewale Sekoni#### Nondeterminisic Sublinear Time Has Measure 0 in P

__
TR18-011
| 18th January 2018
__

John Hitchcock, Hadi Shafei#### Nonuniform Reductions and NP-Completeness

__
TR16-012
| 21st January 2016
__

John Hitchcock, Hadi Shafei#### Autoreducibility of NP-Complete Sets

__
TR10-174
| 12th November 2010
__

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek#### A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

__
TR09-071
| 1st September 2009
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Kolmogorov Complexity in Randomness Extraction

__
TR08-022
| 9th January 2008
__

Harry Buhrman, John Hitchcock#### NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

__
TR06-071
| 25th April 2006
__

John Hitchcock, A. Pavan#### Hardness Hypotheses, Derandomization, and Circuit Complexity

__
TR06-039
| 28th February 2006
__

John Hitchcock, A. Pavan#### Comparing Reductions to NP-Complete Sets

__
TR05-161
| 13th December 2005
__

John Hitchcock#### Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR04-079
| 30th August 2004
__

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn#### The Arithmetical Complexity of Dimension and Randomness

__
TR04-072
| 19th August 2004
__

John Hitchcock#### Hausdorff Dimension and Oracle Constructions

__
TR04-029
| 7th April 2004
__

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo#### Scaled dimension and the Kolmogorov complexity of Turing hard sets

__
TR04-025
| 24th January 2004
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Partial Bi-Immunity and NP-Completeness

__
TR03-063
| 2nd July 2003
__

John Hitchcock#### The Size of SPP

John Hitchcock, Adewale Sekoni, Hadi Shafei

Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random

oracle A, with probability 1. We investigate whether this result

extends to individual polynomial-time random oracles. We consider two

notions of random oracles: p-random oracles in the sense of

martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ...
more >>>

John Hitchcock, Adewale Sekoni

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

John Hitchcock, Hadi Shafei

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

John Hitchcock, Hadi Shafei

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity

extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction

more >>>

Harry Buhrman, John Hitchcock

We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| ≥ 2<sup>n<sup>ε</sup></sup> for some ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-ε</sup> queries.

In addition we study the instance ... more >>>

John Hitchcock, A. Pavan

We consider hypotheses about nondeterministic computation that

have been studied in different contexts and shown to have interesting

consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be

distinguished from any DTIME(2^n^epsilon) language by an ...
more >>>

John Hitchcock, A. Pavan

Under the assumption that NP does not have p-measure 0, we

investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive

reductions: there is a problem that is Turing-complete for NP but

not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

John Hitchcock

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>

John Hitchcock

Bennett and Gill (1981) proved that P^A != NP^A relative to a

random oracle A, or in other words, that the set

O_[P=NP] = { A | P^A = NP^A }

has Lebesgue measure 0. In contrast, we show that O_[P=NP] has

Hausdorff dimension 1.

... more >>>

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>John Hitchcock, A. Pavan, N. V. Vinodchandran

The Turing and many-one completeness notions for $\NP$ have been

previously separated under {\em measure}, {\em genericity}, and {\em

bi-immunity} hypotheses on NP. The proofs of all these results rely

on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

John Hitchcock

Derandomization techniques are used to show that at least one of the

following holds regarding the size of the counting complexity class

SPP.

1. SPP has p-measure 0.

2. PH is contained in SPP.

In other words, SPP is small by being a negligible subset of

exponential time or large ...
more >>>