|
FORSCHUNGSBERICHT 1999-2001 | INDEX
|
 Institut für Informatik Abteilung für Informatik IV
 Institut für Informatik Abteilung für Informatik VI
|  Forschungsbericht
Mathematisch-Naturwissenschaftliche Fakultät
|
Allgemeine Angaben:
Römerstraße 164, 53117 Bonn
Telefon: 0228 / 73-4327
Fax: 0228 / 73-4440
eMail: marikar@cs.uni-bonn.de
Ablayev F, Gainutdinova A, Karpinski M
On Computational Power of Quantum Branching Programs
Proc. of the 13th Symposium on Fundamentals of Computation Theory,LNCS 2138(2001), pp. 59-70
Ambainis A, Bonner R, Freivalds R, Golovkins M, Karpinski M
Quantum finite multitape automata
SOFSEM'99: theory and practice of informatics (Milovy), 340--348, Lecture Notes in Comput. Sci., 1725
Arora S, Karger D, Karpinski M
Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems
J. Comput. System Sci. 58 (1999), pp. 193-210
Berman P, Charikar M, Karpinski M
On-line Load Balancing for Related Machines
J. of Algorithms 35 (2000), pp. 108-121
Berman P, Karpinski M
On Some Tighter Inapproximability Results
Preliminary version appeared in ECCC TR98-065; Also in Proc. 26th ICALP (1999), pp. 200-209
Blum N
Speeding up Dynamic Programming without Omitting any Optimal Solution and some Applications in Molecular Biology,
Journal of Algorithms 35
Blum N
On Parsing LL-Languages
TCS 267
Blum N , Koch R
Greibach Normal Form Transformation, Revisited
Information and Computation 150
Engebretsen L, Karpinski M
Approximation Hardness of TSP with Bounded Metrics,
ECCC TR00-089 (2000), to appear in Proc. 28th ICALP (2001)
Evdokimov S, Karpinski M, Ponomarenko I
On a new High-dimensional Weisfeiler-Lehman Algorithm
J. Algebraic Combin. 10 (1999)
Feige U, Karpinski M, Langberg M
Improved Approximation of MAX-CUT on Graphs of Bounded
ECCC TR00-021 (2000), to appear in J. of Algorithms 2002
Fernandez de la Vega W, Karpinski M
On the Approximation Hardness of Dense TSP and other Path Problems
Information Processing Letters 70 (1999), pp. 53-55
Fernandez de la Vega W, Karpinski M
Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
Random Structures and Algorithms 8 (2000), pp. 314-332
Freivalds R, Karpinski M, Smith C H, Wiehagen R
Learning by the Process of Elimination
Information and Computation, 171 (2001)
Jansen K, Karpinski M, Lingas A, Seidel E
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
Proc. STACS '01, LNCS
Karpinski M
Randomized Complexity of Linear Arrangements and Polyhedra
Proc. 12th FCT (1999), pp. 1-12
Karpinski M
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems
Algorithmica 30 (2001), pp. 386-397
Karpinski M
Approximating Bounded Degree Instances of NP-Hard Problems
Proc. 13th Symp. on Fundamentals of Computation Theory, FCT'01, LNCS 2138 (2001), pp.24-34.
Karpinski M, Macintyre A
A Generalization of Wilkie's Theorem of the Complement, and an Application to Pfaffian Closure
Selecta Mathematica 5 (1999), pp. 1-10
Karpinski M, Macintyre A
Approximating Volumes and Integrals in o-minimal and p-minimal Theories
Quaderni Mathematica, 6(2000), pp. 149-177
Karpinski M, Mubarakzjanov R
A Note on Las Vegas OBDDs
ECCC TR99-009
Karpinski M, Shparlinski I
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials
Proc. AAECC (1999), pp. 492-497
Karpinski M, van der Poorten A, Shparlinski I
Zero Testing of p-adic and Modular Polynomials
Theoretical Computer Science, 233 (2000), pp. 309-317
Nekritch Y
Decoding of Canonical Huffman Codes with Look-Up Tables
Data Compression Conference 2000, 28-30 March
Nekritch Y
Byte-oriented Decoding of Canonical Huffman Codes
IEEE International Symposium on Information Theory
Nekritch Y
Image Compression by Local Choice of Compression Method
Signal and Image Processing Conference
Rick C
Efficient Computation of All Longest Common Subsequences
Lecture Notes in Computer Science, Vol. 1851
Rick C
Simple and Fast Linear Space Computation of Longest Common Subsequences,
Information Processing Letters, Vol. 75/6
| eMail: Transfer und Öffentlichkeitsarbeit |
|