Marek Karpinski

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.

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

  1. ^ [1]
  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 · WorldCat Identities (EN) lccn-n80146008
  Portale Biografie
  Portale Informatica
  Portale Matematica