Gerd Wechsung

According to our database1, Gerd Wechsung
  • authored at least 54 papers between 1972 and 2006.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2006
On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P.
Inf. Process. Lett., 2006

2003
Relativizing Function Classes.
J. UCS, 2003

2002
The Minimization Problem for Boolean Formulas.
SIAM J. Comput., 2002

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.
Theory Comput. Syst., 2002

Reducing the Number of Solutions of NP Functions.
J. Comput. Syst. Sci., 2002

2001
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
CoRR, 2001

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
CoRR, 2001

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

2000
The Operators min and max on the Polynomial Hierarchy.
Int. J. Found. Comput. Sci., 2000

Reducing the Number of Solutions of NP Functions.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999
Robust Reductions.
Theory Comput. Syst., 1999

Self-Specifying Machines.
Int. J. Found. Comput. Sci., 1999

Self-Specifying Machines
CoRR, 1999

Query Order
CoRR, 1999

Easy Sets and Hard Certificate Schemes
CoRR, 1999

Robust Reductions
CoRR, 1999

1998
Query Order.
SIAM J. Comput., 1998

Embedding ladders and caterpillars into the hypercube.
Discrete Applied Mathematics, 1998

Robust Reductions.
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

1997
Time Bounded Frequency Computations.
Inf. Comput., 1997

The Operators min and max on the Polynomial Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1997

Easy Sets and Hard Certificate Schemes.
Acta Inf., 1997

The Operators min and max on the Polynomial Hierarchy.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

The Minimization Problem for Boolean Formulas.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Time Bounded Frequency Computations.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

On Sets with Easy Certificates and the Existence of One-Way Permutations.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1992
New Parallel Algorithms for Convex Hull and Triangulation in 3-Dimensional Space.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

1991
Kolmogorov Characterizations of Complexity Classes.
Theor. Comput. Sci., 1991

Probabilistic Polynomial Time is Closed under Parity Reductions.
Inf. Process. Lett., 1991

1990
A Survey on Counting Classes.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
The Boolean Hierarchy II: Applications.
SIAM J. Comput., 1989

Using Randomness to Characterize the Complexity of Computation.
IFIP Congress, 1989

On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput., 1988

1986
Nondeterministic Turing Machines with Modified Acceptance.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

1985
On Sparse Complete Sets.
Math. Log. Q., 1985

On Sparse Complete Sets.
Elektronische Informationsverarbeitung und Kybernetik, 1985

On the Boolean closure of NP.
Proceedings of the Fundamentals of Computation Theory, 1985

1980
A Note on the Return Complexity.
Elektronische Informationsverarbeitung und Kybernetik, 1980

1979
A Relation Between Space, Return and Dual Return Complexities.
Theor. Comput. Sci., 1979

A Crossing Measure for 2-Tape Turing Machines.
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

The oscillation complexity and a hierarchy of context-free languages.
FCT, 1979

1977
Properties of Complexity Classes: A Short Survey.
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

Complexity Hierarchies of Oracles.
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

A Nonlinear Lower Bound for the Formula Complexity of Certain Boolean Functions.
IFIP Congress, 1977

1976
Kompliziertheitstheoretische Charakterisierung der kontextfreien und linearen Sprachen.
Elektronische Informationsverarbeitung und Kybernetik, 1976

1975
Minimale und optimale Blumsche Maße.
Elektronische Informationsverarbeitung und Kybernetik, 1975

Eine algebraische Charakterisierung der linearen Sprachen.
Elektronische Informationsverarbeitung und Kybernetik, 1975

Characterization of Some Classes of Context-Free Languages in Terms of Complexity Classes.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974
The Axiomatization Problem of a Theory of Linear Languages.
Proceedings of the Mathematical Foundations of Computer Science, 1974

1973
Funktionen, die von pushdown-Automaten berechnet werden.
Acta Cybern., 1973

Eine verbandstheoretische Klassifikation der längentreuen Wortfunktionen.
Acta Cybern., 1973

Quasisequentielle Funktionen.
Acta Cybern., 1973

1972
Die Gruppe der eineindeutigen längentreuen sequentiellen Funktionen.
Elektronische Informationsverarbeitung und Kybernetik, 1972


  Loading...