| 2008 |
|---|
| 50 | EE | Debajyoti Bera,
Stephen A. Fenner,
Frederic Green,
Steven Homer:
Universal Quantum Circuits
CoRR abs/0804.2429: (2008) |
| 2007 |
|---|
| 49 | EE | Debajyoti Bera,
Frederic Green,
Steven Homer:
Small depth quantum circuits.
SIGACT News 38(2): 35-50 (2007) |
| 2005 |
|---|
| 48 | EE | Stephen A. Fenner,
Frederic Green,
Steven Homer,
Yong Zhang:
Bounds on the Power of Constant-Depth Quantum Circuits.
FCT 2005: 44-55 |
| 2003 |
|---|
| 47 | | Lance Fortnow,
Steven Homer:
A Short History of Computational Complexity.
Bulletin of the EATCS 80: 95-133 (2003) |
| 2001 |
|---|
| 46 | EE | Stephen A. Fenner,
Steven Homer,
Randall Pruim,
Marcus Schaefer:
Hyper-polynomial hierarchies and the polynomial jump.
Theor. Comput. Sci. 262(1): 241-256 (2001) |
| 2000 |
|---|
| 45 | EE | Frederic Green,
Steven Homer,
Chris Pollett:
On the Complexity of Quantum ACC.
IEEE Conference on Computational Complexity 2000: 250-262 |
| 1999 |
|---|
| 44 | EE | Stephen A. Fenner,
Frederic Green,
Steven Homer,
Alan L. Selman,
Thomas Thierauf,
Heribert Vollmer:
Complements of Multivalued Functions.
Chicago J. Theor. Comput. Sci. 1999: (1999) |
| 43 | EE | Stephen A. Fenner,
Frederic Green,
Steven Homer,
Randall Pruim:
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
Electronic Colloquium on Computational Complexity (ECCC) 6(3): (1999) |
| 1997 |
|---|
| 42 | EE | Stephen A. Fenner,
Steven Homer,
Randall Pruim,
Marcus Schaefer:
Hyper-Polynomial Hierarchies and the NP-Jump.
IEEE Conference on Computational Complexity 1997: 102-110 |
| 41 | | Steven Homer,
Marcus Peinado:
Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut.
J. Parallel Distrib. Comput. 46(1): 48-61 (1997) |
| 40 | | Stephen A. Fenner,
Steven Homer,
Mitsunori Ogihara,
Alan L. Selman:
Oracles that Compute Values.
SIAM J. Comput. 26(4): 1043-1065 (1997) |
| 39 | EE | Zhixiang Chen,
Steven Homer:
Learning Counting Functions with Queries.
Theor. Comput. Sci. 180(1-2): 155-168 (1997) |
| 1996 |
|---|
| 38 | | Zhixiang Chen,
Carlos Cunha,
Steven Homer:
Finding a Hidden Code by Asking Questions.
COCOON 1996: 50-55 |
| 37 | EE | Stephen A. Fenner,
Frederic Green,
Steven Homer,
Alan L. Selman,
Thomas Thierauf,
Heribert Vollmer:
Complements of Multivalued Functions.
IEEE Conference on Computational Complexity 1996: 260-269 |
| 36 | | Zhixiang Chen,
Steven Homer:
The Bounded Injury Priority Method and the Learnability of Unions of Rectangles.
Ann. Pure Appl. Logic 77(2): 143-168 (1996) |
| 35 | EE | Judy Goldsmith,
Steven Homer:
Scalability and the Isomorphism Problem.
Inf. Process. Lett. 57(3): 137-143 (1996) |
| 1995 |
|---|
| 34 | EE | Nader H. Bshouty,
Zhixiang Chen,
Scott E. Decatur,
Steven Homer:
On the Learnability of Zn-DNF Formulas (Extended Abstract).
COLT 1995: 198-205 |
| 33 | EE | Steven Homer,
Marcus Peinado:
A highly parallel algorithm to approximate MaxCut on distributed memory architectures.
IPPS 1995: 113-117 |
| 32 | | Steven Homer,
Sarah Mocas:
Nonuniform Lower Bounds for Exponential Time Classes.
MFCS 1995: 159-168 |
| 1994 |
|---|
| 31 | EE | Zhixiang Chen,
Steven Homer:
On Learning Counting Functions with Queries.
COLT 1994: 218-227 |
| 30 | | Nader H. Bshouty,
Zhixiang Chen,
Steven Homer:
On Learning Discretized Geometric Concepts (Extended Abstract)
FOCS 1994: 54-63 |
| 29 | | Steven Homer,
Jie Wang:
Immunity of Complete Problems
Inf. Comput. 110(1): 119-129 (1994) |
| 28 | | Steven Homer,
Luc Longpré:
On Reductions of NP Sets to Sparse Sets.
J. Comput. Syst. Sci. 48(2): 324-336 (1994) |
| 27 | | Klaus Ambos-Spies,
Steven Homer,
Robert I. Soare:
Minimal Pairs and Complete Problems.
Theor. Comput. Sci. 132(2): 229-241 (1994) |
| 1993 |
|---|
| 26 | | Klaus Ambos-Spies,
Steven Homer,
Uwe Schöning:
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992
Cambridge University Press 1993 |
| 25 | | Stephen A. Fenner,
Steven Homer,
Mitsunori Ogiwara,
Alan L. Selman:
On Using Oracles That Compute Values.
STACS 1993: 398-407 |
| 24 | | Eric Allender,
Richard Beigel,
Ulrich Hertrampf,
Steven Homer:
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.
Theor. Comput. Sci. 115(2): 225-241 (1993) |
| 23 | | Steven Homer,
Stuart A. Kurtz,
James S. Royer:
On A-Truth-Table-Hard Languages.
Theor. Comput. Sci. 115(2): 383-389 (1993) |
| 1992 |
|---|
| 22 | | Harry Buhrman,
Steven Homer:
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy.
FSTTCS 1992: 116-127 |
| 21 | | Steven Homer,
Alan L. Selman:
Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.
J. Comput. Syst. Sci. 44(2): 287-301 (1992) |
| 20 | | K. Ganesan,
Steven Homer:
Complete Problems and Strong Polynomial Reducibilities.
SIAM J. Comput. 21(4): 733-742 (1992) |
| 1991 |
|---|
| 19 | | Steven Homer,
Luc Longpré:
On Reductions of NP Sets to Sparse Sets.
Structure in Complexity Theory Conference 1991: 79-88 |
| 18 | | Harry Buhrman,
Steven Homer,
Leen Torenvliet:
Completeness for Nondeterministic Complexity Classes.
Mathematical Systems Theory 24(3): 179-200 (1991) |
| 1990 |
|---|
| 17 | | Eric Allender,
Richard Beigel,
Ulrich Hertrampf,
Steven Homer:
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.
STACS 1990: 1-11 |
| 16 | | Klaus Ambos-Spies,
Steven Homer,
Robert I. Soare:
Minimal Pairs and Complete Problems.
STACS 1990: 24-36 |
| 15 | | Steven Homer:
Structural Properties of Nondeterministic Complete Sets.
Structure in Complexity Theory Conference 1990: 3-10 |
| 1989 |
|---|
| 14 | | K. Ganesan,
Steven Homer:
Complete Problems and Strong Polynomial Reducibilities.
STACS 1989: 240-250 |
| 13 | | Rodney G. Downey,
Steven Homer,
William I. Gasarch,
Michael Moses:
On Honest Polynomial Reductions, Relativizations, and P=NP.
Structure in Complexity Theory Conference 1989: 196-207 |
| 12 | | Steven Homer,
Alan L. Selman:
Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.
Structure in Complexity Theory Conference 1989: 3-14 |
| 11 | | Steven Homer,
Jie Wang:
Absolute Results Concerning One-Way Functions and Their Applications.
Mathematical Systems Theory 22(1): 21-35 (1989) |
| 1987 |
|---|
| 10 | EE | Steven Homer:
Minimal degrees for polynomial reducibilities.
J. ACM 34(2): 480-491 (1987) |
| 9 | | Steven Homer,
Timothy J. Long:
Honest Polynomial Degrees and P=?NP.
Theor. Comput. Sci. 51: 265-280 (1987) |
| 1986 |
|---|
| 8 | | Steven Homer:
On Simple and Creative Sets in NP.
FSTTCS 1986: 412-425 |
| 7 | | Steven Homer,
John H. Reif:
Arithmetic Theories for Computational Complexity Problems
Information and Control 69(1-3): 1-11 (1986) |
| 6 | | Steven Homer:
On Simple and Creative Sets in NP.
Theor. Comput. Sci. 47(3): 169-180 (1986) |
| 1984 |
|---|
| 5 | | Steven Homer:
Minimal Degrees for Honest Polynomial Reducibilities
FOCS 1984: 300-307 |
| 1983 |
|---|
| 4 | | William I. Gasarch,
Steven Homer:
Relativizations Comparing NP and Exponential Time
Information and Control 58(1-3): 88-100 (1983) |
| 3 | | Steven Homer:
Intermediate beta-R.E. Degrees and the Half-Jump.
J. Symb. Log. 48(3): 790-796 (1983) |
| 2 | | Steven Homer,
Wolfgang Maass:
Oracle-Dependent Properties of the Lattice of NP Sets.
Theor. Comput. Sci. 24: 279-289 (1983) |
| 1982 |
|---|
| 1 | | Jerry Goldman,
Steven Homer:
Quadratic Automata.
J. Comput. Syst. Sci. 24(2): 180-196 (1982) |
