×
Author ID: homer.steven Recent zbMATH articles by "Homer, Steven"
Published as: Homer, Steven
External Links: MGP

Publications by Year

Citations contained in zbMATH Open

40 Publications have been cited 229 times in 180 Documents Cited by Year
Oracle-dependent properties of the lattice of NP sets. Zbl 0543.03024
Homer, Steven; Maass, Wolfgang
27
1983
Complete problems and strong polynomial reducibilities. Zbl 0749.68035
Ganesan, K.; Homer, Steven
22
1992
Oracles for structural properties: The isomorphism problem and public-key cryptography. Zbl 0757.68055
Homer, Steven; Selman, Alan L.
13
1992
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. Zbl 0925.68183
Buhrman, Harry; Homer, Steven
13
1992
Computability and complexity theory. 2nd ed. Zbl 1248.68192
Homer, Steven; Selman, Alan L.
12
2011
Computability and complexity theory. Zbl 1033.68045
Homer, Steven; Selman, Alan L.
11
2001
Minimal degrees for polynomial reducibilities. Zbl 0639.03046
Homer, Steven
10
1987
On 1-truth-table-hard languages. Zbl 0780.68041
Homer, Steven; Kurtz, Stuart; Royer, James
10
1993
Counting, fanout and the complexity of quantum ACC. Zbl 1187.81065
Green, F.; Homer, S.; Moore, Cristopher; Pollett, C.
10
2001
Completeness for nondeterministic complexity classes. Zbl 0745.68046
Buhrman, Harry; Homer, Steven; Torenvliet, Leen
9
1991
On reductions of NP sets to sparse sets. Zbl 0806.68046
Homer, Steven; Longpré, Luc
9
1994
Relativizations comparing NP and exponential time. Zbl 0562.68034
Gasarch, W. Ian; Homer, Steven
8
1983
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Zbl 0964.68011
Fenner, Stephen; Green, Frederic; Homer, Steven; Pruim, Randall
8
1999
Experiments with polynomial-time CLIQUE approximation algorithms on very large graphs. Zbl 0859.68068
Homer, Steven; Peinado, Marcus
7
1996
Bounds on the power of constant-depth quantum circuits. Zbl 1123.68037
Fenner, Stephen; Green, Frederic; Homer, Steven; Zhang, Yong
6
2005
On simple and creative sets in NP. Zbl 0638.68034
Homer, Steven
6
1986
Structural properties of complete problems for exponential time. Zbl 0880.68040
Homer, Steven
6
1997
Minimal polynomial degrees of nonrecursive sets. Zbl 0582.03023
Homer, Steven
5
1985
Honest polynomial degrees and \(P=?NP\). Zbl 0631.68048
Homer, Steven; Long, Timothy J.
5
1987
The bounded injury priority method and the learnability of unions of rectangles. Zbl 0852.68079
Chen, Zhixiang; Homer, Steven
5
1996
Quantum lower bounds for fanout. Zbl 1152.81710
Fang, M.; Fenner, S.; Green, F.; Homer, S.; Zhang, Y.
5
2006
Scalability and the isomorphism problem. Zbl 0875.68542
Goldsmith, Judy; Homer, Steven
4
1996
Non-uniform reductions. Zbl 1206.68129
Buhrman, Harry; Hescott, Benjamin; Homer, Steven; Torenvliet, Leen
4
2010
Efficient universal quantum circuits. Zbl 1183.81036
Bera, Debajyoti; Fenner, S.; Green, F.; Homer, S.
4
2010
A note on the almost-everywhere hierarchy for nondeterministic time. Zbl 0729.68022
Allender, Eric; Beigel, Richard; Hertrampf, Ulrich; Homer, Steven
4
1990
Oracles that compute values. Zbl 0885.68057
Fenner, Stephen; Homer, Steven; Ogihara, Mitsunori; Selman, Alan
3
1997
Doubly-periodic sequences and two-dimensional recurrences. Zbl 0571.12010
Homer, Steven; Goldman, Jerry
3
1985
Doubly-periodic sequences and a class of two-dimensional cyclic codes. Zbl 0765.16011
Goldman, Jerry; Homer, Steven
2
1992
Complements of multivalued functions. Zbl 0924.68089
Fenner, Stephen; Green, Frederic; Homer, Steven; Selman, Alan L.; Thierauf, Thomas; Vollmer, Heribert
2
1999
Absolute results concerning one-way functions and their applications. Zbl 0677.94008
Homer, Steven; Wang, Jie
2
1989
Almost-everywhere complexity hierarchies for nondeterministic time. Zbl 0779.68032
Allender, Eric; Beigel, Richard; Hertrampf, Ulrich; Homer, Steven
2
1993
Immunity of complete problems. Zbl 0804.68050
Homer, Steven; Wang, Jie
2
1994
Complete problems and strong polynomial reducibilities. Zbl 1492.68055
Ganesan, K.; Homer, Steven
2
1989
Quadratic automata. Zbl 0492.68046
Goldman, Jerry; Homer, Steven
1
1982
Minimal pairs and complete problems. Zbl 0744.03045
Ambos-Spies, Klaus; Homer, Steven; Soare, Robert I.
1
1990
Honest polynomial reductions and Exptally sets. Zbl 0722.03034
Ambos-Spies, Klaus; Homer, Steven; Yang, Dongping
1
1990
On simple and creative sets in NP. Zbl 0624.68039
Homer, Steven
1
1986
Minimal pairs and complete problems. Zbl 0801.03031
Ambos-Spies, Klaus; Homer, Steven; Soare, Robert I.
1
1994
Learning counting functions with queries. Zbl 0901.68158
Chen, Zhixiang; Homer, Steven
1
1997
Nonuniform lower bounds for exponential time classes. Zbl 1188.68145
Homer, Steven; Mocas, Sarah
1
1995
Computability and complexity theory. 2nd ed. Zbl 1248.68192
Homer, Steven; Selman, Alan L.
12
2011
Non-uniform reductions. Zbl 1206.68129
Buhrman, Harry; Hescott, Benjamin; Homer, Steven; Torenvliet, Leen
4
2010
Efficient universal quantum circuits. Zbl 1183.81036
Bera, Debajyoti; Fenner, S.; Green, F.; Homer, S.
4
2010
Quantum lower bounds for fanout. Zbl 1152.81710
Fang, M.; Fenner, S.; Green, F.; Homer, S.; Zhang, Y.
5
2006
Bounds on the power of constant-depth quantum circuits. Zbl 1123.68037
Fenner, Stephen; Green, Frederic; Homer, Steven; Zhang, Yong
6
2005
Computability and complexity theory. Zbl 1033.68045
Homer, Steven; Selman, Alan L.
11
2001
Counting, fanout and the complexity of quantum ACC. Zbl 1187.81065
Green, F.; Homer, S.; Moore, Cristopher; Pollett, C.
10
2001
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Zbl 0964.68011
Fenner, Stephen; Green, Frederic; Homer, Steven; Pruim, Randall
8
1999
Complements of multivalued functions. Zbl 0924.68089
Fenner, Stephen; Green, Frederic; Homer, Steven; Selman, Alan L.; Thierauf, Thomas; Vollmer, Heribert
2
1999
Structural properties of complete problems for exponential time. Zbl 0880.68040
Homer, Steven
6
1997
Oracles that compute values. Zbl 0885.68057
Fenner, Stephen; Homer, Steven; Ogihara, Mitsunori; Selman, Alan
3
1997
Learning counting functions with queries. Zbl 0901.68158
Chen, Zhixiang; Homer, Steven
1
1997
Experiments with polynomial-time CLIQUE approximation algorithms on very large graphs. Zbl 0859.68068
Homer, Steven; Peinado, Marcus
7
1996
The bounded injury priority method and the learnability of unions of rectangles. Zbl 0852.68079
Chen, Zhixiang; Homer, Steven
5
1996
Scalability and the isomorphism problem. Zbl 0875.68542
Goldsmith, Judy; Homer, Steven
4
1996
Nonuniform lower bounds for exponential time classes. Zbl 1188.68145
Homer, Steven; Mocas, Sarah
1
1995
On reductions of NP sets to sparse sets. Zbl 0806.68046
Homer, Steven; Longpré, Luc
9
1994
Immunity of complete problems. Zbl 0804.68050
Homer, Steven; Wang, Jie
2
1994
Minimal pairs and complete problems. Zbl 0801.03031
Ambos-Spies, Klaus; Homer, Steven; Soare, Robert I.
1
1994
On 1-truth-table-hard languages. Zbl 0780.68041
Homer, Steven; Kurtz, Stuart; Royer, James
10
1993
Almost-everywhere complexity hierarchies for nondeterministic time. Zbl 0779.68032
Allender, Eric; Beigel, Richard; Hertrampf, Ulrich; Homer, Steven
2
1993
Complete problems and strong polynomial reducibilities. Zbl 0749.68035
Ganesan, K.; Homer, Steven
22
1992
Oracles for structural properties: The isomorphism problem and public-key cryptography. Zbl 0757.68055
Homer, Steven; Selman, Alan L.
13
1992
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. Zbl 0925.68183
Buhrman, Harry; Homer, Steven
13
1992
Doubly-periodic sequences and a class of two-dimensional cyclic codes. Zbl 0765.16011
Goldman, Jerry; Homer, Steven
2
1992
Completeness for nondeterministic complexity classes. Zbl 0745.68046
Buhrman, Harry; Homer, Steven; Torenvliet, Leen
9
1991
A note on the almost-everywhere hierarchy for nondeterministic time. Zbl 0729.68022
Allender, Eric; Beigel, Richard; Hertrampf, Ulrich; Homer, Steven
4
1990
Minimal pairs and complete problems. Zbl 0744.03045
Ambos-Spies, Klaus; Homer, Steven; Soare, Robert I.
1
1990
Honest polynomial reductions and Exptally sets. Zbl 0722.03034
Ambos-Spies, Klaus; Homer, Steven; Yang, Dongping
1
1990
Absolute results concerning one-way functions and their applications. Zbl 0677.94008
Homer, Steven; Wang, Jie
2
1989
Complete problems and strong polynomial reducibilities. Zbl 1492.68055
Ganesan, K.; Homer, Steven
2
1989
Minimal degrees for polynomial reducibilities. Zbl 0639.03046
Homer, Steven
10
1987
Honest polynomial degrees and \(P=?NP\). Zbl 0631.68048
Homer, Steven; Long, Timothy J.
5
1987
On simple and creative sets in NP. Zbl 0638.68034
Homer, Steven
6
1986
On simple and creative sets in NP. Zbl 0624.68039
Homer, Steven
1
1986
Minimal polynomial degrees of nonrecursive sets. Zbl 0582.03023
Homer, Steven
5
1985
Doubly-periodic sequences and two-dimensional recurrences. Zbl 0571.12010
Homer, Steven; Goldman, Jerry
3
1985
Oracle-dependent properties of the lattice of NP sets. Zbl 0543.03024
Homer, Steven; Maass, Wolfgang
27
1983
Relativizations comparing NP and exponential time. Zbl 0562.68034
Gasarch, W. Ian; Homer, Steven
8
1983
Quadratic automata. Zbl 0492.68046
Goldman, Jerry; Homer, Steven
1
1982
all top 5

Cited by 225 Authors

12 Hemaspaandra, Lane A.
10 Glaßer, Christian
10 Zhang, Liyu
9 Selman, Alan Louis
8 Homer, Steven
7 Fortnow, Lance J.
7 Hitchcock, John M.
7 Tani, Seiichiro
6 Ambos-Spies, Klaus
6 Takahashi, Yasuhiro
5 Fu, Bin
5 Mayordomo, Elvira
5 Pavan, Aduri
4 Allender, Eric W.
4 Beyersdorff, Olaf
4 Downey, Rodney Graham
4 Kabanets, Valentine
4 Kurtz, Stuart A.
4 Royer, James S.
4 Torenvliet, Leen
3 Agrawal, Manindra
3 Balcázar, José Luis
3 Buhrman, Harry
3 Goldman, Jerry I.
3 Hemaspaandra, Edith
3 Hoene, Albrecht
3 Impagliazzo, Russell
3 Ko, Ker-I
3 Köbler, Johannes
3 Levet, Michael
3 Lutz, Jack H.
3 Shafei, Hadi
3 Subramani, Krishnan
3 Takeuchi, Yuki
3 Yamakami, Tomoyuki
2 Arvind, Vikraman
2 Beigel, Richard
2 Chandrasekaran, Ramaswamy
2 Chen, Zhixiang
2 Faliszewski, Piotr
2 Fenner, Stephen A.
2 Gasarch, William Ian
2 Goldsmith, Judy
2 Grochow, Joshua A.
2 Hescott, Benjamin J.
2 Karpinski, Marek
2 Khan, Fitra
2 Lei, Hansheng
2 Li, Angsheng
2 Mahaney, Stephen R.
2 Mundhenk, Martin
2 Naik, Ashish V.
2 Nerode, Anil
2 Ogihara, Mitsunori
2 Orponen, Pekka
2 Quweider, Mahmoud
2 Reitwießner, Christian
2 Remmel, Jeffrey Brian
2 Rothe, Jörg-Matthias
2 Rubery, Daniel
2 Russo, David A.
2 Schöning, Uwe
2 Selivanov, Viktor L’vovich
2 Sengupta, Samik
2 Shinoda, Juichi
2 Thierauf, Thomas
2 Travers, Stephen D.
2 Vinodchandran, N. Variyam
2 Volkovich, Ilya
2 Wang, Jie
2 Watanabe, Osamu
2 Witek, Maximilian
2 Zimand, Marius
1 Aaronson, Scott
1 Abascal, Jackson
1 Albrecht, Andreas A.
1 Ameur, Foued
1 Anderson, Daniel M.
1 Anjos, Miguel F.
1 Aoki, Kunimasa
1 Apon, Daniel
1 Atıcı, Alp
1 Bach, Eric
1 Bakibayev, Timur
1 Beaudry, Martin
1 Biswas, Somenath
1 Botella, Arnaud
1 Brotcorne, Luce
1 Bruschi, Danilo
1 Bshouty, Nader H.
1 Burtschick, Hans-Jörg
1 Caumon, Guillaume
1 Chalki, Aggeliki
1 Chen, Ruiwen
1 Chen, Yijia
1 Chin, William
1 Chomicki, Jan
1 Collins, Nathaniel A.
1 Costa, José Félix
1 Crescenzi, Pierluigi
...and 125 more Authors
all top 5

Cited in 40 Serials

51 Theoretical Computer Science
19 Journal of Computer and System Sciences
12 Information and Computation
10 Theory of Computing Systems
9 Mathematical Systems Theory
8 Information Processing Letters
5 Computational Complexity
4 Annals of Pure and Applied Logic
4 RAIRO. Informatique Théorique et Applications
3 Artificial Intelligence
2 Discrete Applied Mathematics
2 The Journal of Symbolic Logic
2 Computers & Operations Research
2 International Journal of Foundations of Computer Science
1 Communications in Algebra
1 Journal of Combinatorial Theory. Series B
1 Journal of Soviet Mathematics
1 Advances in Applied Mathematics
1 SIAM Journal on Algebraic and Discrete Methods
1 Journal of Complexity
1 Algorithmica
1 Japan Journal of Industrial and Applied Mathematics
1 International Journal of Algebra and Computation
1 Games and Economic Behavior
1 Acta Mathematica Sinica. New Series
1 Mathematical Programming. Series A. Series B
1 The Australasian Journal of Combinatorics
1 Journal of Applied Non-Classical Logics
1 Mathematical Logic Quarterly (MLQ)
1 Annals of Mathematics and Artificial Intelligence
1 Journal of Heuristics
1 Journal of Combinatorial Optimization
1 Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
1 Computational Geosciences
1 RAIRO. Theoretical Informatics and Applications
1 Quantum Information Processing
1 Computational Biology and Chemistry
1 Discrete Optimization
1 Forum of Mathematics, Sigma
1 Computer Science Review

Citations by Year