Profile
Profile

Prof. Dr. Marek Karpinski

E-mail: marek(at)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
Birthdate: 25.Mar 1948
Mathscinet-Number: 98650

Publications

Academic Career

1970

M.A. in mathematics, Poznan University

1971

M.E.E. in computer science, TU Poznan

1973

PhD in computer science and mathematics, Polish Academy of Sciences Warsaw

1976

Habilitation in computer science and mathematics, Polish Academy of Sciences Warsaw

1989--

C4 professor, Bonn University

Has been doing research and teaching at various universities and research institutes among others in Warsaw, Pittsburgh, Berekeley, 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.

Selected Publications

[1] Marek Karpinski, Alexander Zelikovsky
New approximation algorithms for the Steiner tree problems
J. Comb. Optim. , 1: (1): 47--65
1997
ISSN: 1382-6905
DOI: 10.1023/A:1009758919736
[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
ISSN: 0022-0000
DOI: 10.1006/jcss.1998.1605
[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
ISSN: 0022-0000
DOI: 10.1016/S0022-0000(03)00008-4
[4] Lars Engebretsen, Marek Karpinski
TSP with bounded metrics
J. Comput. System Sci. , 72: (4): 509--546
2006
ISSN: 0022-0000
DOI: 10.1016/j.jcss.2005.12.001
[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
ISSN: 0178-4617
[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. Ivanyos, M. Karpinski, N. Saxena
Deterministic polynomial time algorithms for matrix completion problems
SIAM Journal on Computing , 39: : 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
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1477
[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
ISSN: 1042-9832
[10] P. Berman, M. Karpinski, A. Zelikovsky
A 3/2-approximation algorithm for generalized Steiner tree problems in graphs with edge length 1 and 2
Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), LNCS 6506
2010

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

1995

Max-Planck-Forschungspreis

2004

IHES European Fellowship

2013

Member of the Academia Europaea

Editorships

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

Research Projects and Activities

Principal Investigator in the following international projects:
– ESPRIT BR Working Group – 7097 and 21726 on “Randomized Algorithms, RAND and RAND2”, (Bonn, Edinburgh, Leeds, Lund, Oxford, Paris, Weizmann Institute, Rehovot), (1992--1995) and (1996--1999);
– Volkswagen-Stiftung Project (I/68055) on “Computational Complexity and Efficient Algorithms”, (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, (1993--1997);
– IST BR Project 14036 (RAND-APX) on “Randomness and Approximate Computation”, (Bonn, Edinburgh, Leeds, Lund, Oxford, and Paris), (1998--2004);
– Project PROCOPE 333587 on “Design and Analysis of Randomized Approximation Algorithms for NP-Hard Optimization Problems”, (Bonn, Paris), (2004--2007);
– FP6 Marie Curie Research Training Network in Model Theory (512234), MODNET, (2004--);
– B-IT Research School, University of Bonn and RWTH Aachen, PI of the Research Area “Algorithm Design and Formal Foundations”, (2008--);
– Chair, Steering Committee on International Series of Conferences “Foundamental of Computation Theory” (FCT), (1999--);

Contribution to Research Areas

Research Area G
My research in the RA G evolved around the following main topics:
<br>bullet Rapidly mixing Markov chains and path coupling with stopping times and general MCMC method.
<br>bullet Mixing Time of Glauber Dynamics for sampling colorings.
<br>bullet 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.
Research Area I (until 10/2012)
My research area was focused on general tractability issues of algorithmic game theory and related issues, especially games on networks, rank aggregation, and feedback arc set tournament problems. On the above topics, among other things, we were able to construct the first efficient approximation scheme of the fragile minimization problems including certain constraint forms of rigidity, and correlation clustering problem. More recent results involve design of the best up to now exact algorithms for Feedback Arc Set Tournament, (FAST), Kemeny Rank Aggregation and the Betweenness Tournament problems.
Former Research Area K
The research within that topic was concerned with selected problems of combinatorial optimization, especially the problems of network design and facility location, multicast Steiner Tree problems, general clustering and partitioning problems (related paper: [1]) as well as on the methods for approximating nonlinear Smooth Integer Polynomial Programs (SIPPs) and related optimization problems ([2]). One of the main trusts of our investigations was devoted to the problems of approximation tractability of TSP and Generalized Steiner Tree (GST) problems and getting better approximation ratios for those problems.
My research is planned to be continued on the above topics in the new RA KL.
Former Research Area L
The research within that topic was focused on fundamental problems of computational complexity of exact and approximate computation, the underlying nature of computational feasibility and intractability, and design of efficient approximation algorithms (see related papers: [3], [4], [5]). We focused also on new mathematical paradigms for designing efficient sublinear time approximation algorithms for CSP problems, and also some aspects of algorithmic game theory ([6]). We studied Markov Chain Monte Carlo (MCMC) based algorithms for various counting problems. We studied also the deterministic computation complexity of the well known problem of factoring polynomial over finite field and its intimate connection to the Generalized Riemann Hypothesis (GRH).
This research will be continued on the aforementioned topics in the new RA KL.
Research Area KL
Download Profile