default search action
Steven Homer
Person information
- affiliation: Boston University, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2011
- [b2]Steven Homer, Alan L. Selman:
Computability and Complexity Theory, Second Edition. Texts in Computer Science, Springer 2011, ISBN 978-1-4614-0681-5, pp. I-XVI, 1-298 - 2001
- [b1]Steven Homer, Alan L. Selman:
Computability and Complexity Theory. Texts in Computer Science, Springer 2001, ISBN 978-1-4419-2865-8, pp. i-xiii, 1-195
Journal Articles
- 2020
- [j35]Tim Jackman, Steve Homer:
Review of Kernelization: Theory of Parameterized Preprocessing by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. SIGACT News 51(4): 11-14 (2020) - 2018
- [j34]Stephen A. Fenner, Frederic Green, Steven Homer:
Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems. SIGACT News 49(3): 35-47 (2018) - 2017
- [j33]Steve Homer:
Review of Crypto School by Joachim von zur Gathen. SIGACT News 48(3): 10-13 (2017) - 2010
- [j32]Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet:
Non-Uniform Reductions. Theory Comput. Syst. 47(2): 317-341 (2010) - [j31]Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Efficient universal quantum circuits. Quantum Inf. Comput. 10(1&2): 16-27 (2010) - 2007
- [j30]Debajyoti Bera, Frederic Green, Steven Homer:
Small depth quantum circuits. SIGACT News 38(2): 35-50 (2007) - 2006
- [j29]M. Fang, Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang:
Quantum lower bounds for fanout. Quantum Inf. Comput. 6(1): 46-57 (2006) - 2003
- [j28]Lance Fortnow, Steven Homer:
A Short History of Computational Complexity. Bull. EATCS 80: 95-133 (2003) - 2002
- [j27]Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett:
Counting, fanout and the complexity of quantum ACC. Quantum Inf. Comput. 2(1): 35-65 (2002) - 2001
- [j26]Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer:
Hyper-polynomial hierarchies and the polynomial jump. Theor. Comput. Sci. 262(1): 241-256 (2001) - 1999
- [j25]Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer:
Complements of Multivalued Functions. Chic. J. Theor. Comput. Sci. 1999 (1999) - 1997
- [j24]Steven Homer, Marcus Peinado:
Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut. J. Parallel Distributed Comput. 46(1): 48-61 (1997) - [j23]Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman:
Oracles that Compute Values. SIAM J. Comput. 26(4): 1043-1065 (1997) - [j22]Zhixiang Chen, Steven Homer:
Learning Counting Functions with Queries. Theor. Comput. Sci. 180(1-2): 155-168 (1997) - 1996
- [j21]Zhixiang Chen, Steven Homer:
The Bounded Injury Priority Method and the Learnability of Unions of Rectangles. Ann. Pure Appl. Log. 77(2): 143-168 (1996) - [j20]Judy Goldsmith, Steven Homer:
Scalability and the Isomorphism Problem. Inf. Process. Lett. 57(3): 137-143 (1996) - 1994
- [j19]Steven Homer, Jie Wang:
Immunity of Complete Problems. Inf. Comput. 110(1): 119-129 (1994) - [j18]Steven Homer, Luc Longpré:
On Reductions of NP Sets to Sparse Sets. J. Comput. Syst. Sci. 48(2): 324-336 (1994) - [j17]Klaus Ambos-Spies, Steven Homer, Robert I. Soare:
Minimal Pairs and Complete Problems. Theor. Comput. Sci. 132(2): 229-241 (1994) - 1993
- [j16]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993) - [j15]Steven Homer, Stuart A. Kurtz, James S. Royer:
On A-Truth-Table-Hard Languages. Theor. Comput. Sci. 115(2): 383-389 (1993) - 1992
- [j14]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) - [j13]K. Ganesan, Steven Homer:
Complete Problems and Strong Polynomial Reducibilities. SIAM J. Comput. 21(4): 733-742 (1992) - 1991
- [j12]Harry Buhrman, Steven Homer, Leen Torenvliet:
Completeness for Nondeterministic Complexity Classes. Math. Syst. Theory 24(3): 179-200 (1991) - 1990
- [j11]Steven Homer:
Setting standards in Europe. Comput. Secur. 9(4): 295-300 (1990) - 1989
- [j10]Steven Homer, Jie Wang:
Absolute Results Concerning One-Way Functions and Their Applications. Math. Syst. Theory 22(1): 21-35 (1989) - 1987
- [j9]Steven Homer:
Minimal degrees for polynomial reducibilities. J. ACM 34(2): 480-491 (1987) - [j8]Steven Homer, Timothy J. Long:
Honest Polynomial Degrees and P=?NP. Theor. Comput. Sci. 51: 265-280 (1987) - 1986
- [j7]Steven Homer, John H. Reif:
Arithmetic Theories for Computational Complexity Problems. Inf. Control. 69(1-3): 1-11 (1986) - [j6]Steven Homer:
On Simple and Creative Sets in NP. Theor. Comput. Sci. 47(3): 169-180 (1986) - 1983
- [j5]William I. Gasarch, Steven Homer:
Relativizations Comparing NP and Exponential Time. Inf. Control. 58(1-3): 88-100 (1983) - [j4]Steven Homer:
Intermediate beta-R.E. Degrees and the Half-Jump. J. Symb. Log. 48(3): 790-796 (1983) - [j3]Steven Homer, Wolfgang Maass:
Oracle-Dependent Properties of the Lattice of NP Sets. Theor. Comput. Sci. 24: 279-289 (1983) - 1982
- [j2]Jerry Goldman, Steven Homer:
Quadratic Automata. J. Comput. Syst. Sci. 24(2): 180-196 (1982) - 1981
- [j1]Steven Homer, Barry E. Jacobs:
Degrees of Non α-Speedable Sets. Math. Log. Q. 27(31-35): 539-548 (1981)
Conference and Workshop Papers
- 2019
- [c25]Steven Homer:
Learning Hierarchical Spectral Representations of Human Speech with the Information Dynamics of Thinking. BNAIC/BENELEARN 2019 - [c24]Steven Homer:
Maximum Entropy Bayesian Actor Critic. BNAIC/BENELEARN 2019 - 2009
- [c23]Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Efficient Universal Quantum Circuits. COCOON 2009: 418-428 - 2005
- [c22]Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang:
Bounds on the Power of Constant-Depth Quantum Circuits. FCT 2005: 44-55 - 2000
- [c21]Frederic Green, Steven Homer, Chris Pollett:
On the Complexity of Quantum ACC. CCC 2000: 250-262 - 1997
- [c20]Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer:
Hyper-Polynomial Hierarchies and the NP-Jump. CCC 1997: 102-110 - 1996
- [c19]Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer:
Complements of Multivalued Functions. CCC 1996: 260-269 - [c18]Zhixiang Chen, Carlos Cunha, Steven Homer:
Finding a Hidden Code by Asking Questions. COCOON 1996: 50-55 - 1995
- [c17]Nader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer:
On the Learnability of Zn-DNF Formulas (Extended Abstract). COLT 1995: 198-205 - [c16]Steven Homer, Marcus Peinado:
A highly parallel algorithm to approximate MaxCut on distributed memory architectures. IPPS 1995: 113-117 - [c15]Steven Homer, Sarah Mocas:
Nonuniform Lower Bounds for Exponential Time Classes. MFCS 1995: 159-168 - 1994
- [c14]Zhixiang Chen, Steven Homer:
On Learning Counting Functions with Queries. COLT 1994: 218-227 - [c13]Nader H. Bshouty, Zhixiang Chen, Steven Homer:
On Learning Discretized Geometric Concepts (Extended Abstract). FOCS 1994: 54-63 - 1993
- [c12]Steven Homer, Marcus Peinado:
Experiments with polynomial-time CLIQUE approximation algorithms on very large graphs. Cliques, Coloring, and Satisfiability 1993: 147-167 - [c11]Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman:
On Using Oracles That Compute Values. STACS 1993: 398-407 - 1992
- [c10]Harry Buhrman, Steven Homer:
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS 1992: 116-127 - 1991
- [c9]Steven Homer, Luc Longpré:
On Reductions of NP Sets to Sparse Sets. SCT 1991: 79-88 - 1990
- [c8]Steven Homer:
Structural Properties of Nondeterministic Complete Sets. SCT 1990: 3-10 - [c7]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11 - [c6]Klaus Ambos-Spies, Steven Homer, Robert I. Soare:
Minimal Pairs and Complete Problems. STACS 1990: 24-36 - 1989
- [c5]Steven Homer, Alan L. Selman:
Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. SCT 1989: 3-14 - [c4]Rodney G. Downey, Steven Homer, William I. Gasarch, Michael F. Moses:
On Honest Polynomial Reductions, Relativizations, and P=NP. SCT 1989: 196-207 - [c3]K. Ganesan, Steven Homer:
Complete Problems and Strong Polynomial Reducibilities. STACS 1989: 240-250 - 1986
- [c2]Steven Homer:
On Simple and Creative Sets in NP. FSTTCS 1986: 412-425 - 1984
- [c1]Steven Homer:
Minimal Degrees for Honest Polynomial Reducibilities. FOCS 1984: 300-307
Parts in Books or Collections
- 2014
- [p1]Steven Homer, Alan L. Selman:
Turing and the development of computational complexity. Turing's Legacy 2014: 299-328
Editorship
- 1996
- [e2]Steven Homer, Jin-Yi Cai:
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996. IEEE Computer Society 1996, ISBN 0-8186-7386-9 [contents] - 1993
- [e1]Klaus Ambos-Spies, Steven Homer, Uwe Schöning:
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992. Cambridge University Press 1993, ISBN 0-521-44220-6 [contents]
Reference Works
- 2014
- [r1]Lance Fortnow, Steven Homer:
Computational Complexity. Computational Logic 2014: 495-521
Informal and Other Publications
- 2008
- [i3]Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Universal Quantum Circuits. CoRR abs/0804.2429 (2008) - [i2]Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Universal Quantum Circuits. Electron. Colloquium Comput. Complex. TR08 (2008) - 1999
- [i1]Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim:
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy. Electron. Colloquium Comput. Complex. TR99 (1999)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-24 23:06 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint