M. Agrawal and O. Watanabe, One-way functions and the isomorphism conjecture, Electronic Colloquium on Computational Complexity, 2009.

K. Ambos-spies and L. Bentzien, Separating NP-Completeness Notions under Strong Hypotheses, Journal of Computer and System Sciences, vol.61, issue.3, pp.335-361, 2000.
DOI : 10.1006/jcss.1999.1674
URL : http://doi.org/10.1006/jcss.1999.1674

A. Amir, R. Beigel, and W. Gasarch, Some connections between bounded query classes and non-uniform complexity, Information and Computation, vol.186, issue.1, pp.104-139, 2003.
DOI : 10.1016/S0890-5401(03)00091-9
URL : http://doi.org/10.1016/s0890-5401(03)00091-9

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pp.307-318, 1993.
DOI : 10.1109/SCT.1991.160263

R. Beigel, Query-limited reducibilities, 1987.
DOI : 10.1016/0168-0072(89)90010-9
URL : http://doi.org/10.1016/0168-0072(89)90010-9

R. Beigel and J. Feigenbaum, On being incoherent without being very hard, Computational Complexity, vol.192, issue.1, pp.1-17, 1992.
DOI : 10.1007/BF01276436
URL : http://1013seopc.eecs.uic.edu/papers/bf-coherent-cc.PS.gz

L. Berman, Polynomial Reducibilities and Complete Sets, 1977.

L. Berman and J. Hartmanis, On Isomorphisms and Density of $NP$ and Other Complete Sets, SIAM Journal on Computing, vol.6, issue.2, pp.305-322, 1977.
DOI : 10.1137/0206023

H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet, Non-uniform reductions. Theory of Computing Systems
DOI : 10.1007/s00224-008-9163-5
URL : http://dx.doi.org/10.1007/s00224-008-9163-5

H. Buhrman and J. M. Hitchcock, NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly, 2008 23rd Annual IEEE Conference on Computational Complexity, pp.1-7, 2008.
DOI : 10.1109/CCC.2008.21

H. Buhrman, S. Homer, and L. Torenvliet, Completeness for nondeterministic complexity classes, Mathematical Systems Theory, vol.54, issue.1, pp.179-200, 1991.
DOI : 10.1007/BF02090397

S. A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing , STOC '71, pp.151-158, 1971.
DOI : 10.1145/800157.805047

J. Feigenbaum, L. Fortnow, S. Laplante, and A. Naik, On coherence, random-self-reducibility, and self-correction, Proceedings of Computational Complexity (Formerly Structure in Complexity Theory), pp.174-191, 1998.
DOI : 10.1109/CCC.1996.507668

J. Feigenbaum, L. Fortnow, C. Lund, and D. Spielman, The power of adaptiveness and additional queries in random-self-reductions, Computational Complexity, vol.39, issue.2, pp.158-174, 1994.
DOI : 10.1007/BF01202287

L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.133-142, 2008.
DOI : 10.1145/1374376.1374398

K. Ganesan and S. Homer, Complete Problems and Strong Polynomial Reducibilities, SIAM Journal on Computing, vol.21, issue.4, pp.733-742, 1992.
DOI : 10.1137/0221044

O. Goldreich, L. Levin, and N. Nisan, On Constructing 1-1 One-Way Functions, 1995.
DOI : 10.1137/0206006

E. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman, P-Selective Sets and Reducing Search to Decision vs Self-Reducibility, Journal of Computer and System Sciences, vol.53, issue.2, pp.194-209, 1996.
DOI : 10.1006/jcss.1996.0061

J. M. Hitchcock and A. Pavan, Comparing reductions to NP-complete sets, Information and Computation, vol.205, issue.5, pp.694-706, 2007.
DOI : 10.1016/j.ic.2006.10.005
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.6266

J. M. Hitchcock, A. Pavan, and N. V. Vinodchandran, Partial Bi-immunity, Scaled Dimension, and NP-Completeness. Theory of Computing Systems
DOI : 10.1007/s00224-007-9000-2
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.4993

R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of IEEE 36th Annual Foundations of Computer Science, pp.538-545, 1995.
DOI : 10.1109/SFCS.1995.492584

R. Impagliazzo and A. Wigderson, requires exponential circuits, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.220-229, 1997.
DOI : 10.1145/258533.258590

R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial time reducibilities, Theoretical Computer Science, vol.1, issue.2, pp.103-123, 1975.
DOI : 10.1016/0304-3975(75)90016-X

L. Levin, Universal sorting problems. Problems of Information Transmission, pp.265-266, 1973.

J. H. Lutz and E. Mayordomo, Measure, Stochasticity, and the Density of Hard Languages, SIAM Journal on Computing, vol.23, issue.4, pp.762-779, 1994.
DOI : 10.1137/S0097539792237498

J. H. Lutz and E. Mayordomo, Cook versus Karp-Levin: Separating completeness notions if NP is not small, Theoretical Computer Science, vol.164, issue.1-2, pp.141-163, 1996.
DOI : 10.1016/0304-3975(95)00189-1
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8184

N. Nisan and A. Wigderson, Hardness vs randomness, Journal of Computer and System Sciences, vol.49, issue.2, pp.149-167, 1994.
DOI : 10.1016/S0022-0000(05)80043-1
URL : http://doi.org/10.1016/s0022-0000(05)80043-1

A. Pavan, Comparison of reductions and completeness notions, pp.27-41, 2003.

A. Pavan and A. Selman, Separation of NP-Completeness Notions, SIAM Journal on Computing, vol.31, issue.3, pp.906-918, 2002.
DOI : 10.1137/S0097539701387039

A. Pavan and A. Selman, Bi-immunity separates strong NP-completeness notions. Information and Computation, pp.116-126, 2004.
DOI : 10.1007/3-540-45841-7_33
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.7423

M. Sudan, L. Trevisan, and S. Vadhan, Pseudorandom generators without the XOR lemma, JCSS: Journal of Computer and System Sciences, vol.62, 2001.

O. Watanabe, A comparison of polynomial time completeness notions, Theoretical Computer Science, vol.54, issue.2-3, pp.249-265, 1987.
DOI : 10.1016/0304-3975(87)90132-0

A. Yao, Theory and application of trapdoor functions, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.80-91, 1982.
DOI : 10.1109/SFCS.1982.45