×

zbMATH — the first resource for mathematics

Schöning, Uwe

Compute Distance To:
Author ID: schoning.uwe Recent zbMATH articles by "Schöning, Uwe"
Published as: Schoening, Uwe; Schöning, U.; Schöning, Uwe
Documents Indexed: 89 Publications since 1981, including 20 Books

Publications by Year

Citations contained in zbMATH Open

62 Publications have been cited 777 times in 503 Documents Cited by Year
The graph isomorphism problem: its structural complexity. Zbl 0813.68103
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
74
1993
A low and a high hierarchy within NP. Zbl 0515.68046
Schoening, Uwe
46
1983
The difference and truth-table hierarchies for NP. Zbl 0642.03024
Köbler, Johannes; Schöning, Uwe; Wagner, Klaus W.
39
1987
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
38
2002
Bi-immune sets for complexity classes. Zbl 0572.68035
Balcázar, José L.; Schöning, Uwe
36
1985
Graph isomorphism is in the low hierarchy. Zbl 0666.68048
Schöning, Uwe
35
1988
On circuit-size complexity and the low hierarchy in NP. Zbl 0562.68033
Ko, Ker-I; Schöning, Uwe
31
1985
Probabilistic complexity classes and lowness. Zbl 0688.68045
Schöning, Uwe
30
1989
Complexity and structure. Zbl 0589.03022
Schöning, Uwe
28
1986
A uniform approach to obtain diagonal sets in complexity classes. Zbl 0485.68039
Schoening, Uwe
27
1982
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U.
26
1997
The polynomial-time hierarchy and sparse oracles. Zbl 0625.68033
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe
25
1986
Immunity, relativizations, and nondeterminism. Zbl 0558.68039
Schöning, Uwe; Book, Ronald V.
21
1984
A probabilistic algorithm for \(k\)-SAT based on limited local search and restart. Zbl 1050.68049
Schöning, U.
20
2002
On counting and approximation. Zbl 0663.03025
Köbler, Johannes; Schöning, Uwe; Toran, Jacobo
19
1989
A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
18
2002
Instance complexity. Zbl 0807.68035
Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu
18
1994
Complete sets and closeness to complexity classes. Zbl 0617.68047
Schöning, Uwe
18
1986
Reductions to sets of low information content. Zbl 0794.68058
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
17
1993
Sparse sets, lowness and highness. Zbl 0621.68033
Balćzar, José L.; Book, Ronald V.; Schöning, Uwe
16
1986
Optimal approximations and polynomially levelable sets. Zbl 0644.68054
Orponen, Pekka; Russo, David A.; Schöning, Uwe
15
1986
Graph isomorphism is low for PP. Zbl 0770.68055
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
13
1992
Robust algorithms: a different approach to oracles. Zbl 0574.68041
Schöning, Uwe
13
1985
Algorithmics in exponential time. Zbl 1118.68500
Schöning, Uwe
12
2005
Turing machines with few accepting computations and low sets for PP. Zbl 0757.68056
Köbler, Johannes; Schöning, Uwe; Toda, Seinosuke; Torán, Jacobo
12
1992
The density and complexity of polynomial cores for intractable sets. Zbl 0611.68021
Orponen, Pekka; Schöning, Uwe
11
1986
Gems of theoretical computer science. Zbl 0911.68002
Schöning, Uwe; Pruim, Randall
10
1998
Logarithmic advice classes. Zbl 0761.68040
Balcázar, José L.; Schöning, Uwe
10
1992
Collapsing oracle hierarchies, census functions and logarithmically many queries. Zbl 0648.68065
Schöning, Uwe; Wagner, Klaus W.
9
1988
On small generators. Zbl 0558.68040
Schöning, Uwe
8
1984
If NP has polynomial-size circuits, then MA=AM. Zbl 0874.68185
Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer
6
1995
Graph isomorphism is in the low hierarchy. Zbl 0621.68034
Schöning, Uwe
6
1987
Choosing probability distributions for stochastic local search and the role of make versus break. Zbl 1273.68333
Balint, Adrian; Schöning, Uwe
5
2012
Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe
4
2000
What is a hard instance of a computational problem? Zbl 0617.68048
Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu
4
1986
On bounded query machines. Zbl 0608.68038
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe
4
1985
The structure of polynomial complexity cores. Zbl 0556.68014
Orponen, Pekka; Schöning, Uwe
4
1984
Minimal pairs for P. Zbl 0543.03025
Schöning, Uwe
4
1984
Randomized algorithms for 3-SAT. Zbl 1109.68133
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
3
2007
Smaller superconcentrators of density 28. Zbl 1185.68496
Schöning, Uwe
3
2006
New algorithms for \(k\)-SAT based on the local search principle. Zbl 0999.68205
Schöning, Uwe
3
2001
Construction of expanders and superconcentrators using Kolmogorov complexity. Zbl 0953.68065
Schöning, Uwe
3
2000
Resolution proofs, exponential bounds, and Kolmogorov complexity. Zbl 0976.03063
Schöning, Uwe
3
1997
Theoretical computer science - in brief. 3. Aufl. Zbl 0876.68005
Schöning, Uwe
3
1997
High sets for NP. Zbl 0876.68043
Köbler, Johannes; Schöning, Uwe
3
1997
On random reductions from sparse sets to tally sets. Zbl 0780.68044
Schöning, Uwe
3
1993
Logik für Informatiker. 2., überarb. Aufl. Zbl 0677.03001
Schöning, Uwe
3
1989
Logic for computer scientists. Reprint of the 1989 hardback ed. Zbl 1206.03001
Schöning, Uwe
2
2008
An improved randomized algorithm for 3-SAT. Zbl 0991.68742
Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu
2
2001
Sparse oracles, lowness, and highness. Zbl 0554.68033
Balcázar, José L.; Book, Ronald V.; Schöning, Uwe
2
1984
QuickSort from an information theoretic view. Zbl 1170.68450
List, Beatrice; Maucher, Markus; Schöning, Uwe; Schuler, Rainer
1
2009
Theoretical computer science – in brief. 5th ed. Zbl 1173.68517
Schöning, Uwe
1
2008
Principles of stochastic local search. Zbl 1175.68424
Schöning, Uwe
1
2007
Algorithmics. Zbl 0993.68143
Schöning, Uwe
1
2001
Logic for computer scientists. 4., überarb. Aufl. Zbl 0829.03001
Schöning, Uwe
1
1995
Reductions to sets of low information content (extended abstract). Zbl 1425.68125
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
1
1992
Complexity cores and hard problem instances. Zbl 0819.68064
Schöning, Uwe
1
1990
Logic for computer scientists. Zbl 0748.03001
Schöning, Uwe
1
1989
Complexity theory and interaction. Zbl 0661.68044
Schöning, Uwe
1
1988
Graph isomorphism is in the low hierarchy. Zbl 0797.68076
Schoening, Uwe
1
1988
Netzwerkkomplexität, probabilistische Algorithmen und Relativierungen. Zbl 0575.68050
Schöning, Uwe
1
1985
Generalized polynomial-time reducibilities, degrees and NP-completeness. Zbl 0598.03030
Schöning, Uwe
1
1984
Choosing probability distributions for stochastic local search and the role of make versus break. Zbl 1273.68333
Balint, Adrian; Schöning, Uwe
5
2012
QuickSort from an information theoretic view. Zbl 1170.68450
List, Beatrice; Maucher, Markus; Schöning, Uwe; Schuler, Rainer
1
2009
Logic for computer scientists. Reprint of the 1989 hardback ed. Zbl 1206.03001
Schöning, Uwe
2
2008
Theoretical computer science – in brief. 5th ed. Zbl 1173.68517
Schöning, Uwe
1
2008
Randomized algorithms for 3-SAT. Zbl 1109.68133
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
3
2007
Principles of stochastic local search. Zbl 1175.68424
Schöning, Uwe
1
2007
Smaller superconcentrators of density 28. Zbl 1185.68496
Schöning, Uwe
3
2006
Algorithmics in exponential time. Zbl 1118.68500
Schöning, Uwe
12
2005
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
38
2002
A probabilistic algorithm for \(k\)-SAT based on limited local search and restart. Zbl 1050.68049
Schöning, U.
20
2002
A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
18
2002
New algorithms for \(k\)-SAT based on the local search principle. Zbl 0999.68205
Schöning, Uwe
3
2001
An improved randomized algorithm for 3-SAT. Zbl 0991.68742
Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu
2
2001
Algorithmics. Zbl 0993.68143
Schöning, Uwe
1
2001
Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe
4
2000
Construction of expanders and superconcentrators using Kolmogorov complexity. Zbl 0953.68065
Schöning, Uwe
3
2000
Gems of theoretical computer science. Zbl 0911.68002
Schöning, Uwe; Pruim, Randall
10
1998
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U.
26
1997
Resolution proofs, exponential bounds, and Kolmogorov complexity. Zbl 0976.03063
Schöning, Uwe
3
1997
Theoretical computer science - in brief. 3. Aufl. Zbl 0876.68005
Schöning, Uwe
3
1997
High sets for NP. Zbl 0876.68043
Köbler, Johannes; Schöning, Uwe
3
1997
If NP has polynomial-size circuits, then MA=AM. Zbl 0874.68185
Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer
6
1995
Logic for computer scientists. 4., überarb. Aufl. Zbl 0829.03001
Schöning, Uwe
1
1995
Instance complexity. Zbl 0807.68035
Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu
18
1994
The graph isomorphism problem: its structural complexity. Zbl 0813.68103
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
74
1993
Reductions to sets of low information content. Zbl 0794.68058
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
17
1993
On random reductions from sparse sets to tally sets. Zbl 0780.68044
Schöning, Uwe
3
1993
Graph isomorphism is low for PP. Zbl 0770.68055
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
13
1992
Turing machines with few accepting computations and low sets for PP. Zbl 0757.68056
Köbler, Johannes; Schöning, Uwe; Toda, Seinosuke; Torán, Jacobo
12
1992
Logarithmic advice classes. Zbl 0761.68040
Balcázar, José L.; Schöning, Uwe
10
1992
Reductions to sets of low information content (extended abstract). Zbl 1425.68125
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
1
1992
Complexity cores and hard problem instances. Zbl 0819.68064
Schöning, Uwe
1
1990
Probabilistic complexity classes and lowness. Zbl 0688.68045
Schöning, Uwe
30
1989
On counting and approximation. Zbl 0663.03025
Köbler, Johannes; Schöning, Uwe; Toran, Jacobo
19
1989
Logik für Informatiker. 2., überarb. Aufl. Zbl 0677.03001
Schöning, Uwe
3
1989
Logic for computer scientists. Zbl 0748.03001
Schöning, Uwe
1
1989
Graph isomorphism is in the low hierarchy. Zbl 0666.68048
Schöning, Uwe
35
1988
Collapsing oracle hierarchies, census functions and logarithmically many queries. Zbl 0648.68065
Schöning, Uwe; Wagner, Klaus W.
9
1988
Complexity theory and interaction. Zbl 0661.68044
Schöning, Uwe
1
1988
Graph isomorphism is in the low hierarchy. Zbl 0797.68076
Schoening, Uwe
1
1988
The difference and truth-table hierarchies for NP. Zbl 0642.03024
Köbler, Johannes; Schöning, Uwe; Wagner, Klaus W.
39
1987
Graph isomorphism is in the low hierarchy. Zbl 0621.68034
Schöning, Uwe
6
1987
Complexity and structure. Zbl 0589.03022
Schöning, Uwe
28
1986
The polynomial-time hierarchy and sparse oracles. Zbl 0625.68033
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe
25
1986
Complete sets and closeness to complexity classes. Zbl 0617.68047
Schöning, Uwe
18
1986
Sparse sets, lowness and highness. Zbl 0621.68033
Balćzar, José L.; Book, Ronald V.; Schöning, Uwe
16
1986
Optimal approximations and polynomially levelable sets. Zbl 0644.68054
Orponen, Pekka; Russo, David A.; Schöning, Uwe
15
1986
The density and complexity of polynomial cores for intractable sets. Zbl 0611.68021
Orponen, Pekka; Schöning, Uwe
11
1986
What is a hard instance of a computational problem? Zbl 0617.68048
Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu
4
1986
Bi-immune sets for complexity classes. Zbl 0572.68035
Balcázar, José L.; Schöning, Uwe
36
1985
On circuit-size complexity and the low hierarchy in NP. Zbl 0562.68033
Ko, Ker-I; Schöning, Uwe
31
1985
Robust algorithms: a different approach to oracles. Zbl 0574.68041
Schöning, Uwe
13
1985
On bounded query machines. Zbl 0608.68038
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe
4
1985
Netzwerkkomplexität, probabilistische Algorithmen und Relativierungen. Zbl 0575.68050
Schöning, Uwe
1
1985
Immunity, relativizations, and nondeterminism. Zbl 0558.68039
Schöning, Uwe; Book, Ronald V.
21
1984
On small generators. Zbl 0558.68040
Schöning, Uwe
8
1984
The structure of polynomial complexity cores. Zbl 0556.68014
Orponen, Pekka; Schöning, Uwe
4
1984
Minimal pairs for P. Zbl 0543.03025
Schöning, Uwe
4
1984
Sparse oracles, lowness, and highness. Zbl 0554.68033
Balcázar, José L.; Book, Ronald V.; Schöning, Uwe
2
1984
Generalized polynomial-time reducibilities, degrees and NP-completeness. Zbl 0598.03030
Schöning, Uwe
1
1984
A low and a high hierarchy within NP. Zbl 0515.68046
Schoening, Uwe
46
1983
A uniform approach to obtain diagonal sets in complexity classes. Zbl 0485.68039
Schoening, Uwe
27
1982
all top 5

Cited by 591 Authors

37 Hemaspaandra, Lane A.
19 Köbler, Johannes
17 Arvind, Vikraman
16 Schöning, Uwe
15 Rothe, Jörg-Matthias
13 Torán, Jacobo
12 Toda, Seinosuke
11 Book, Ronald Vernon
10 Beigel, Richard
10 Ogihara, Mitsunori
10 Pavan, Aduri
10 Watanabe, Osamu
9 Allender, Eric W.
9 Balcázar, José Luis
9 Selman, Alan L.
9 Vinodchandran, N. Variyam
8 Ambos-Spies, Klaus
8 Glaßer, Christian
8 Hemaspaandra, Edith
7 Das, Bireswar
7 Hirsch, Edward A.
7 Ko, Ker-I
7 Wagner, Klaus W.
6 Downey, Rodney Graham
6 Regan, Kenneth W.
5 Beyersdorff, Olaf
5 Cai, Jin-Yi
5 Cintioli, Patrizio
5 Faliszewski, Piotr
5 Fortnow, Lance J.
5 Homer, Steven
5 Jenner, Birgit
5 Long, Timothy J.
5 Lutz, Jack H.
5 Selivanov, Viktor L’vovich
5 Silvestri, Riccardo
5 Spakowski, Holger
5 Thierauf, Thomas
4 Chen, Jian-er
4 Du, Ding-Zhu
4 Fomin, Fedor V.
4 Fu, Bin
4 Gasarch, William Ian
4 Goldsmith, Judy
4 Mayordomo, Elvira
4 Mundhenk, Martin
4 Nagoya, Takayuki
4 Ogiwara, Mitsunori
4 Rossmanith, Peter
4 Tang, Shouwen
4 Torenvliet, Leen
4 Vollmer, Heribert
4 Yamakami, Tomoyuki
3 Buss, Samuel R.
3 Cucker, Felipe
3 Dantsin, Evgeny
3 Hartmanis, Juris
3 Hermo, Montserrat
3 Hitchcock, John M.
3 Hutter, Frank
3 Iwama, Kazuo
3 Jonsson, Peter A.
3 Joseph, Deborah
3 Kolaitis, Phokion G.
3 Kratsch, Dieter
3 Kurur, Piyush P.
3 Li, Hongzhou
3 Lindauer, Marius
3 Merkle, Wolfgang
3 Müller, Sebastian
3 Nguyen, Danny
3 Niedermeier, Rolf
3 Orponen, Pekka
3 Pak, Igor
3 Schuler, Rainer
3 Schweitzer, Pascal
3 Shen, Haiou
3 Sheu, Ming-Jye
3 Subramani, Krishnan
3 Tamaki, Suguru
3 Terwijn, Sebastiaan A.
3 Thakur, Mayur
3 Travers, Stephen D.
3 Tripathi, Rahul
3 Uehara, Ryuhei
3 Wechsung, Gerd
3 Yamamoto, Masaki
3 Young, Paul Thomas
3 Zachos, Stathis K.
3 Zhang, Hantao
3 Zimand, Marius
2 Amir, Amihood
2 Basu, Saugata
2 Bodlaender, Hans L.
2 Borchert, Bernd
2 Bourgeois, Nicolas
2 Boy de la Tour, Thierry
2 Brueggemann, Tobias
2 Buhrman, Harry
2 Calabro, Chris
...and 491 more Authors
all top 5

Cited in 82 Serials

129 Theoretical Computer Science
47 Journal of Computer and System Sciences
36 Information Processing Letters
29 Information and Computation
27 Mathematical Systems Theory
16 Theory of Computing Systems
15 Discrete Applied Mathematics
13 Algorithmica
13 Computational Complexity
9 Annals of Pure and Applied Logic
9 RAIRO. Informatique Théorique et Applications
7 Artificial Intelligence
6 Annals of Mathematics and Artificial Intelligence
5 Journal of Complexity
5 Mathematical Logic Quarterly (MLQ)
5 RAIRO. Theoretical Informatics and Applications
4 Journal of Discrete Algorithms
3 Acta Informatica
3 Random Structures & Algorithms
3 International Journal of Foundations of Computer Science
3 International Journal of Computer Mathematics
3 Journal of Combinatorial Optimization
3 Mathematics in Computer Science
3 Computer Science Review
2 Discrete Mathematics
2 The Journal of Symbolic Logic
2 Notre Dame Journal of Formal Logic
2 SIAM Journal on Computing
2 Synthese
2 Journal of Automated Reasoning
2 International Journal of Approximate Reasoning
2 SIAM Journal on Discrete Mathematics
2 Journal of Cryptology
2 Archive for Mathematical Logic
2 Journal of Mathematical Sciences (New York)
2 The Bulletin of Symbolic Logic
2 Foundations of Computational Mathematics
1 Computers & Mathematics with Applications
1 Journal of the Franklin Institute
1 Journal of Mathematical Physics
1 Linear and Multilinear Algebra
1 Problems of Information Transmission
1 Mathematics of Computation
1 Computing
1 Journal of Algebra
1 Journal of Combinatorial Theory. Series A
1 Journal of Graph Theory
1 Journal of Mathematical Psychology
1 Mathematics of Operations Research
1 Networks
1 Combinatorica
1 Acta Mathematicae Applicatae Sinica. English Series
1 Journal of Symbolic Computation
1 Probability Theory and Related Fields
1 Journal of Computer Science and Technology
1 Discrete & Computational Geometry
1 Annals of Operations Research
1 Machine Learning
1 Computational Statistics
1 Linear Algebra and its Applications
1 Mathematical Programming. Series A. Series B
1 Foundations of Computing and Decision Sciences
1 Computational Optimization and Applications
1 Formal Methods in System Design
1 The Journal of Artificial Intelligence Research (JAIR)
1 Journal of Heuristics
1 Constraints
1 Journal of Applied Mathematics and Decision Sciences
1 Data Mining and Knowledge Discovery
1 Mathematical and Computer Modelling of Dynamical Systems
1 LMS Journal of Computation and Mathematics
1 Natural Computing
1 Journal of Statistical Mechanics: Theory and Experiment
1 Foundations of Physics
1 Discrete Optimization
1 Optimization Letters
1 Logical Methods in Computer Science
1 Discrete Mathematics, Algorithms and Applications
1 Forum of Mathematics, Sigma
1 ACM Transactions on Computation Theory
1 Mathematics
1 Prikladnaya Diskretnaya Matematika

Citations by Year