Computability and complexity theory S Homer, AL Selman Springer-Verlag New York Inc, 2011 | 204 | 2011 |
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy S Fenner, F Green, S Homer, R Pruim Arxiv preprint quant-ph/9812056, 1998 | 93 | 1998 |
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy S Fenner, F Green, S Homer, R Pruim Proceedings of the Royal Society of London. Series A: Mathematical, Physical …, 1999 | 86 | 1999 |
Oracle-dependent properties of the lattice of NP sets S Homer, W Maass Theoretical Computer Science 24 (3), 279-289, 1983 | 79 | 1983 |
On reductions of NP sets to sparse sets S Homer, L Longpré Journal of Computer and System Sciences 48 (2), 324-336, 1994 | 69 | 1994 |
Design and performance of parallel and distributed approximation algorithms for maxcut S Homer, M Peinado Journal of Parallel and Distributed Computing 46 (1), 48-61, 1997 | 68 | 1997 |
Oracles for structural properties: The isomorphism problem and public-key cryptography S Homer, AL Selman Journal of Computer and System Sciences 44 (2), 287-301, 1992 | 67 | 1992 |
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy H Buhrman, S Homer Foundations of Software Technology and Theoretical Computer Science, 116-127, 1992 | 60 | 1992 |
Completeness for nondeterministic complexity classes H Buhrman, S Homer, L Torenvliet Theory of Computing Systems 24 (1), 179-200, 1991 | 46 | 1991 |
Quantum lower bounds for fanout M Fang, S Fenner, F Green, S Homer, Y Zhang Arxiv preprint quant-ph/0312208, 2003 | 43 | 2003 |
Finding a hidden code by asking questions Z Chen, C Cunha, S Homer Computing and Combinatorics, 50-55, 1996 | 40 | 1996 |
Bounds on the power of constant-depth quantum circuits S Fenner, F Green, S Homer, Y Zhang Fundamentals of Computation Theory, 44-55, 2005 | 39 | 2005 |
Almost-everywhere complexity hierarchies for nondeterministic time E Allender, R Beigel, U Hertrampf, S Homer Theoretical Computer Science 115 (2), 225-241, 1993 | 37 | 1993 |
Oracles that compute values S Fenner, S Homer, M Ogihara, A Selman SIAM J. Comput. 26 (4), 1043-1065, 1997 | 33 | 1997 |
Experiments with polynomial-time clique approximation algorithms on very large graphs S Homer, M Peinado DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26 …, 1996 | 33 | 1996 |
Complete problems and strong polynomial reducibilities K Ganesan, S Homer SIAM Journal on Computing 21, 733, 1992 | 32 | 1992 |
Structural properties of nondeterministic complete sets S Homer Proceedings Fifth Annual Structure in Complexity Theory Conference, 3-10, 1990 | 31 | 1990 |
On 1-truth-table-hard languages S Homer, S Kurtz, J Royer Theoretical Computer Science 115 (2), 383-389, 1993 | 27 | 1993 |
A Note on 1-Truth-Table Hard Languages S Homer, S Kurtz, J Royer Theoretical Computer Science, to appear, 1993 | 27* | 1993 |
Minimal degrees for polynomial reducibilities S Homer Journal of the ACM (JACM) 34 (2), 480-491, 1987 | 27 | 1987 |