[
Universität Bonn
|
Institut für Informatik
|
Abt. V
|
english version
]
Professor Marek Karpinski
or at the lectures
Kontakt:
-
Postanschrift:
-
Institut für Informatik und
Hausdorff Center for Mathematics,
Lab for Foundations of Computing,
Universität Bonn,
Friedrich-Hirzebruch-Allee 5,
53115 Bonn.
-
Besucher:
-
Friedrich-Hirzebruch-Allee 8,
Büro: 2.069, Sekretariat: 2.056,
-
-
Telefon und Fax:
-
+49 (0)228 73-4224 (Büro),
+49 (0)228 73-4327 (Sekretariat),
+49 (0)228 73-4440 (Fax).
-
Electronic mail:
-
marek@cs.uni-bonn.de
Forschungsüberblick:
Professor Karpinskis Forschungsinteressen liegen im Entwurf effizienter
Algorithmen, besonders bei randomisierten und
approximativen Algorithmen, in der algorithmischen molekularen Bioinformatik, bei der Theorie von parallelen und verteilten
Systemen und den fundamentalen Fragen der
Berechnungskomplexität und der Schaltkreistheorie.
Professor Karpinski beschäftigt sich auch mit Methoden der effizienten
Approximation für geometrische und kombinatorische Optimierungsprobleme, die sich in exakten
Berechnungsmodellen als besonders hartnäckig erweisen.
Er ist auch Professor an der
Bonner Internationalen Graduierten Schule für Mathematik und ein Gründungsmitglied
des Hausdorff Centers für Mathematik.
Er ist auch Mitglied der B-IT Research School in Informatik.
Randomisierte und approximative Algorithmen:
In diesem Bereich beschäftigt sich Professor Karpinski mit
grundsätzlichen Fragen der Berechnungskomplexität, des Entwurfs approximativer Algorithmen, der
Organisation von parallelen und verteilten Systemen,
Internet-Algorithmen sowie mit dabei
entstehenden Kommunikationsproblemen und algorithmischer
Spieltheorie. Darüber hinaus interessiert sich
Professor Karpinski für Probleme der geometrischen VC-Dimension und
algorithmischen Lerntheorie und der molekularen Bioinformatik.
Professor Karpinski beschäftigt sich auch mit grundsätzlichen
Problemen der Randomisierung (Zufallssteuerung) als
Berechnungsressource. Für einige wichtige Berechnungsprobleme
erscheinen heutzutage randomisierte bzw. pseudo-randomisierte Algorithmen
effizienter als deterministische Algorithmen in Bezug auf Laufzeit,
Hardware-Größe, Schaltkreistiefe, usw. Hier hat man in letzter Zeit
wesentliche Fortschritte erzielt, z.B. im Entwurf von effizienten
Approximationsalgorithmen für verschiedene kombinatorische und algebraische
Zähl- und Optimierungsprobleme. Lösungen zu solchen Problemen haben einen breiten
Anwendungsbereich, der von Algorithmen über Schaltkreisentwurf und
Codierungstheorie bis hin zur statistischen Mechanik und Quantentheorie reicht.
Die einzelnen Forschungsthemen sind:
-
Entwurf effizienter Algorithmen
-
Randomisierte und approximative Algorithmen
-
Kombinatorische und Geometrische Optimierung
-
Parallele und verteilte Systeme
-
Komplexe Netzwerke
-
Internet-Algorithmen
-
Berechnungskomplexität
-
Mathematische Grundlagen
-
VC-Dimension und O-Minimality
-
Schaltkreistheorie
-
Algorithmen in Molekularer Bioinformatik
-
Algorithmische Spieltheorie
-
Effiziente Approximationsalgorithmen
-
Algebraische Berechnungskomplexität
-
Algorithmische Lerntheorie
Ausgewählte Veröffentlichungen:
-
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.
The most recent publications are to be v
found at the HCM address
https://www.hcm.uni-bonn.de/people/faculty/publications/?tx_sevenpack_pi1%5Bauthor%5D=67&tx_sevenpack_pi1%5BbackPageId%5D=239.
URL dieser Seite: https://theory.cs.uni-bonn.de/marek/index-ge.html
Letzte Änderung: 1.10.2018
Verantwortlich: webmaster@cs.uni-bonn.de