[ University of Bonn | Department of Computer Science | Chair V | deutsche Version ]

ESPRIT Working Group

"Randomized Algorithms"

RAND2 (No. 21726)

(Bonn Site)

Publications 1997

F. Ablayev and M. Karpinski.

On the Power of Randomized Branching Programs,
Research Report No. 85181-CS, University of Bonn, 1997.

F. Ablayev and M. Karpinski.

A Lower Bound for Interger Multiplication on Randomized Read-Once Branching Programs,
Research Report No. 85184-CS, University of Bonn, 1997.

A. Ambainis, K. Aprits, C. Calude, R. Freivalds, M. Karpinski, T. Larfeldt and I. Sala.

Effects of Kolmogorov Complexity Present in Inductive Inference,
Proc. 8th Workshop on Algorithmic Learning Theory, ALT'97.

A. Ambainis, R. Freivalds, and M. Karpinski.

Weak and Strong Recognition by 2-Way Randomized Automata,
Proc. 1st Symp. on Randomization and Approximation Techniques in Computer Science, RANDOM'97, Bologna,
Lecture Notes in Computer Science Vol. 1269, Springer Verlag, 1997, pp. 175 -- 185.

P. Berman, M. Charikar, and M. Karpinski.

On-Line Load Balancing for Related Machines,
Proc. WADS'97, pp. 116 -- 125.

P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter.

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts,
Proc. CPM'97.

G. Blache, M. Karpinski and J. Wirtgen.

On Approximation Intractability of the Bandwidth Problems,
Research Report No. 85182-CS, University of Bonn, 1997.

A. Chistov, G. Ivanyos, and M. Karpinski.

Polynomial Time Algorithms for Modules over Finite Dimensional Algebras,
Proc. ACM Symp. ISSAC'97.

C. Dorgerloh and J. Wirtgen.

Faster Finding of Simple Cycles in Planar Graphs on a randomized EREW-PRAM,
Proc. 2nd Workshop on Randomized Parallel Computing (1997), held in conjunction with IPPS'97.

L. Gasieniec, M. Karpinski, W. Plandowski and W. Rytter.

Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach,
Proc. 7th Annual Symp. on Combinatorial Pattern Matching (1996), pp. 39--49.

J. von zur Gathen, M. Karpinski and I. Shparlinski.

Counting Curves and Their Projections,
Computational Complexity 6 (1997), pp. 64--69.

D. Grigoriev and M. Karpinski.

Randomized $\Omega (n^2)$ Lower Bound for Knapsack,
Proc. 29th ACM STOC (1997), pp. 76--85.

D. Grigoriev, M. Karpinski and R. Smolensky.

Randomizationand the computational Power of Analytic and Algebraic Decision Trees,
to appear in Computational Complexity, 1997.

M. Karpinski.

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems,
Proc. 1st Symp. on Randomization and Approximation Techninques in Computer Science, RANDOM'97 (Invited Paper) Bologna,
Lecture Notes in Computer Science Vol. 1269, Springer Verlag, 1997, pp. 1 -- 14.

M. Karpinski and W. Fernandez de la Vega.

Polynomial Time Approximability of Dense Weighted Instances of MAX-CUT,
Research Report No. 85171-CS, University of Bonn, 1997.

M. Karpinski and A. Macintyre.

Approximating the Volume of General Pfaffian Bodies,
Lecture Notes in Computer Science Vol. 1261 (Special Volume in Honor of A. Ehrenfeucht), Springer Verlag, 1997.

M. Karpinski and A. Macintyre.

Approximating Volumes and Integrals in o-Minimal and p-Minimal Theories,
Research Report No. 85174-CS, University of Bonn, 1997;
submitted to Discrete Comput. Geometry.

M. Karpinski and A. Macintyre.

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks,
J. Comput. Syst. Sciences 54 (1997), pp. 169 -- 176.

M. Karpinski, A. von der Poorten and I. Shparlinski.

Zero Testing of p-adic and Modular Polynomials,
Research Report No. 85175-CS, University of Bonn, 1997;
submitted to Theoretical Computer Science, 1997.

M. Karpinski, W. Rytter, and A. Shinohara.

An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions,
Nordic Journal of Computing 4 (1997), pp. 172 -- 186.

M. Karpinski, and I. Shparlinski.

On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields,
Theoretical Computer Science 157 (1996), pp. 259--266.

M. Karpinski and J. Wirtgen.

NP-Hardness of the Bandwidth Problem on Dense Graphs,
Research Report No. 85176-CS, University of Bonn, 1997.

M. Karpinski, J. Wirtgen, and A. Zelikovsky.

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs,
ECCC Technical Report TR 97-017. Proc. Workshop on Randomized Algorithms in Sequential, Parallel, and Distributed Computing, RALCOM'97, 1997.

M. Karpinski, and A. Zelikovsky.

New Approximation Algorithms for the Steiner Tree Problems,
J. of Combinatorial Optimization 1 (1997), pp. 47--65.

M. Karpinski, and A. Zelikovsky.

Approximating Dense Cases of Covering Problems,
Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, Princeton, 1997.