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

Professor Marek Karpinski

Contact:

Address:

Department of Computer Science,
University of Bonn,
Römerstr. 164,
53117 Bonn.

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

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.

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.
• The Mixing Time of Glauber Dynamics for Colouring Regular Trees,
  submitted to Random Structures and Algorithms, 2008.
• Searching for Frequent Colors in Rectangles,
  Proc. 20th CCGG (2008), pp. 11-14.
• Space-Efficient Multi-Dimensional Range Reporting,
  Computing Research Repository (CoRR), arXiv:0806.4361, 2008.
• Schemes for Deterministic Polynomial Factoring,
  Computing Research Repository (CoRR), arXiv:0804.1974, 2008.
• Trading GRH for Algebra: Algorithms for Factoring Polynomials and Related Structures,
  Computing Research Repository (CoRR), arXiv:0811.3165, 2008.
• Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems,
  Proc. 41st ACM STOC (2009), pp. 313-322.