Uni Logo
 

FORSCHUNGSBERICHT 1996-1998


 

Prev.:Institut für Informatik Abteilung für Informatik IV
Next.:Institut für Informatik - Abt. V Lehrstuhl Prof. Lengauer
Up:Forschungsbericht
Up:Mathematisch-Naturwissenschaftliche Fakultät
Index


Institut für Informatik Abt.für Informatik V

Allgemeine Angaben:
Römerstraße 164, 53117 Bonn, Telefon: 0228 / 73-4327, Telefax: 0228 / 73-4440, eMail: marikar@tcs.uni-bonn.de

Hauptamtliche Professoren
Prof. Dr. Michael Clausen
Prof. Dr. Marek Karpinski
Prof. Dr. Thomas Lengauer

Wissenschaftliches Personal
Universitätsstellen
Priv.-Doz. Elias Dahlhaus
Dr. Carsten Dorgerloh
Dipl.-Inform. Christoph Günzel
Dipl.-Inform. Frank Kurth
Dr. Helga Meier-Reinhold
Dr. Amin Shokrollahi
Dipl.-Inform. Peter Wegner
Dipl.-Inform. Dietmar Wiggerich
Dr. Jürgen Wirtgen

Drittmittelstellen
Dipl.-Inform./Dipl.-Math. Heiko Goeman (DFG)
Dr. Patrick Hamilton (DFG)
Dipl.-Inform. Dirk Meyer (DFG)

Stipendiaten
Dipl.-Ing. Vlora Arifi (DAAD)
Dipl.-Inform. Yakov Nekritch (FES)

Forschungsschwerpunkte
Parallele und verteilte Systeme, On-Line Algorithmen
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Algorithmische Geometrie und VC Dimension
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Approximationsalgorithmen für NP-harte kombinatorische Optimierungsprobleme und Anwendungen
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Berechnungskomplexität, Boolesche Schaltkreise, Branching Programme und VLSI-Entwurf
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Kodierungs- und Dekodierungsalgorithmen für fehlerresistente ATM Systeme
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Schnelle parallele und randomisierte Algorithmen
(Dahlhaus, Dorgerloh, Günzel, Karpinski, Nekritch, Wegner, Wirtgen)

Besondere Forschungsförderung
DFG
(Karpinski, Deutsche Forschungsgemeinschaft, Bonn)

ESPRIT BR RAND2
(Karpinski, European Commission - Bruxelles)

ESPRIT BR/NSF RAND-REC
(Karpinski, European Commission - Bruxelles, National Science Foundation - Washington)

Max-Planck-Forschungspreis
(Karpinski, Max-Planck-Gesellschaft)

PROCOPE
(Karpinski, DAAD - Deutscher Akademischer Austauschdienst)

Volkswagen-Stiftung-Projekt
(Karpinski, Volkswagen-Stiftung)

Veröffentlichungen
Ablayev F, Karpinski M:
''On the Power of Randomized Branching Programs''
Lecture Notes in Computer Science, volume 1099, pp. 348-356. Springer, 1996.

Ablayev F, Karpinski M:
''A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs''
Information and Computation, 1998.

Ablayev F, Karpinski M:
''On the Power of Randomized Ordered Branching Programs''
Journal of Algorithms, 1998.

Ambainis A, Freivalds R, Karpinski M:
''Weak and Strong Recognition by 2-way Randomized Automata''
Lecture Notes in Computer Science, vol. 1269, pp. 175-185. Springer, 1997.

Berman P, Larmore L, Karpinski M, Plandowski W, Rytter W:
''On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts''
Lecture Note in Computer Science, vol. 1264, pp. 40-51. Springer, 1997.

Buhler, J, Crandall, R, Ernvall, R, Metsänkylä, T, Shokrollahi, M A:
''Irregular primes below 8 million''
J. Symb. Comp, 1997.

Bürgisser P, Clausen M, Shokrollahi M A:
''Algebraic Complexity Theory''
Grundlehren der Mathematischen Wissenschaften, vol. 315, Springer Verlag, 1996

Bürgisser, P, Clausen, M:
''Algebraische Komplexitätstheorie I, Eine Einführung''
Proceedings 36. Seminaire Lothringien de Combinatoire, 1996.

Clausen M:
''A direct proof of Minkwitz's extension theorem''
AAECC, vol. 8, pp. 305-306, 1997.

Clausen, M:
''Algebraische Komplexitätstheorie III, Zur Berechnungskomplexität von Permanenten''
Proceedings 36. Seminaire Lothringien de Combinatoire, 1996.

Dahlhaus E, Karpinski M:
''Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs''
Discrete Applied Mathematics, 84:pp. 79-91, 1998.

Fernandez de la Vega W, Karpinski M:
''Polynomial Time Approximability of Dense Weighted Instances of MAX-CUT''
Random Structures and Algorithms, 1997.

Gathen, von zur J, Karpinski M, Shparlinski I:
''Counting Curves and their Projections''
Computational Complexity, 6:pp. 64-99.1996.

Goeman, H:
''On parsing and condensing substrings of {LR} languages in linear time (extended abstract)''
Proc. Third Int. Workshop on Implementing Automata (WIA'98), Rouen, Springer LNCS, 1998.

Goldmann M, Karpinski M:
''Simultating Threshold Circuits by Majority Circuits''
SIAM Journal on Computing, 27:pp. 230 246, 1998.

Grigoriev D, Karpinski M, Odlyzko A:
''Short Proofs for Nondivisibility Polynomials under the Extended Riemann Hypothesis''
Fundamenta Informaticae, 28:pp. 297-301, 1996.

Grigoriev D, Karpinski M, Smolensky R:
''Randomization and the Computational Power of Analytic and Algebraic Decision Trees''
Computational Complexity, 6:pp. 376-388, 1997.

Grigoriev D, Karpinski M, Yao A:
''An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX''
Computational Complexity, 7(3), 1998.

Grigoriev D, Karpinski M:
''Computing the Additive Complexity of Algebraic Circuits with Root Extracting''
SIAM Journal on Computing, 27(3):pp. 694-701, 1998.

Grigoriev D, Meyer auf der Heide F, Karpinski M, Smolensky R:
''A Lower Bound for Randomized Algebraic Decision Trees''
Computational Complexity, 6:pp. 357-375, 1997.

Karpinski M, Larmore L, Rytter W:
''Correctness of Constructing Optimal Alphabetic Trees Revisited''
Theoretical Computer Science, 180:pp. 309-324, 1997.

Karpinski M, Macintyre A:
''Approximating Volumes and Integrals''
Discrete Computational Geometry, 1997.

Karpinski M, Macintyre A:
''Approximating the Volume of General Pfaffian Bodies - Special Volume in Honor of A. Ehrenfeucht''
Lecture Notes in Computer Science, volume 1261, pp. 162-173. Springer, 1997.

Karpinski M, Macintyre A:
''o-Minimal Expansions of the Real Field: a Characterization, and an Application to Pfaffian Closure''
Selecta Mathematica, 1998.

Karpinski M, Rytter W, Shinohara A:
''An Efficient Pattern-Matching Algorithms for Strings with Short Descriptions''
Nordic Journal of Computation, 4:pp. 172-186, 1997.

Karpinski M, Rytter W:
''An Alphabet-Independent Optimal Parallel Search for Three Dimensional Patterns''
Theoretical Computer Science, 205:pp. 243-260, 1998.

Karpinski M, Rytter W:
''Fast Parallel Algorithms for Graph Matching Problems''
Monograph. Oxford University Press, 1998.

Karpinski M, Verbeek R:
''On Randomized versus Deterministic Computation''
Theoretical Computer Science, 154:pp. 23-39, 1996.

Karpinski M, von der Poorten A, Shparlinski I:
''Zero Testing of p-adic and Modular Polynomials''
Theoretical Computer Science, 1998.

Karpinski M, Zelikovsky A:
''New Approximation Algorithms for the Steiner Tree Problems''
Combinatorial Optimization, 1:pp. 47-65, 1997.

Karpinski M:
''On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields''
Theoretical Computer Science, 157:pp 259-266, 1996.

Karpinski M:
''Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees''
Discrete Computational Geometry, 17:pp. 191-215, 1997.

Karpinski M:
''Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems''
Lecture Notes in Computer Science, pp. l1-14.Springer, 1997.

Karpinski M:
"On the Computational Power of Randomized Branching Programs"
Randomized Algorithms, pp. 1-12, 1998.

Karpinski M:
"Randomized OBDDs and the Model Checking"
Probabilistic Methods in Verification, PROBMIV'98, pp. 35-38.

Kurth, F, Clausen, M:
''Filter bank tree and $M$-band wavelet packet algorithms in audio signal processing''
IEEE Transactions on Signal Processing.

Kurth, F, Clausen, M:
''M-Band Wavelet Packets and Filter Bank Trees as Flexible Tools in Audio Signal Processing''
Proc. IEEE WASPAA 97, Mohonk, New Paltz, NY, 1997.

Luby, M, Mitzenmacher, M, Shokrollahi, M A, Spielman, D:
''Analysis of low density codes and improved designs using irregular graphs''
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 249-258, 1998.

Luby, M, Mitzenmacher, M, Shokrollahi, M A, Spielman, D:
''Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation''
Proceedings of the 1998 IEEE International Symposium on Information Theory, p. 117, 1998.

Luby, M, Mitzenmacher, M, Shokrollahi, M A:
''Analysis of random processes via AND/OR tree evaluations''
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 364-373, 1998.

Sander, T, Shokrollahi, M A:
''Deciding properties of polynomials without factoring''
Proceedings of the 28th IEEE Syposium on the Foundations of Computer Science, pp. 46-55, 1997.

Shokrollahi, M A:
''Relative class number of abelian CM-fields of prime conductor below 1000''
Math. Comp., 1998.


Transfer und Öffentlichkeitsarbeit