2008 | ||
---|---|---|
52 | EE | Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits CoRR abs/0804.2429: (2008) |
51 | EE | Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits. Electronic Colloquium on Computational Complexity (ECCC) 15(078): (2008) |
2007 | ||
50 | EE | Debajyoti Bera, Frederic Green, Steven Homer: Small depth quantum circuits. SIGACT News 38(2): 35-50 (2007) |
2005 | ||
49 | EE | Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang: Bounds on the Power of Constant-Depth Quantum Circuits. FCT 2005: 44-55 |
2003 | ||
48 | Lance Fortnow, Steven Homer: A Short History of Computational Complexity. Bulletin of the EATCS 80: 95-133 (2003) | |
2001 | ||
47 | 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 | ||
46 | EE | Frederic Green, Steven Homer, Chris Pollett: On the Complexity of Quantum ACC. IEEE Conference on Computational Complexity 2000: 250-262 |
1999 | ||
45 | 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) |
44 | 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 | ||
43 | 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 |
42 | Steven Homer, Marcus Peinado: Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut. J. Parallel Distrib. Comput. 46(1): 48-61 (1997) | |
41 | Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman: Oracles that Compute Values. SIAM J. Comput. 26(4): 1043-1065 (1997) | |
40 | EE | Zhixiang Chen, Steven Homer: Learning Counting Functions with Queries. Theor. Comput. Sci. 180(1-2): 155-168 (1997) |
1996 | ||
39 | Zhixiang Chen, Carlos Cunha, Steven Homer: Finding a Hidden Code by Asking Questions. COCOON 1996: 50-55 | |
38 | 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 |
37 | 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) | |
36 | EE | Judy Goldsmith, Steven Homer: Scalability and the Isomorphism Problem. Inf. Process. Lett. 57(3): 137-143 (1996) |
1995 | ||
35 | EE | Nader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer: On the Learnability of Zn-DNF Formulas (Extended Abstract). COLT 1995: 198-205 |
34 | EE | Steven Homer, Marcus Peinado: A highly parallel algorithm to approximate MaxCut on distributed memory architectures. IPPS 1995: 113-117 |
33 | Steven Homer, Sarah Mocas: Nonuniform Lower Bounds for Exponential Time Classes. MFCS 1995: 159-168 | |
1994 | ||
32 | EE | Zhixiang Chen, Steven Homer: On Learning Counting Functions with Queries. COLT 1994: 218-227 |
31 | Nader H. Bshouty, Zhixiang Chen, Steven Homer: On Learning Discretized Geometric Concepts (Extended Abstract) FOCS 1994: 54-63 | |
30 | Steven Homer, Jie Wang: Immunity of Complete Problems Inf. Comput. 110(1): 119-129 (1994) | |
29 | Steven Homer, Luc Longpré: On Reductions of NP Sets to Sparse Sets. J. Comput. Syst. Sci. 48(2): 324-336 (1994) | |
28 | Klaus Ambos-Spies, Steven Homer, Robert I. Soare: Minimal Pairs and Complete Problems. Theor. Comput. Sci. 132(2): 229-241 (1994) | |
1993 | ||
27 | Klaus Ambos-Spies, Steven Homer, Uwe Schöning: Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992 Cambridge University Press 1993 | |
26 | Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman: On Using Oracles That Compute Values. STACS 1993: 398-407 | |
25 | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993) | |
24 | Steven Homer, Stuart A. Kurtz, James S. Royer: On A-Truth-Table-Hard Languages. Theor. Comput. Sci. 115(2): 383-389 (1993) | |
1992 | ||
23 | Harry Buhrman, Steven Homer: Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS 1992: 116-127 | |
22 | 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) | |
21 | K. Ganesan, Steven Homer: Complete Problems and Strong Polynomial Reducibilities. SIAM J. Comput. 21(4): 733-742 (1992) | |
1991 | ||
20 | Steven Homer, Luc Longpré: On Reductions of NP Sets to Sparse Sets. Structure in Complexity Theory Conference 1991: 79-88 | |
19 | Harry Buhrman, Steven Homer, Leen Torenvliet: Completeness for Nondeterministic Complexity Classes. Mathematical Systems Theory 24(3): 179-200 (1991) | |
1990 | ||
18 | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11 | |
17 | Klaus Ambos-Spies, Steven Homer, Robert I. Soare: Minimal Pairs and Complete Problems. STACS 1990: 24-36 | |
16 | Steven Homer: Structural Properties of Nondeterministic Complete Sets. Structure in Complexity Theory Conference 1990: 3-10 | |
15 | EE | Steven Homer: Setting standards in Europe. Computers & Security 9(4): 295-300 (1990) |
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) |