Marek Karpinski

Marek Karpinski

Marek Karpinski (25 marzo 1948) è un informatico e matematico polacco, noto per la sua ricerca nella teoria degli algoritmi e delle loro applicazioni, ottimizzazione combinatoria, complessità computazionale e fondamenti matematici.

Ha lavorato nel campo della ricerca e di insegnamento in varie università europee ed americane, fra l'altro, in Berkeley, Princeton e Bonn. Ha una grande influenza scientifica, soprattutto nei campi di algoritmi di approssimazione per problemi di ottimizzazione NP-hard, la teoria del VC-dimension (Karpinski-Macintire theorem) così come altre tecniche computazionali di limiti inferiori per diversi modelli computazionali. Ha ricevuto diversi premi di ricerca nei settori sopra menzionati. È stato anche cofondatore delle FCT serie internazionale di conferenze teoriche e fondamentali in informatica così come dei Bonn workshops specializzati sulla teoria della computazione. È stato anche uno dei fondatori e un investigatore principale di gruppi di ricerca internazionali su basi di randomized and approximate computation. È uno dei ricercatori più prolifici e importanti in questi settori.

Attualmente è professore d´informatica e matematica e il capo del gruppo algoritmi e complessità computazionale presso l'Università di Bonn e della sezione algoritmica di Bonn-Aachen Research School. È anche uno dei membri fondatori di Bonn International Graduate School in Mathematics e Hausdorff Center for Mathematics..

Nel 1994 è stato insignito del prestigioso Max Planck Research Price. Nel 2013 è stato eletto alla Academia Europæa, the Academy of Europe.

Bibliografia selezionata

Altre pubblicazioni di Marek Karpinski Scholar Wiki

• N. Alon, W. F. de la Vega, R. Kannan, and M. Karpinski, Random Sampling and Approximation of MAX-CSP Problems, J. Comput. and Syst. Sci. 67 (2003), 212–243., su dl.acm.org.
• S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems, J. Comput. and Syst. Sci. 58 (1999), 193–210., su dl.acm.org.
• M. Bordewich, M. Dyer, and M. Karpinski, Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs ,Random Struct. Algorithms 32 (2008), 375–399., su onlinelibrary.wiley.com.
• L. Engebretsen and M. Karpinski, TSP with Bounded Metrics, J. Comput. System Sci. 72 (2006), 509–546., su sciencedirect.com.
• W. F. de la Vega, R. Kannan, M. Karpinski, and S. Vempala, Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems, Proc. 37th ACM STOC (2005), 747–754., su dl.acm.org.
• G. Ivanyos, M. Karpinski, and N. Saxena, Deterministic Polynomial Time Algorithms for Matrix Completion Problems, SIAM J. Comput. 39 (2010), 3736-3751., su epubs.siam.org.
• M. Karpinski, Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems, Algorithmica 30 (2001), 386–397., su link.springer.com.
• M. Karpinski and A. Macintyre, Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks, J. Comput. Syst. Sci. 54 (1997), 169–176., su sciencedirect.com.
• M. Karpinski and W. Schudy, Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems, Proc. 41st ACM STOC (2009), pp. 313-322., su dl.acm.org.
• M. Karpinski and A. Zelikovsky, New Approximation Algorithms for the Steiner Tree Problems, J. of Comb. Optimization1 (1997), 47–65., su link.springer.com.

Collegamenti esterni

• (EN) Site personnel, su theory.cs.uni-bonn.de.
• (EN) Marek Karpinski at DBLP, su informatik.uni-trier.de.
• (EN) Marek Karpinski at Scholar Wiki, su scholarwiki.indiana.edu. URL consultato il 17 novembre 2014 (archiviato dall'url originale il 3 novembre 2014).
• Numero di Erdős
• (EN) Publications at ACM Digital Library, su dl.acm.org.
• (EN) Computational Complexity theory,notable researchers
• (EN) The Best Nurturers in Computer Science Research, su eprints.iisc.ernet.in. URL consultato il 18 novembre 2014 (archiviato dall'url originale il 26 settembre 2015).