Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Chair V

851 Probabilistic NC1-Circuits Equal Probabilistic Polynomial Time
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF] [Abstract]
852 On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF] [Abstract]
853 There is No Polynomial Deterministic Space Simulation of Two-Way Probabilistic Space with a Two-Way Random-Tape Generator
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF] [Abstract]
854 Ont the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes
(Revised Version)

Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF] [Abstract]
855 Matching Problem for Strongly Chordal Graphs is in NC
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
856 Subtree Isomorphism and Bipartite Perfect Matching are Mutually NC-Reducible
Marek Karpinski and Andrzej Lingas
[Download PostScript] [Download PDF] [Abstract]
857 The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC
Dima Yu. Grigoriev, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
858 Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
859 Parallel Complexity for Matching Restricted to Degree Defined Graph Classes
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8510 Randomness, Provability, and the Separation of Monte Carlo Time and Space
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF] [Abstract]
8512 On the Parallel Complexity of Matching for Chordal and Path Graphs
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8513 Fast Parallel Computation of Perfect and Strongly Perfect Elimination Schemes
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8514 The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC
Dima Grigoriev and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8515 Proceedings of the Bonn Workshop on Foundations of Computing (BFC '87)
Marek Karpinski and Volker Strassen
[Download PostScript] [Download PDF] [Abstract]
8516 A Fast Parallel Algorithm for Computing All Maximal Cliques in a Graph and the Related Problems
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8518 Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8519 Efficient Deterministic Interpolation of Multivariate Polynomials over Finite Fields
Michael Clausen, Johannes Grabmeier and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8520 On the Computational Complexity of Quantified Horn Clauses
Marek Karpinski, Hans Kleine-Buening, Peter H. Schmitt
[Download PostScript] [Download PDF] [Abstract]
8521 The Computational Complexity of Graph Problems with Succinct Multigraph Representation
Marek Karpinski and Klaus W. Wagner
[Download PostScript] [Download PDF] [Abstract]
8522 On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields
Michael Clausen, Andreas Dress, Johannes Grabmeier and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8523 Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
Dima Grigoriev, Marek Karpinski and Michael F. Singer
[Download PostScript] [Download PDF] [Abstract]
8524 On the Possibility of Design and the Algorithms for the fast VLSI-Randomness Sources
C. Glowacz, Marek Karpinski and Heinrich Theodor Vierhaus
[Download PostScript] [Download PDF] [Abstract]
8525 Fast Parallel Decomposition by Clique Separators
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8526 A Deterministic Algorithm for Rational Function Interpolation
Dimar Grigoriev and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8527 Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Elias Dahlhaus, Péter Hajnal and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8528 Learning Machine for Probabilistically Describable Concepts
Marek Karpinski and Zbigniew W. Ras
[Download PostScript] [Download PDF] [Abstract]
8529 A Survey of Parallel Algorithms for Sparse Algebraic Interpolation
Thorsten Werther
[Download PostScript] [Download PDF] [Abstract]
8530 Boolean Circuit Complexity of Algebraic Interpolation Problems
Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8531 Efficient Parallel Algorithm for Clique Separator Decomposition
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8532 A Parallel Algorithm for Maximum Matching in Planar Graphs
Elias Dahlhaus, Marek Karpinski and Andrzej Lingas
[Download PostScript] [Download PDF] [Abstract]
8533 An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8534 Fast Parallel Algorithms for the Clique Separator Decomposition
Elias Dahlhaus, Marek Karpinski, Mark Novick
[Download PostScript] [Download PDF] [Abstract]
8535 Learning Read-Once Formulas with Queries
Dana Angluin, Lisa Hellerstein and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8536 An Efficient Parallel Algorithm for the 3MIS Problem
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
8537 VC Dimension and Learnability of Sparse Polynomials and Rational Functions
Marek Karpinski, Thorsten Werther
[Download PostScript] [Download PDF] [Abstract]
8538 The Interpolation Problem for k-Sparse Sums of Eigenfunctions of Operators
Dima Grigoriev, Marek Karpinski and Miachel Singer
[Download PostScript] [Download PDF] [Abstract]
8539 Interpolation of Sparse Rational Functions without Knowing Bounds on Exponents
Dima Y. Grigoriev, Marek Karpinski, Michael Singer
[Download PostScript] [Download PDF] [Abstract]
8540 Mutlivariate Polynomials, Standard Tableaux, and Representations of Symmetric Groups
Michael Clausen
[Download PostScript] [Download PDF] [Abstract]
Last Change: 06/18/13 at 09:29:04
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V