|
|
| |
| 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
|
University of Bonn -> Department of Computer Science -> Chair V | |