Uwe Schöning

Q: What Schools Are Affiliated With Uwe Schöning

Uwe Schöning is affiliated with the following schools: University of Ulm, University of Stuttgart

Uwe Schöning's AcademicInfluence.com Rankings

Uwe Schöning

Computer Science

#980

World Rank

#1016

Historical Rank

Theoretical Computer Science

#28

World Rank

#28

Historical Rank

Database

#8061

World Rank

#8402

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Uwe Schöning Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Uwe Schöning is a retired German computer scientist, known for his research in computational complexity theory. Education and career Schöning earned his Ph.D. from the University of Stuttgart in 1981, under the supervision of Wolfram Schwabhäuser. He was a professor in the Institute for Theoretical Informatics at the University of Ulm until his retirement in 2021.

(See a Problem?)

Uwe Schöning's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

The Graph Isomorphism Problem: Its Structural Complexity (1993) (513)
Accuracy of the diagnosis of GORD by questionnaire, physicians and a trial of proton pump inhibitor treatment: the Diamond Study (2010) (285)
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems (1999) (273)
Graph Isomorphism is in the Low Hierarchy (1987) (231)
The Graph Isomorphism Problem (1993) (209)
A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search (2002) (199)
A Low and a High Hierarchy within NP (1983) (151)
Complexity and Structure (1986) (141)
The Difference and Truth-Table Hierarchies for NP (1987) (127)
A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart (2002) (107)
Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break (2012) (102)
A Probabilistic 3-SAT Algorithm Further Improved (2002) (93)
On Circuit-Size Complexity and the Low Hierarchy in NP (1985) (87)
Probabilistic Complexity Classes and Lowness (1989) (84)
A Uniform Approach to Obtain Diagonal Sets in Complexity Classes (1982) (81)
The polynomial-time hierarchy and sparse oracles (1986) (78)
Logic for computer scientists (1989) (76)
Turning machines with few accepting computations and low sets for PP (1989) (74)
Instance complexity (1994) (72)
Sparse Sets, Lowness and Highness (1986) (71)
Reductions to Sets of Low Information Content (1992) (64)
Graph isomorphism is low for PP (1992) (60)
The Density and Complexity of Polynomial Cores for Intractable Sets (1986) (47)
Algorithmics in Exponential Time (2005) (45)
Bi-immune sets for complexity classes (1985) (44)
Immunity, Relativizations, and Nondeterminism (1984) (41)
Optimal Approximations and Polynomially Levelable Sets (1986) (38)
Robust Algorithms: A Different Approach to Oracles (1984) (37)
Gems of Theoretical Computer Science (1998) (37)
Phloem translocation in regenerating in vitro- heterografts of different compatibility (1997) (36)
The power of counting (1988) (36)
Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries (1988) (34)
What Is a Hard Instance of a Computational Problem? (1986) (30)
Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search (2000) (29)
On counting and approximation (1989) (29)
Complexity Cores and Hard Problem Instances (1990) (28)
If NP has Polynomial-Size Circuits, then MA=AM (1995) (28)
Complexity theory: current research (1993) (27)
Complete sets and closeness to complexity classes (1986) (26)
Logarithmic Advice Classes (1992) (26)
On Small Generators (1984) (25)
Complexity of presburger arithmetic with fixed quantifier dimension (1997) (21)
An empirical assessment of local and population based search methods with different degrees of pseudorandomness (2008) (20)
Minimal pairs for P (1984) (18)
On the different notions of pseudorandomness (2008) (18)
The Structure of Polynomial Complexity Cores (Extended Abstract) (1984) (18)
New Algorithms for k -SAT Based on the Local Search Principle (2001) (17)
Structural RNA alignment by multi-objective optimization (2013) (16)
The Priority Method (1998) (15)
Improving Implementation of SLS Solvers for SAT and New Heuristics for k-SAT with Long Clauses (2014) (15)
Smaller superconcentrators of density 28 (2006) (13)
On Bounded Query Machines (1985) (13)
Complexity theory and interaction (1988) (12)
Sparse Oracles and Uniform Complexity Classes (1984) (11)
Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing (2011) (11)
RNA-Pareto: interactive analysis of Pareto-optimal RNA sequence-structure alignments (2013) (10)
Better Expanders and Superconcentrators by Kolmogorov Complexity (1997) (10)
Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity (1997) (10)
The Function of Phloem Connections in Regenerating In Vitro-Grafts* (1995) (10)
Engineering a Lightweight and Efficient Local Search SAT Solver (2016) (10)
Randomized Algorithms for 3-SAT (2007) (10)
On Random Reductions from Sparse Sets to Tally Sets (1993) (9)
An Improved Randomized Algorithm for 3-SAT (2001) (9)
Robust Orale Machines (1988) (9)
Sparse Oracles, Lowness, and Highness (1984) (7)
A note on complete sets for the polynomial-time hierarchy (1981) (7)
Principles of Stochastic Local Search (2007) (6)
A Uniform Circuit Lower Bound for the Permanent (2012) (6)
Construction of expanders and superconcentrators using Kolmogorov complexity (2000) (6)
The Pebble Game (1998) (6)
tRNA-like elements in Haloferax volcanii. (2012) (5)
High Sets for NP (1997) (5)
Recent highlights in structural complexity theory (2009) (5)
Lowness and probabilistic complexity classes (1987) (4)
Complexity Cores and Hard-To-Prove Formulas (1987) (4)
On NP-decomposable sets (1982) (4)
Mastering the Master Theorem (2000) (3)
Randomized Quicksort and the Entropy of the Random Source (2005) (2)
Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems (2010) (2)
On the Dtructure of Deltap2 (1983) (2)
QuickSort from an Information Theoretic View (2009) (2)
Polynomial Levelability and Maximal Complexity Cores (1985) (2)
New Algorithmic Paradigms in Exponential Time Algorithms (2005) (2)
A note on the size of Craig Interpolants (2006) (2)
Spectral Problems and Descriptive Complexity Theory (1998) (1)
Promise Problems on Probability Distributions (2020) (1)
The Complexity of Craig Interpolants (1998) (1)
Randomized Quicksort and the Entropy of the Random Number Generator (2004) (1)
Decision Problems, Search Problems, and Counting Problems (1993) (0)
Structure and Complexity Theory (Dagstuhl Seminar 9206) (2021) (0)
Curved conveyor belt. (2007) (0)
Equivalence Problems and Lower Bounds for Branching Programs (1998) (0)
An Improved Randomized Algorithm for 3-SAT (New Developments of Theory of Computation and Algorithms) (2001) (0)
Ant colony optimization with group learning (2014) (0)
PAC-Learning and Occam’s Razor (1998) (0)
On the complexity of constraint satisfaction (2010) (0)
The BP-Operator and the Power of Counting Classes (1998) (0)
Structure and Complexity (Dagstuhl Seminar 9407) (2021) (0)
Circuit-size complexity (1986) (0)
Quantifiers, Games, and Interactive Proofs (1993) (0)
Information Theoretic Measures for Ant Colony Optimization (2014) (0)
RNA Structures as Processing Signals (2018) (0)
Superconcentrators and the Marriage Theorem (1998) (0)
The Second LBA Problem (1998) (0)
Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers (1998) (0)
Lower Bounds by Recursion Theoretic Arguments (Extended Abstract) (1986) (0)
Lower Bounds via Kolmogorov Complexity (1998) (0)
Fundamental Definitions and Results (1998) (0)
Immunity (Extended Abstract) (1983) (0)
Quantum Search Algorithms (1998) (0)
Lower Bounds for the Parity Function (1998) (0)
P ≠ NP with probability 1 (1998) (0)
The Berman-Hartmanis Conjecture and Sparse Sets (1998) (0)
Using Stochastic Indexed Grammars for RNA Structure PredictionWith Pseudoknots (2010) (0)
Interactive Proofs and Zero Knowledge (1998) (0)
Editor's ForewordEDITOR'S FOREWORD: Special Issue on the 9th Annual Structure in Complexity Theory Conference in Amsterdam, June 28–July 1, 1994 (1996) (0)
Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case (1998) (0)
The low and high hierarchies (1986) (0)
The BP Operator and Graph Isomorphism (1998) (0)
Exponential Lower Bounds for the Length of Resolution Proofs (1998) (0)
Average-Case Complexity (1998) (0)
The Equivalence Problem for LOOP(1)- and LOOP(2)-Programs (1998) (0)
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992 (1993) (0)
The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141) (2021) (0)
LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences (1998) (0)
The Parity Function Again (1998) (0)
Circuits and Sparse Sets (1993) (0)

This paper list is powered by the following services:

Other Resources About Uwe Schöning

en.wikipedia.org

What Schools Are Affiliated With Uwe Schöning?

Uwe Schöning is affiliated with the following schools:

Uwe Schöning's Academic­Influence.com Rankings

Why Is Uwe Schöning Influential?

Uwe Schöning's Published Works

Published Works

Other Resources About Uwe Schöning

What Schools Are Affiliated With Uwe Schöning?

Uwe Schöning's AcademicInfluence.com Rankings