Steven Homer

According to our database, Steven Homer authored at least 58 papers between 1981 and 2020.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2020

Review of Kernelization: Theory of Parameterized Preprocessing by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.

Tim Jackman, Steve Homer

SIGACT News, 2020

2019

Maximum Entropy Bayesian Actor Critic.

Steven Homer

Proceedings of the 31st Benelux Conference on Artificial Intelligence (BNAIC 2019) and the 28th Belgian Dutch Conference on Machine Learning (Benelearn 2019), 2019

Learning Hierarchical Spectral Representations of Human Speech with the Information Dynamics of Thinking.

Steven Homer

Proceedings of the 31st Benelux Conference on Artificial Intelligence (BNAIC 2019) and the 28th Belgian Dutch Conference on Machine Learning (Benelearn 2019), 2019

2018

Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems.

Stephen A. Fenner, Frederic Green, Steven Homer

SIGACT News, 2018

2017

Review of Crypto School by Joachim von zur Gathen.

Steve Homer

SIGACT News, 2017

2014

Computational Complexity.

Lance Fortnow, Steven Homer

Proceedings of the Computational Logic, 2014

Turing and the development of computational complexity.

Steven Homer, Alan L. Selman

Proceedings of the Turing's Legacy: Developments from Turing's Ideas in Logic, 2014

2011

Computability and Complexity Theory, Second Edition.

Steven Homer, Alan L. Selman

Texts in Computer Science, Springer, ISBN: 978-1-4614-0682-2, 2011

2010

Efficient universal quantum circuits.

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer

Quantum Inf. Comput., 2010

Non-Uniform Reductions.

Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet

Theory Comput. Syst., 2010

2008

Universal Quantum Circuits.

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer

Electron. Colloquium Comput. Complex., 2008

2007

Small depth quantum circuits.

Debajyoti Bera, Frederic Green, Steven Homer

SIGACT News, 2007

2006

Quantum lower bounds for fanout.

M. Fang, Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang

Quantum Inf. Comput., 2006

2005

Bounds on the Power of Constant-Depth Quantum Circuits.

Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2003

A Short History of Computational Complexity.

Lance Fortnow, Steven Homer

Bull. EATCS, 2003

2002

Counting, fanout and the complexity of quantum ACC.

Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett

Quantum Inf. Comput., 2002

2001

Computability and Complexity Theory.

Steven Homer, Alan L. Selman

Texts in Computer Science, Springer, ISBN: 978-1-4757-3544-4, 2001

Hyper-polynomial hierarchies and the polynomial jump.

Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer

Theor. Comput. Sci., 2001

2000

On the Complexity of Quantum ACC.

Frederic Green, Steven Homer, Chris Pollett

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

Electron. Colloquium Comput. Complex., 1999

Complements of Multivalued Functions.

Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer

Chic. J. Theor. Comput. Sci., 1999

1997

Learning Counting Functions with Queries.

Zhixiang Chen, Steven Homer

Theor. Comput. Sci., 1997

Oracles that Compute Values.

Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman

SIAM J. Comput., 1997

Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut.

Steven Homer, Marcus Peinado

J. Parallel Distributed Comput., 1997

Hyper-Polynomial Hierarchies and the NP-Jump.

Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Scalability and the Isomorphism Problem.

Judy Goldsmith, Steven Homer

Inf. Process. Lett., 1996

The Bounded Injury Priority Method and the Learnability of Unions of Rectangles.

Zhixiang Chen, Steven Homer

Ann. Pure Appl. Log., 1996

Finding a Hidden Code by Asking Questions.

Zhixiang Chen, Carlos Cunha, Steven Homer

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

Nonuniform Lower Bounds for Exponential Time Classes.

Steven Homer, Sarah Mocas

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

A highly parallel algorithm to approximate MaxCut on distributed memory architectures.

Steven Homer, Marcus Peinado

Proceedings of IPPS '95, 1995

On the Learnability of <i>Z</i>_n-DNF Formulas (Extended Abstract).

Nader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

Immunity of Complete Problems

Steven Homer, Jie Wang

Inf. Comput., April, 1994

Minimal Pairs and Complete Problems.

Klaus Ambos-Spies, Steven Homer, Robert I. Soare

Theor. Comput. Sci., 1994

On Reductions of NP Sets to Sparse Sets.

Steven Homer, Luc Longpré

J. Comput. Syst. Sci., 1994

On Learning Discretized Geometric Concepts (Extended Abstract)

Nader H. Bshouty, Zhixiang Chen, Steven Homer

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

On A-Truth-Table-Hard Languages.

Steven Homer, Stuart A. Kurtz, James S. Royer

Theor. Comput. Sci., 1993

Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Theor. Comput. Sci., 1993

On Using Oracles That Compute Values.

Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman

Proceedings of the STACS 93, 1993

Experiments with polynomial-time CLIQUE approximation algorithms on very large graphs.

Steven Homer, Marcus Peinado

Proceedings of the Cliques, 1993

1992

Complete Problems and Strong Polynomial Reducibilities.

K. Ganesan, Steven Homer

SIAM J. Comput., 1992

Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography.

Steven Homer, Alan L. Selman

J. Comput. Syst. Sci., 1992

Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy.

Harry Buhrman, Steven Homer

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

1991

Completeness for Nondeterministic Complexity Classes.

Harry Buhrman, Steven Homer, Leen Torenvliet

Math. Syst. Theory, 1991

1990

Setting standards in Europe.

Steven Homer

Comput. Secur., 1990

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Proceedings of the STACS 90, 1990

Structural Properties of Nondeterministic Complete Sets.

Steven Homer

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Absolute Results Concerning One-Way Functions and Their Applications.

Steven Homer, Jie Wang

Math. Syst. Theory, 1989

On Honest Polynomial Reductions, Relativizations, and P=NP.

Rodney G. Downey, Steven Homer, William I. Gasarch, Michael F. Moses

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1987

Honest Polynomial Degrees and P=?NP.

Steven Homer, Timothy J. Long

Theor. Comput. Sci., 1987

Minimal degrees for polynomial reducibilities.

Steven Homer

J. ACM, 1987

1986

On Simple and Creative Sets in NP.

Steven Homer

Theor. Comput. Sci., 1986

Arithmetic Theories for Computational Complexity Problems

Steven Homer, John H. Reif

Inf. Control., 1986

1984

Minimal Degrees for Honest Polynomial Reducibilities

Steven Homer

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Oracle-Dependent Properties of the Lattice of NP Sets.

Steven Homer, Wolfgang Maass

Theor. Comput. Sci., 1983

Intermediate beta-R.E. Degrees and the Half-Jump.

Steven Homer

J. Symb. Log., 1983

Relativizations Comparing NP and Exponential Time

William I. Gasarch, Steven Homer

Inf. Control., 1983

1982

Quadratic Automata.

Jerry Goldman, Steven Homer

J. Comput. Syst. Sci., 1982

1981

Degrees of Non α-Speedable Sets.

Steven Homer, Barry E. Jacobs

Math. Log. Q., 1981