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

Professor Marek Karpinski

Contact:

Postal address:

Department of Computer Science and
Hausdorff Center for Mathematics,
Lab for Foundations of Computing,
University of Bonn,
Friedrich-Hirzebruch-Allee 5,
53115 Bonn.

Visitor address:

Friedrich-Hirzebruch-Allee 8,
53115 Bonn.
Office: 2.069, Secretary: 2.056,

Phone and Fax:

+49 (0)228 73-4224 (office),
+49 (0)228 73-4327 (secretary),
+49 (0)228 73-4440 (fax).

Electronic mail:

marek@cs.uni-bonn.de

Short Bio

Short CV

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 B-IT 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 pseudo-randomized 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 O-Minimality
• 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 NP-Hard Problems,
  Proc. 27th ACM STOC (1995), pp. 284-293.
• On Real Turing Machines that Toss Coins,
  Proc. 27th ACM STOC (1995), pp. 335-342.
• Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks,
  Proc. 27th ACM STOC (1995), pp. 200-208.
• Lower Time Bounds for Randomized Computation,
  Proc. 22nd ICALP '95, LNCS Vol. 944, Springer (1995), pp. 183-195.
• Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees,
  Proc. 36th IEEE FOCS (1995), pp. 258-265.
• Bounding VC Dimension for Neural Networks: Progress and Prospects (Invited Lecture),
  Proc. EuroColt '95, Lecture Notes in Artificial Intelligence Vol. 904, Springer (1995), pp. 337-341.
• Pattern Matching for Strings with Short Descriptions,
  Proc. 6th CPM '95, LNCS Vol. 937, Springer (1995), pp. 205-214.
• Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees,
  Proc. 7th ACM-SIAM SODA (1996), pp. 36-41.
• A Lower Bound for Randomized Algebraic Decision Trees,
  Proc. 28th ACM STOC (1996), pp. 612-619; journal version in Computational Complexity 6 (1997), pp. 357-375.
• On the Power of Randomized Branching Programs,
  Proc. 28th ICALP (1996), LNCS Vol. 1099, Springer (1996), pp. 348-356.
• Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach,
  Proc. 7th CPM '96, LNCS Vol. 1075, Springer (1996), pp. 39-49.
• On Randomized versus Deterministic Computation,
  Theoretical Computer Science 154 (1996), pp. 23-39.
• Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks,
  J. Comput. System Sci. 54 (1997), pp. 169-176.
• Counting Curves and Their Projections,
  Computational Complexity 6 (1997), pp. 64-99.
• An Exponential Lower Bound on the Size of Algebraic Decision Trees for the MAX,
  Computational Complexity 7 (1998), pp. 193-203.
• Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields,
  Theoretical Computer Science 157 (1996), pp. 259-266.
• Computing Additive Complexity of Algebraic Circuits with Root Extracting,
  SIAM J. Computing 27 (1998), pp. 694-701.
• Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Rieman Hypothesis,
  Fundamenta Informaticae 28 (1996), pp. 297-301.
• New Approximation Algorithms for the Steiner Tree Problems,
  J. of Combinatorial Optimization 1 (1997), pp. 1-19.
• Randomization and the Computational Power of Analytic and Algebraic Decison Trees,
  Computational Complexity 6 (1997), pp. 376-388.
• Approximating Dense Cases of Covering Problems,
  Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, Princeton, 1997, pp. 169-178.
• Randomized $\Omega (n^2)$ Lower Bound for Knapsack,
  Proc. 29th ACM STOC (1997), pp. 76-85.
• Polynomial Time Algorithms for Modules over Finite Dimensional Algebras ,
  Proc. ACM Symp. ISSAC '97, pp. 68-74.
• On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts,
  Proc. 8th CPM '97, LNCS Vol. 1264, Springer (1997), pp. 40-51; also in J. Comput. Syst. Sci. 65 (2002), pp. 332-350.
• An Approximation Algorithm for the Bandwidth Problem on Dense Graphs,
  Proc. RALCOM'97, Santorini, 1997, pp. 1-14; also in ECCC TR97-017 (1997).
• On-Line Load Balancing for Related Machines,
  Proc. 5th WADS '97, LNCS Vol. 1272, Springer (1997), pp. 116-125; also in J. Algorithms 35 (2000), pp. 108-121.
• Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems,
  Proc. 1st Symp. on Randomization and Approximation Techniques in Computer Science, RANDOM '97, Bologna; invited paper, LNCS Vol. 1269, Springer (1997), pp. 1-14.
• On Approximation Hardness of the Bandwidth Problem on Dense Graphs,
  ECCC TR97-041(1997).
• On a Sublinear Time Parallel Construction of Optimal Binary Search Tree,
  Parallel Processing Letters 8 (1998), pp. 387-397.
• Simulating Threshold Circuits by Majority Circuits,
  SIAM J. Computing 27 (1998), pp. 230-246.
• An Exponential Lower Bound for Depth 3 Arithmetic Circuits,
  Proc. 30th ACM STOC (1998), pp. 577-582.
• On Approximation Intractability of the Bandwidth Problem,
  ECCC TR98-014 (1998)
• On the Computational Power of Randomized Branching Programs,
  Proc. Randomized Algorithms 1998, Brno, pp. 1-12.
• A Generalization of Wilkie's Theorem of the Complement, and an Application to Pfaffian Closure,
  Selecta Mathematica 5 (1999), pp. 1-10.
• On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials,
  Proc. 13th AAECC 1999, LNCS Vol. 1719, Springer (1999), pp. 492-497.
• A Note on Las Vegas OBDDs,
  ECCC TR99-009 (1999).
• Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems,
  J. Comput. System Sci. 58 (1999), pp. 193-210.
• Randomized Complexity of Linear Arrangements and Polyhedra,
  Proc. 12th FCT, LNCS Vol. 1684, Springer (1999), pp. 1-12.
• On Some Tighter Inapproximability Results,
  Preliminary version appeared in ECCC TR98-065; also in Proc. 26th ICALP (1999), LNCS Vol. 1644, Springer (1999), pp. 200-209.
• On the Approximation Hardness of Dense TSP and other Path Problems,
  Information Processing Letters 70 (1999), pp. 53-55.
• Zero Testing of p-adic and Modular Polynomials,
  Theoretical Computer Science 233 (2000), pp. 309-317.
• On-line Load Balancing for Related Machines,
  J. of Algorithms 35 (2000), pp. 108-121.
• Improved Approximation of MAX-CUT on Graphs of Bounded Degree,
  ECCC TR00-021 (2000); also in J. of Algorithms 43 (2002), pp. 201-219.
• Approximation Hardness of TSP with Bounded Metrics,
  ECCC TR00-089 (2000); also in Proc. 28th ICALP (2001), LNCS Vol. 2076, Springer (2001), pp. 201-212.
• Approximability of Dense Instances of NEAREST CODEWORD Problem,
  ECCC TR00-091 (2000); also in Proc. 8th Scandinavian Workshop of Algorithm Theory (2002), LNCS Vol. 2368, Springer (2002), pp. 298-307.
• Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT,
  Random Structures and Algorithms 8 (2000), pp. 314-332.
• Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION,
  ECCC TR01-026 (2001); also in Proc. 29th ICALP (2002), LNCS Vol. 2380, Springer (2002), pp. 623-632.
• Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems,
  Algorithmica 30 (2001), pp. 386-397.
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs,
  Proc. 18th STACS '01, LNCS Vol. 2010, Springer (2001), pp. 365-375.
• Approximating Bounded Degree Instances of NP-Hard Problems,
  Proc. 13th FCT'01, LNCS Vol. 2138, Springer (2001), pp. 24-34.
• A Note on Approximating MAX-BISECTION on Regular Graphs,
  Information Processing Letters 79 (2001), pp.181-188.
• Approximating Minimum Unsatisfiability of Linear Equations,
  Proc. 13th ACM-SIAM SODA (2002), pp. 514-516.
• Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems,
  Proc. 13th ACM-SIAM SODA (2002), pp. 74-83.
• Randomized Splay Trees: Theoretical and Experimental Results,
  Information Processing Letters 81 (2002), pp. 213-221.
• Random Sampling and Approximation of MAX-CSP Problems,
  Proc. 34th ACM STOC (2002), pp. 232-239; also in J. Comput. System Sci. 67 (2003), pp. 212-243.
• A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs,
  Information and Computation 186 (2003), pp. 78-89.
• Approximation Schemes for Clustering Problems,
  Proc. 35th ACM STOC (2003), pp. 50-58.
• A Work-Efficient Algorithm for Constructing Huffman Codes,
  Parallel Processing Letters 14 (2004), pp. 99-105.
• Approximation Schemes for Metric Bisection and Partitioning,
  Proc. 15th ACM-SIAM SODA (2004), pp. 506-515.
• Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs,
  Fundamenta Informaticae 62 (2004), pp. 369-374.
• Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem,
  Algorithmica 42 (2005), pp. 109-120.
• Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems,
  Proc. 37th ACM STOC (2005), pp. 747-754.
• Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs,
  Proc. 15th FCT (2005), LNCS Vol. 3623, Springer (2005), pp. 19-31.
• Predecessor Queries in Constant Time,
  Proc. 13th ESA (2005), LNCS Vol. 3669, Springer (2005), pp. 238-248.
• On the Computational Power of Probabilistic and Quantum Branching Programs,
  Information and Computation 203 (2005), pp. 145-162.
• TSP with Bounded Metrics,
  J. Comput. System Sci. 72 (2006), pp. 509-546.
• 8/7-Approximation Algorithm for (1,2)-TSP,
  Proc. 17th ACM-SIAM SODA (2006), pp. 641-648.
• Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes,
  Parallel Processing Letters 16 (2006), pp. 81-92.
• Stopping Times, Metrics and Approximate Counting,
  Proc. 33rd ICALP (2006), pp. 108-119.
• Optimal Trade-Off for Merkle Tree Traversal,
  Theoretical Computer Science 372 (2007), pp. 26-36.
• Computational Complexity of Some Restricted Instances of 3SAT,
  Discrete Applied Mathematics 155 (2007), pp. 649-653.
• Approximating Huffman Codes in Parallel,
  ACM J. of Discrete Algorithms 5 (2007), pp. 479-490.
• 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. 375-399.
• Schemes for Deterministic Polynomial Factoring,
  Proc. 34th ISSAC (2009), pp.191-198.
• Searching for Frequent Colors in Rectangles,
  Proc. 20th CCGG (2008), pp. 11-14.
• Space-Efficient Multi-Dimensional Range Reporting,
  Proc. 15th COCOON (2009), pp. 215-224.
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2,
  Proc. 11th WADS (2009), pp. 86-97.
• A Fast Algorithm for Adaptive Prefix Coding,
  Algorithmica 55 (2009), pp. 29-41.
• Approximating Transitive Reductions for Directed Networks,
  Proc. 11th WADS (2009), pp. 74-85.
• The Complexity of Perfect Matching Problems on Dense Hypergraphs,
  Proc. 20th ISAAC (2009), pp. 626-636.
• Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems,
  Proc. 41st ACM STOC (2009), pp. 313-322.
• 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. 662-673.
• The Mixing Time of Glauber Dynamics for Colouring Regular Trees,
  Random Structures and Algorithms 36 (2010), pp. 464-476.
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament,
  Proc. 21st ISAAC (2010), pp. 3-14.
• Approximating Subdense Instances of Covering Problems,
  Proc. 6th LAGOS (2011), pp. 59-65.
• Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density,
  Int. J. of Foundations of Computer Science 21 (2010), pp. 905-924.
• Approximating Vertex Cover in Dense Hypergraphs,
  Computing Research Repository (CoRR), arXiv:1012.2573, 2010.
• Top-K Color Queries for Document Retrieval,
  Proc. 22nd ACM-SIAM SODA (2011), pp. 401-411.
• Tight Approximation Bounds for Vertex Cover on Dense k-Partite 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. 277-288.
• 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. 24-53, 2011.
• Trading GRH for Algebra: Algorithms for Factoring Polynomials and Related Structures,
  Math. Comput. 81, pp. 493-531, 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. 447-451.
• 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. 71-78.
• 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. 27-36.
• 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 380-391.
• 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 436-452. 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 Crossing-Free Structures on a Planar Point Set,
  Proc. 42nd ICALP (2015), pp 785-796.
• 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.
• Tropical Dominating Sets in Vertex-Coloured Graphs,
  Computing Research Repository (CoRR), arXiv:1503.01008, March 2015.
• Nearly Tight Approximation Bounds for Vertex Cover on Dense k-uniform k-partite Hypergraphs,
  J. Disrete Algorithms (33), pp 49-57, July 2015.
• New Inapproximability Bounds for TSP,
  Journal of Computer and System Sciences, 2015.
• Generalized Wong Sequences and Their Applications to Edmonds' Problems,
  Journal of Computer and System Sciences, 81(7) pp 1373-1386. November 2015.
• Approximation Hardness of Graphic TSP on Cubic Graphs,
  RAIRO-Operations Research 49(4), pp 651-668, 2015.
• Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies,
  Proc. 20th FCT (2015), LNCS 9210:3-11.
• Approximation Complexity of Max-Cut on Power Law Graphs ,
  Computing Research Repository (CoRR), arXiv:1602.08369, February 2016.