Steve Homer
Steve Homer
Professor, CS, Boston University
Verified email at cs.bu.edu
TitleCited byYear
Computability and complexity theory
S Homer, AL Selman
Springer-Verlag New York Inc, 2011
1602011
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
901998
Oracle-dependent properties of the lattice of NP sets
S Homer, W Maass
Theoretical Computer Science 24 (3), 279-289, 1983
761983
On reductions of NP sets to sparse sets
S Homer, L Longpré
Journal of Computer and System Sciences 48 (2), 324-336, 1994
651994
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
651992
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
621997
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
541999
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
501996
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
501996
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy
H Buhrman, S Homer
Foundations of Software Technology and Theoretical Computer Science, 116-127, 1992
441992
Completeness for nondeterministic complexity classes
H Buhrman, S Homer, L Torenvliet
Theory of Computing Systems 24 (1), 179-200, 1991
401991
Complete problems and strong polynomial reducibilities
K Ganesan, S Homer
SIAM Journal on Computing 21, 733, 1992
341992
Finding a hidden code by asking questions
Z Chen, C Cunha, S Homer
Computing and Combinatorics, 50-55, 1996
331996
Almost-everywhere complexity hierarchies for nondeterministic time
E Allender, R Beigel, U Hertrampf, S Homer
Theoretical Computer Science 115 (2), 225-241, 1993
321993
Bounds on the power of constant-depth quantum circuits
S Fenner, F Green, S Homer, Y Zhang
Fundamentals of Computation Theory, 44-55, 2005
312005
Minimal degrees for polynomial reducibilities
S Homer
Journal of the ACM (JACM) 34 (2), 480-491, 1987
311987
Quantum lower bounds for fanout
M Fang, S Fenner, F Green, S Homer, Y Zhang
Arxiv preprint quant-ph/0312208, 2003
292003
Oracles that compute values
S Fenner, S Homer, M Ogihara, A Selman
SIAM J. Comput. 26 (4), 1043-1065, 1997
291997
Structural properties of nondeterministic complete sets
S Homer
Proceedings Fifth Annual Structure in Complexity Theory Conference, 3-10, 1990
271990
On 1-truth-table-hard languages
S Homer, S Kurtz, J Royer
Theoretical Computer Science 115 (2), 383-389, 1993
261993
The system can't perform the operation now. Try again later.
Articles 1–20