Profile
Profile

Prof. Dr. Marek Karpinski

E-mail: marek(at)cs.uni-bonn.de
Phone: +49 228 73 4224
Fax: +49 228 73 4440
Homepage: http://theory.cs.uni-bonn.de/~marek/
Institute: Hausdorff Center for Mathematics - HCM
Research Areas: Former Research Area L (Leader)
Research Area G
Research Area KL
Research Area I (until 10/2012)
Former Research Area K
Date of birth: 25.Mar 1948

Academic Career

1970

M.A. in Mathematics, Poznan University, Poland

1971

M.E.E. in Computer Science, Technical University Poznan, Poland

1973

PhD in Computer Science and Mathematics, Polish Academy of Sciences, Warsaw, Poland

1976

Habilitation in Computer Science and Mathematics, Polish Academy of Sciences, Warsaw, Poland

Since 1989

Director, Department of Computer Science, University of Bonn

Since 1989

Professor (C4), Department of Computer Science, University of Bonn

He has been doing research and teaching at various universities and research institutes among others in Warsaw, Pittsburgh, Berkeley, Princeton, MIT, Yale, Oxford, Cambridge, Lund, and Paris.

Research Profile

Main research interests are in computational complexity and design of efficient algorithms, especially randomized and approximate algorithms. Further topics in recent research include: Combinatorial and Geometric Optimization, VC Dimension and O-Minimality, Parallel and Distributed Systems, Internet Algorithms, Algorithmic Game Theory, Computational Molecular Biology.

Research Projects and Activities

ESPRIT BR Working Group – 7097 and 21726 on “Randomized Algorithms, RAND and RAND2”
Bonn, Edinburgh, Leeds, Lund, Oxford, Paris, Weizmann Institute, Rehovot
Principal Investigator, 1992 - 1995 and 1996 - 1999

Volkswagen-Stiftung Project (I/68055) on “Computational Complexity and Efficient Algorithms”
Principal Investigator, 1993 – 1998

NSF/ESPRIT BR Project EC-US 030 on “Randomness and Efficient Computation, RAND-REC” (with M. Luby, Berkeley)
Research Sites: Bonn, Berkeley, Edinburgh, Leeds, Lund, Oxford, and Paris
Principal Investigator, 1993 - 1997

IST BR Project 14036 (RAND-APX) on “Randomness and Approximate Computation”
Bonn, Edinburgh, Leeds, Lund, Oxford, and Paris
Principal Investigator, 1998 - 2004

Chair, Steering Committee on International Series of Conferences “Fundamentals of Computation Theory” (FCT)
Principal Investigator, since 1999

Project PROCOPE 333587 on “Design and Analysis of Randomized Approximation Algorithms for NP-Hard Optimization Problems”
Bonn, Paris
Principal Investigator, 2004 - 2007

FP6 Marie Curie Research Training Network in Model Theory (512234), MODNET
Principal Investigator, since 2004

B-IT Research School, University of Bonn and RWTH Aachen, Research Area “Algorithm Design and Formal Foundations”
Principal Investigator and Project leader, since 2008

Contribution to Research Areas

Research Area G
My research in the RA G evolved around the following main topics:
• Rapidly mixing Markov chains and path coupling with stopping times and general MCMC method.
• Mixing Time of Glauber Dynamics for sampling colorings.
• Efficient sampling methods for approximating selected NP-hard problems.
Several new results were obtained on the above topics, among other things, solving hitherto long time open problems in counting independent sets in hypergraphs and tree colorings.

Selected Publications

[1] Marek Karpinski, Alexander Zelikovsky
New approximation algorithms for the Steiner tree problems
J. Comb. Optim. , 1: (1): 47--65
1997
[2] Sanjeev Arora, David Karger, Marek Karpinski
Polynomial time approximation schemes for dense instances of NP-hard problems
J. Comput. System Sci. , 58: (1): 193--210
1999
[3] Noga Alon, W. Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Random sampling and approximation of MAX-CSPs
Special issue on STOC2002 (Montreal, QC)
J. Comput. System Sci. , 67: (2): 212--243
2003
[4] Lars Engebretsen, Marek Karpinski
TSP with bounded metrics
J. Comput. System Sci. , 72: (4): 509--546
2006
[5] M. Karpinski
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
Approximation algorithms for combinatorial optimization problems
Algorithmica , 30: (3): 386--397
2001
[6] M. Karpinski, W. Schudy
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
Proceedings of the 41st ACM Symposium on Theory of Computing (STOC)
2009
[7] Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic polynomial time algorithms for matrix completion problems
SIAM J. Comput. , 39: (8): 3736--3751
2010
[8] Marek Karpinski, Angus Macintyre
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
1st Annual Dagstuhl Seminar on Neural Computing (1994)
J. Comput. System Sci. , 54: (1, part 2): 169--176
1997
[9] Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
The mixing time of Glauber dynamics for coloring regular trees
Random Structures Algorithms , 36: (4): 464--476
2010
[10] Piotr Berman, Marek Karpinski, Alexander Zelikovsky
A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2
Algorithms and computation. Part I
of Lecture Notes in Comput. Sci. : 15--24
Publisher: Springer, Berlin
2010

Publication List

MathSciNet Publication List (external link)

Editorships

• Electronic Colloquium on Computational Complexity (since 1983)
• Fundamenta Informaticae (1994 - 2010)
• Journal of Combinatorial Optimization (since 1995)
• Compendium of NP Optimization Problems (since 1999)

Awards

1974

Prize of the Polish Mathematical Society

1975

Venia Legendi Annual Research Prize

1976

Award of the Polish Academy of Sciences

1980

Special IBM T.J. Watson Research Grant

1982

Humboldt Research Award

1988

Senior Visiting Research Fellow, Merton College, Oxford University, England, UK

1995

Max Planck Research Award

2004

IHES European Fellowship

2013

Member of the Academia Europaea

Download Profile