dblp.uni-trier.dewww.uni-trier.de

Steven Homer Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
53EEDebajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Efficient Universal Quantum Circuits. COCOON 2009: 418-428
2008
52EEDebajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits CoRR abs/0804.2429: (2008)
51EEDebajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits. Electronic Colloquium on Computational Complexity (ECCC) 15(078): (2008)
2007
50EEDebajyoti Bera, Frederic Green, Steven Homer: Small depth quantum circuits. SIGACT News 38(2): 35-50 (2007)
2005
49EEStephen 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
47EEStephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer: Hyper-polynomial hierarchies and the polynomial jump. Theor. Comput. Sci. 262(1): 241-256 (2001)
2000
46EEFrederic Green, Steven Homer, Chris Pollett: On the Complexity of Quantum ACC. IEEE Conference on Computational Complexity 2000: 250-262
1999
45EEStephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer: Complements of Multivalued Functions. Chicago J. Theor. Comput. Sci. 1999: (1999)
44EEStephen 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
43EEStephen 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)
40EEZhixiang 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
38EEStephen 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)
36EEJudy Goldsmith, Steven Homer: Scalability and the Isomorphism Problem. Inf. Process. Lett. 57(3): 137-143 (1996)
1995
35EENader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer: On the Learnability of Zn-DNF Formulas (Extended Abstract). COLT 1995: 198-205
34EESteven Homer, Marcus Peinado: A highly parallel algorithm to approximate MaxCut on distributed memory architectures. IPPS 1995: 113-117
33EESteven Homer, Sarah Mocas: Nonuniform Lower Bounds for Exponential Time Classes. MFCS 1995: 159-168
1994
32EEZhixiang 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
26EEStephen 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
23EEHarry 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
18EEEric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11
17EEKlaus 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
15EESteven Homer: Setting standards in Europe. Computers & Security 9(4): 295-300 (1990)
1989
14EEK. 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
10EESteven 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
8EESteven 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)

Coauthor Index

1Eric Allender [18] [25]
2Klaus Ambos-Spies [17] [27] [28]
3Richard Beigel [18] [25]
4Debajyoti Bera [50] [51] [52] [53]
5Nader H. Bshouty [31] [35]
6Harry Buhrman [19] [23]
7Zhixiang Chen [31] [32] [35] [37] [39] [40]
8Carlos Cunha [39]
9Scott E. Decatur [35]
10Rodney G. Downey (Rod Downey) [13]
11Stephen A. Fenner [26] [38] [41] [43] [44] [45] [47] [49] [51] [52] [53]
12Lance Fortnow [48]
13K. Ganesan [14] [21]
14William I. Gasarch [4] [13]
15Jerry Goldman [1]
16Judy Goldsmith [36]
17Frederic Green [38] [44] [45] [46] [49] [50] [51] [52] [53]
18Ulrich Hertrampf [18] [25]
19Stuart A. Kurtz [24]
20Timothy J. Long [9]
21Luc Longpré [20] [29]
22Wolfgang Maass [2]
23Sarah Mocas [33]
24Michael Moses [13]
25Mitsunori Ogihara (Mitsunori Ogiwara) [26] [41]
26Marcus Peinado [34] [42]
27Chris Pollett [46]
28Randall Pruim [43] [44] [47]
29John H. Reif [7]
30James S. Royer [24]
31Marcus Schaefer [43] [47]
32Uwe Schöning [27]
33Alan L. Selman [12] [22] [26] [38] [41] [45]
34Robert I. Soare [17] [28]
35Thomas Thierauf [38] [45]
36Leen Torenvliet [19]
37Heribert Vollmer [38] [45]
38Jie Wang [11] [30]
39Yong Zhang [49]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)