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
2020 – today
- 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)
2010 – 2019
- 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 - 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) - 2014
- [p1]Steven Homer, Alan L. Selman:
Turing and the development of computational complexity. Turing's Legacy 2014: 299-328 - [r1]Lance Fortnow, Steven Homer:
Computational Complexity. Computational Logic 2014: 495-521 - 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 - 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)
2000 – 2009
- 2009
- [c23]Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Efficient Universal Quantum Circuits. COCOON 2009: 418-428 - 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) - 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) - 2005
- [c22]Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang:
Bounds on the Power of Constant-Depth Quantum Circuits. FCT 2005: 44-55 - 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
- [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 - [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) - 2000
- [c21]Frederic Green, Steven Homer, Chris Pollett:
On the Complexity of Quantum ACC. CCC 2000: 250-262
1990 – 1999
- 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) - [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) - 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) - [c20]Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer:
Hyper-Polynomial Hierarchies and the NP-Jump. CCC 1997: 102-110 - 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) - [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 - [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] - 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
- [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) - [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
- [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) - [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 - [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] - 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) - [c10]Harry Buhrman, Steven Homer:
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS 1992: 116-127 - 1991
- [j12]Harry Buhrman, Steven Homer, Leen Torenvliet:
Completeness for Nondeterministic Complexity Classes. Math. Syst. Theory 24(3): 179-200 (1991) - [c9]Steven Homer, Luc Longpré:
On Reductions of NP Sets to Sparse Sets. SCT 1991: 79-88 - 1990
- [j11]Steven Homer:
Setting standards in Europe. Comput. Secur. 9(4): 295-300 (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
1980 – 1989
- 1989
- [j10]Steven Homer, Jie Wang:
Absolute Results Concerning One-Way Functions and Their Applications. Math. Syst. Theory 22(1): 21-35 (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 - 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) - [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 - 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)
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