Steven Homer

	2011
58		Steven Homer, Alan L. Selman: Computability and Complexity Theory, Second Edition. Springer 2011: I-XVI, 1-298
	2010
57		Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Efficient universal quantum circuits. Quantum Information & Computation 10(1&2): 16-27 (2010)
56		Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet: Non-Uniform Reductions. Theory Comput. Syst. 47(2): 317-341 (2010)
	2009
55		Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Efficient Universal Quantum Circuits. COCOON 2009: 418-428
	2008
54		Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits CoRR abs/0804.2429: (2008)
53		Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer: Universal Quantum Circuits. Electronic Colloquium on Computational Complexity (ECCC) 15(078): (2008)
	2007
52		Debajyoti Bera, Frederic Green, Steven Homer: Small depth quantum circuits. SIGACT News 38(2): 35-50 (2007)
	2006
51		M. Fang, Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang: Quantum lower bounds for fanout. Quantum Information & Computation 6(1): 46-57 (2006)
	2005
50		Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang: Bounds on the Power of Constant-Depth Quantum Circuits. FCT 2005: 44-55
	2003
49		Lance Fortnow, Steven Homer: A Short History of Computational Complexity. Bulletin of the EATCS 80: 95-133 (2003)
	2002
48		Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett: Counting, fanout and the complexity of quantum ACC. Quantum Information & Computation 2(1): 35-65 (2002)
	2001
47		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		Frederic Green, Steven Homer, Chris Pollett: On the Complexity of Quantum ACC. IEEE Conference on Computational Complexity 2000: 250-262
	1999
45		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		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		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		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		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		Judy Goldsmith, Steven Homer: Scalability and the Isomorphism Problem. Inf. Process. Lett. 57(3): 137-143 (1996)
	1995
35		Nader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer: On the Learnability of Zn-DNF Formulas (Extended Abstract). COLT 1995: 198-205
34		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		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		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		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)

Coauthor Index

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

Colors in the list of coauthors

Last update Sat Jun 2 20:57:36 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page