Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Hadi Shafei:

TR18-018 | 22nd January 2018
John Hitchcock, Adewale Sekoni, Hadi Shafei

Polynomial-Time Random Oracles and Separating Complexity Classes

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 >>>

TR18-011 | 18th January 2018
John Hitchcock, Hadi Shafei

Nonuniform Reductions and NP-Completeness

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 >>>

TR16-012 | 21st January 2016
John Hitchcock, Hadi Shafei

Autoreducibility of NP-Complete Sets

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 >>>

ISSN 1433-8092 | Imprint