[
University of Bonn

Dept. of Computer Science

Chair V

deutsche Version
]
Professor Marek Karpinski
or at the lectures
Contact:

Address:

Department of Computer Science and
Hausdorff Center for Mathematics,
University of Bonn,
FriedrichEbertAllee 144,
Office: II.63, Secretary: II.62,
53113 Bonn.

Phone and Fax:

+49 (0)228 734224 (office),
+49 (0)228 734327 (secretary),
+49 (0)228 734440 (fax).

Electronic mail:

marek@cs.unibonn.de
Research overview:
Professor Karpinski's research interests are in the design of efficient
algorithms, especially randomized and approximate
algorithms, computational molecular biology,
theory of parallel and distributed systems, and the most fundamental
issues of computational complexity and the circuit theory.
Professor Karpinski is also interested in efficient approximation
methods for the geometric and combinatorial optimization problems which appear to be intractable in exact
computation settings.
He is also a Professor at the
Bonn International Graduate School in Mathematics and a founding member of the
Hausdorff Center for Mathematics.
He is also a member of the Universities BIT Research School in Informatics.
Randomized and Approximate Algorithms:
In this area Professor Karpinski is occupied with fundamental questions of
computational complexity, design of randomized and approximate algorithms, organization of parallel and
distributed systems, internet algorithms as well as the resulting problems of
network communication and algorithmic game theory. Additionally, Professor Karpinski is interested in the
problems of geometric VC Dimension and computational learnability, and
computational molecular biology.
Professor Karpinski is also interested in fundamental questions of
randomization as computational resource. For some important
computational problems, it appears now that the randomized or
pseudorandomized algorithms are more efficient than the deterministic ones in
terms of running time, hardware size, circuit depths, etc.. Recently essential
progresses have been made, e.g. the design of efficient approximate algorithms
for various combinatorial and algebraic enumeration and optimization problems. Solutions to
these problems have applications ranging from the algorithms, circuit design
and coding theory to statistic mechanic und quantum theory.
In particular the research topics include:

Design of Efficient Algorithms

Randomized and Approximate Algorithms

Combinatorial and Geometric Optimization

Parallel and Distributed Systems

Complex Networks

Internet Algorithms

Computational Complexity

Mathematical Foundations

VC Dimension and OMinimality

Circuit Theory

Computational Molecular Biology

Algorithmic Game Theory

Efficient Approximation Algorithms

Algebraic Computational Complexity

Algorithmic Learning Theory
Selected Recent Publications:

Polynomial Time Approximation Schemes
for Dense Instances of NPHard Problems,
Proc. 27th ACM STOC (1995), pp. 284293.

On Real Turing Machines that Toss
Coins,
Proc. 27th ACM STOC (1995), pp. 335342.

Polynomial Bounds for VC
Dimension of Sigmoidal Neural Networks,
Proc. 27th ACM STOC (1995), pp. 200208.

Lower Time Bounds for Randomized
Computation,
Proc. 22nd ICALP '95, LNCS Vol. 944, Springer (1995), pp. 183195.

Improved Lower Bound on Testing
Membership to a Polyhedron by Algebraic Decision Trees,
Proc. 36th IEEE FOCS (1995), pp. 258265.

Bounding VC Dimension for Neural Networks:
Progress and Prospects (Invited Lecture),
Proc. EuroColt '95, Lecture Notes in Artificial Intelligence Vol. 904,
Springer (1995), pp. 337341.

Pattern Matching for Strings with Short
Descriptions,
Proc. 6th CPM '95, LNCS Vol. 937, Springer (1995), pp. 205214.

Sequential and Parallel
Subquadratic Work Algorithms for Constructing Approximately Optimal Binary
Search Trees,
Proc. 7th ACMSIAM SODA (1996), pp. 3641.

A Lower Bound for Randomized Algebraic
Decision Trees,
Proc. 28th ACM STOC (1996), pp. 612619;
journal version in Computational Complexity 6 (1997), pp. 357375.

On the Power of Randomized Branching
Programs,
Proc. 28th ICALP (1996), LNCS Vol. 1099, Springer (1996), pp. 348356.

Randomized Efficient Algorithms for
Compressed Strings: the FingerPrint Approach,
Proc. 7th CPM '96, LNCS Vol. 1075, Springer (1996), pp. 3949.

On Randomized versus Deterministic
Computation,
Theoretical Computer Science 154 (1996), pp. 2339.

Polynomial Bounds for VC
Dimension of Sigmoidal and General Pfaffian Neural Networks,
J. Comput. System Sci. 54 (1997), pp. 169176.

Counting Curves and Their
Projections,
Computational Complexity 6 (1997), pp. 6499.

An Exponential Lower Bound on the Size of
Algebraic Decision Trees for the MAX,
Computational Complexity 7 (1998), pp. 193203.

Efficient Approximation Algorithms for
Sparse Polynomials over Finite Fields,
Theoretical Computer Science 157 (1996), pp. 259266.

Computing Additive Complexity of Algebraic
Circuits with Root Extracting,
SIAM J. Computing 27 (1998), pp. 694701.

Short Proofs for Nondivisibility of
Sparse Polynomials under the Extended Rieman Hypothesis,
Fundamenta Informaticae 28 (1996), pp. 297301.

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

Randomization and the Computational
Power of Analytic and Algebraic Decison Trees,
Computational Complexity 6 (1997), pp. 376388.

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

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

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

On the Complexity of Pattern Matching
for Highly Compressed TwoDimensional Texts,
Proc. 8th CPM '97, LNCS Vol. 1264, Springer (1997), pp. 4051;
also in J. Comput. Syst. Sci. 65 (2002), pp. 332350.

An Approximation Algorithm for the Bandwidth
Problem on Dense Graphs,
Proc. RALCOM'97, Santorini, 1997, pp. 114; also in ECCC TR97017 (1997).

OnLine Load Balancing for Related
Machines,
Proc. 5th WADS '97, LNCS Vol. 1272, Springer (1997), pp. 116125;
also in J. Algorithms 35 (2000), pp. 108121.

Polynomial Time Approximation Schemes
for Some Dense Instances of NPHard Optimization Problems,
Proc. 1st Symp. on Randomization and Approximation Techniques in Computer
Science, RANDOM '97, Bologna;
invited paper, LNCS Vol. 1269, Springer (1997), pp. 114.

On Approximation Hardness of the Bandwidth Problem
on Dense Graphs,
ECCC TR97041(1997).

On a Sublinear Time Parallel
Construction of Optimal Binary Search Tree,
Parallel Processing Letters 8 (1998), pp. 387397.

Simulating Threshold Circuits by Majority
Circuits,
SIAM J. Computing 27 (1998), pp. 230246.

An Exponential Lower Bound for Depth 3
Arithmetic Circuits,
Proc. 30th ACM STOC (1998), pp. 577582.

On Approximation Intractability of the Bandwidth
Problem,
ECCC TR98014 (1998)

On the Computational Power of Randomized Branching
Programs,
Proc. Randomized Algorithms 1998, Brno, pp. 112.

A Generalization of Wilkie's Theorem of the
Complement, and an Application to Pfaffian Closure,
Selecta Mathematica 5 (1999), pp. 110.

On the Computational Hardness
of Testing SquareFreeness of Sparse Polynomials,
Proc. 13th AAECC 1999, LNCS Vol. 1719, Springer (1999), pp. 492497.

A Note on Las Vegas OBDDs,
ECCC TR99009 (1999).

Polynomial Time Approximation Schemes
for Dense Instances of NPhard Problems,
J. Comput. System Sci. 58 (1999), pp. 193210.

Randomized Complexity of Linear
Arrangements and Polyhedra,
Proc. 12th FCT, LNCS Vol. 1684, Springer (1999), pp. 112.

On Some Tighter Inapproximability
Results,
Preliminary version appeared in ECCC TR98065;
also in Proc. 26th ICALP (1999), LNCS Vol. 1644, Springer (1999), pp. 200209.

On the
Approximation Hardness of Dense TSP and other Path Problems,
Information Processing Letters 70 (1999), pp. 5355.

Zero Testing of padic and Modular Polynomials,
Theoretical Computer Science 233 (2000), pp. 309317.

Online
Load Balancing for Related Machines,
J. of Algorithms 35 (2000), pp. 108121.

Improved
Approximation of MAXCUT on Graphs of Bounded Degree,
ECCC TR00021 (2000);
also in J. of Algorithms 43 (2002), pp. 201219.

Approximation
Hardness of TSP with Bounded Metrics,
ECCC TR00089 (2000);
also in Proc. 28th ICALP (2001), LNCS Vol. 2076, Springer (2001), pp. 201212.

Approximability
of Dense Instances of NEAREST CODEWORD Problem,
ECCC TR00091 (2000);
also in Proc. 8th Scandinavian Workshop of Algorithm Theory (2002), LNCS Vol. 2368,
Springer (2002), pp. 298307.

Polynomial
Time Approximation of Dense Weighted Instances of MAXCUT,
Random Structures and Algorithms 8 (2000), pp. 314332.

Approximation
Hardness of Bounded Degree MINCSP and MINBISECTION,
ECCC TR01026 (2001);
also in Proc. 29th ICALP (2002), LNCS Vol. 2380, Springer (2002), pp. 623632.

Polynomial Time Approximation Schemes for Some
Dense Instances of NPHard Problems,
Algorithmica 30 (2001), pp. 386397.

Polynomial
Time Approximation Schemes for MAXBISECTION on Planar and Geometric Graphs,
Proc. 18th STACS '01, LNCS Vol. 2010, Springer (2001), pp. 365375.

Approximating Bounded Degree Instances of
NPHard Problems,
Proc. 13th FCT'01, LNCS Vol. 2138, Springer (2001), pp. 2434.

A Note on
Approximating MAXBISECTION on Regular Graphs,
Information Processing Letters 79 (2001), pp.181188.

Approximating
Minimum Unsatisfiability of Linear Equations,
Proc. 13th ACMSIAM SODA (2002), pp. 514516.

Approximability of Dense and Sparse Instances of
Minimum 2Connectivity, TSP and Path Problems,
Proc. 13th ACMSIAM SODA (2002), pp. 7483.

Randomized Splay Trees: Theoretical and Experimental
Results,
Information Processing Letters 81 (2002), pp. 213221.

Random
Sampling and Approximation of MAXCSP Problems,
Proc. 34th ACM STOC (2002), pp. 232239; also in J. Comput. System Sci. 67 (2003), pp. 212243.

A Lower Bound for Integer Multiplication on Randomized
ReadOnce Branching Programs,
Information and Computation 186 (2003), pp. 7889.

Approximation Schemes for Clustering
Problems,
Proc. 35th ACM STOC (2003), pp. 5058.

A WorkEfficient
Algorithm for Constructing Huffman Codes,
Parallel Processing Letters 14 (2004), pp. 99105.

Approximation Schemes for Metric Bisection and
Partitioning,
Proc. 15th ACMSIAM SODA (2004), pp. 506515.

Approximation
Algorithms for MAXBISECTION on Low Degree Regular Graphs,
Fundamenta Informaticae 62 (2004), pp. 369374.

Improved Approximation Algorithms for the Quality of
Service Multicast Tree Problem,
Algorithmica 42 (2005), pp. 109120.

Tensor
Decomposition and Approximation Schemes for Constraint Satisfaction Problems,
Proc. 37th ACM STOC (2005), pp. 747754.

Path Coupling
Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs,
Proc. 15th FCT (2005), LNCS Vol. 3623, Springer (2005), pp. 1931.

Predecessor
Queries in Constant Time,
Proc. 13th ESA (2005), LNCS Vol. 3669, Springer (2005), pp. 238248.

On the
Computational Power of Probabilistic and Quantum Branching Programs,
Information and Computation 203 (2005), pp. 145162.

TSP with Bounded Metrics,
J. Comput. System Sci. 72 (2006), pp. 509546.

8/7Approximation Algorithm for (1,2)TSP,
Proc. 17th ACMSIAM SODA (2006), pp. 641648.

Algorithms for Construction of Optimal and AlmostOptimal LengthRestricted Codes,
Parallel Processing Letters 16 (2006), pp. 8192.

Stopping Times, Metrics and Approximate Counting,
Proc. 33rd ICALP (2006), pp. 108119.

Optimal TradeOff for Merkle Tree Traversal,
Theoretical Computer Science 372 (2007), pp. 2636.

Computational Complexity of Some Restricted Instances of 3SAT,
Discrete Applied Mathematics 155 (2007), pp. 649653.

Approximating Huffman Codes in Parallel,
ACM J. of Discrete Algorithms 5 (2007), pp. 479490.

Embedding Point Sets into Plane Graphs of Small Dilation,
Int. J. of Geometry and Applications 17 (2007).

Path Coupling Using Stopping Times and Counting Independent Sets and Colorings in Hypergraphs,
Random Structures and Algorithms 32 (2008), pp. 375399.

Schemes for Deterministic Polynomial Factoring,
Proc. 34th ISSAC (2009), pp.191198.

Searching for Frequent Colors in Rectangles,
Proc. 20th CCGG (2008), pp. 1114.

SpaceEfficient MultiDimensional Range Reporting,
Proc. 15th COCOON (2009), pp. 215224.

1.25Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2,
Proc. 11th WADS (2009), pp. 8697.

A Fast Algorithm for Adaptive Prefix Coding,
Algorithmica 55 (2009), pp. 2941.

Approximating Transitive Reductions for Directed Networks,
Proc. 11th WADS (2009), pp. 7485.

The Complexity of Perfect Matching Problems on Dense Hypergraphs,
Proc. 20th ISAAC (2009), pp. 626636.

Linear Time Approximation Schemes for the GaleBerlekamp Game and Related Minimization Problems,
Proc. 41st ACM STOC (2009), pp. 313322.

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems,
Computing Research Repository (CoRR), arXiv:0911.2214, 2009.

Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs,
Proc. 9th LATIN (2010), pp. 662673.

The Mixing Time of Glauber Dynamics for Colouring Regular Trees,
Random Structures and Algorithms 36 (2010), pp. 464476.

Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament,
Proc. 21st ISAAC (2010), pp. 314.

Approximating Subdense Instances of Covering Problems,
Proc. 6th LAGOS (2011), pp. 5965.

Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density,
Int. J. of Foundations of Computer Science 21 (2010), pp. 905924.

Approximating Vertex Cover in Dense Hypergraphs,
Computing Research Repository (CoRR), arXiv:1012.2573, 2010.

TopK Color Queries for Document Retrieval,
Proc. 22nd ACMSIAM SODA (2011), pp. 401411.

Tight Approximation Bounds for Vertex Cover on Dense kPartite Hypergraphs,
Computing Research Repository (CoRR), arXiv:1107.2000, 2011.

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems,
Proc. 14th APPROX (2011), LNCS 6845, pp. 277288.

Improved Lower Bounds for the Shortest Superstring and Related Problems,
Computing Research Repository (CoRR), arXiv:1111.5442, 2011.

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241),
Dagstuhl Reports, 1(6), pp. 2453, 2011.

Trading GRH for Algebra: Algorithms for Factoring Polynomials and Related Structures,
Math. Comput. 81, pp. 493531, 2012.

On Approximation Lower Bounds for TSP with Bounded Metrics,
Computing Research Repository (CoRR), arXiv:1201.5821, 2012.

Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations,
Computing Research Repository (CoRR), arXiv:1210.2698, 2012.

Optimal Cuts and Partitions in Tree Metrics in Polynomial Time,
Computing Research Repository (CoRR), arXiv:1212.3471, 2012; also in
Information Processing Letters 113 (2013), pp. 447451.

Inapproximability of Dominating Set in Power Law Graphs,
Computing Research Repository (CoRR), arXiv:1212.3517, 2012.

Approximate Counting of Matchings in Sparse Uniform Hypergraphs,
Proc. 13th SIAM ANALCO (2013), pp. 7178.

Algorithmic
Perspectives on Network Transitive Preduction Problems and
Their Applications, submitted to the Special Issue on
Developments in Bioinformatic Algorithms, 2012.

Improved Inapproximability Results for the Shortest Superstring and Related Problems,
Proc. 19th CATS (2013), CRPIT 141, pp. 2736.

New Inapproximability Bounds for TSP,
Computing Research Repository (CoRR), arXiv:1303.6437, March 2013.

Approximation Hardness of Graphic TSP on Cubic Graphs ,
Computing Research Repository (CoRR), arXiv:1304.6800, April 2013.

Approximate Counting of Matchings in (3, 3)Hypergraphs,
Proc. 14th SWAT (2014), Volume 8503 of LNCS, pp 380391.

Generalized Wong Sequences and Their Applications to Edmonds' Problems,
Proc. 31th STACS (2014), pp 397408.

Limits of CSP Problems and Efficient Parameter Testing,
Computing Research Repository (CoRR), arXiv:1406.3514, June 2014.

Complexity of Nondeterministic Graph Parameter Testing,
Computing Research Repository (CoRR), arXiv:1408.3590, August 2014.

A QPTAS for the Base of the Number of Triangulations of a Planar Point Set,
Computing Research Repository (CoRR), arXiv:1411.0544, November 2014.

Inapproximability of dominating set on power law graphs,
Theoretical Computer Science 562, pp 436452. January 2015.

Polynomial Interpolation and Identity Testing from High Powers over Finite Fields ,
Computing Research Repository (CoRR), arXiv:1502.06631, February 2015.

A QPTAS for the Base of the Number of CrossingFree Structures on a Planar Point Set,
CSReports, February 2015.

On the Approximability of Independent Set Problem on Power Law Graphs ,
Computing Research Repository (CoRR), arXiv:1503.02880, March 2015.

On the Complexity of Nondeterministically Testable Hypergraph Parameters,
Computing Research Repository (CoRR), arXiv:1503.07093, March 2015.

Approximation hardness of graphic TSP on cubic graphs,
RAIROOperations Research 49(4), pp 651668, March 2015.
URL of this page: http://theory.cs.unibonn.de/~marek/indexen.html
Last updated: March 26th, 2015
Maintained by: webmaster@cs.unibonn.de