Marek Karpinski

Marek Karpinski (25 marzo 1948^[1]) è 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.

Marek Karpinski

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.^[2][3] È 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.^[4][5] È 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.^[6].

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

Note

2. Marek Karpinski Biography at the Hausdorff Center for Mathematics, Excellence Cluster
3. Marek Karpinski, Awards
4. Working Group "Randomized Algorithms" RAND2
5. Working Group on "Randomized and Approximate Computation" RAND-APX
6. Hausdorff Center for Mathematics
7. Max Planck Research Price 1994

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).

Controllo di autorità	VIAF (EN) 167681 · ISNI (EN) 0000 0001 1803 790X · LCCN (EN) n80146008 · GND (DE) 115476032 · BNF (FR) cb13518082r (data) · J9U (EN, HE) 987007439974205171

Portale Biografie

Portale Informatica

Portale Matematica