Aleksander Mądry

Données clés
Naissance	Wrocław
Domaines	Mathématiques, informatique théorique
Institutions	Massachusetts Institute of Technology.
Directeur de thèse	Michel Xavier Goemans et Jonathan A. Kelner
Renommé pour	Problème de flot maximum
Distinctions	Prix Presburger (en 2018)

Aleksander Mądry est un informaticien théoricien et mathématicien, professeur assistant au Massachusetts Institute of Technology.

Biographie

Aleksander Mądry, né à Wrocław, fait des études supérieures à l'Université de Wrocław avec une licence en physique théorique en 2007 et une maîtrise en informatique en 2006^[1]. Il poursuit ses études au Massachusetts Institute of Technology avec un M. Sc. en informatique (titre du mémoire : Faster Generation of Random Spanning Trees) et un Ph. D. en 2011^[2] sous la direction de Michel Xavier Goemans et Jonathan A. Kelner (titre de la thèse : « From Graphs to Matrices, and Back: New Techniques for Graph Algorithms »). Il passe une année de post-doc à Microsoft Research New England, puis il travaille à l'École polytechnique fédérale de Lausanne (EPFL) jusqu'en 2015, où il rejoint le département d'ingénierie électrique et d'informatique au MIT.

Travaux

Aleksander Mądry a fait plusieurs contributions substantielles à la théorie des algorithmes^[3]. Il a notamment présenté en 2011 un algorithme d'approximation pour le problème du flot maximum dans les graphes en complexité en temps $O(mn^{1/3})$ qui améliore une borne restée stable depuis longtemps^[4]. En 2013, il donne un algorithme de calcul exact pour le problème du flot maximum qui est le premier à améliorer la borne de $O(n^{3/2})$ établie par Evan et Tarjan en 1975^[5]. Mądry a aussi contribué des avancées au problème dit des k serveurs (en)^[6], et au problème du voyageur de commerce^[7]. La laudatio^[3] du prix Presburger écrit: « Aleksander’s results have been celebrated in the community not only because he broke long standing complexity barriers but moreover because he introduced new and very different techniques to the field which since have successfully been picked up by others^[8]. ».

Prix et récompenses

Aleksander Mądry est lauréat du prix Presburger obtenu en 2018 et conférencier invité au congrès international des mathématiciens^[9] de 2018. Il a obtenu un ensemble de prix, bourses et récompenses :

2017 Google Research Award
2016 Bourse Sloan
2015 NSF CAREER Award
2014 Open Mind Prize (prix biennal attribué à un chercheur polonais junior pour des recherches en combinatoire)
2011 Mention honorable au prix de thèse ACM
2011 Prix de thèse George M. Sprowls (attribuée au meilleur Ph. D. du MIT en informatique)

Prix de la meilleure communication :

2013 IEEE Symposium on Foundations of Computer Science (FOCS)^[5]
2011 IEEE Symposium on Foundations of Computer Science (FOCS)^[10]

2011 ACM Symposium on Theory of Computing (STOC)^[4]
2010 ACM-SIAM Symposium on Discrete Algorithms (SODA)^[11]

Notes et références

↑ CV d'Aleksander Mądry
↑ (en) « Aleksander Madry », sur le site du Mathematics Genealogy Project
↑ ^{a et b} Presburger_Laudatio 2018
↑ ^{a et b} Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman et Shang-Hua Teng, « Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs », Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC,‎ 2011, p. 273-282 (DOI 10.1145/1993636.1993674)
↑ ^{a et b} Aleksander Madry, « Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back », 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS,‎ 2013, p. 253–262 (DOI 10.1109/FOCS.2013.35)
↑ Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee et Aleksander Mądry, « k-server via multiscale entropic regularization », Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC,‎ 2018, p. 3–16 (DOI 10.1145/3188745.3188798)
↑ Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan et Amin Saberi, « An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem », Operations Research, vol. 65, n^o 4,‎ 2017, p. 1043–1061 (ISSN 0030-364X, DOI 10.1287/opre.2017.1603).
↑ Les résultats d'Aleksander ont été célébrés dans la communauté non seulement parce qu'il a franchi des barrières de complexité établies de longue date, mais aussi parce qu'il a introduit des techniques nouvelles et très différentes dans le domaine qui ont depuis été reprises avec succès par d'autres.
↑ Liste des orateurs du congrès international des mathématiciens#2018 Rio de Janeiro
↑ N. Bansal, N. Buchbinder, A. Madry et J. Naor, « A Polylogarithmic-Competitive Algorithm for the k-Server Problem », IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS,‎ 2011, p. 267–276 (DOI 10.1109/FOCS.2011.63).
↑ Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan et Amin Saberi, « AnO(logn/log logn)-approximation Algorithm for the Asymmetric Traveling Salesman Problem », Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA,‎ 2010, p. 379–389 (DOI 10.1137/1.9781611973075.32)

Liens externes

Publications d'Aleksander Mądry sur DBLP
Ressources relatives à la recherche :
- Mathematics Genealogy Project
- Nauka Polska
Notices d'autorité :
- VIAF
- Pologne
Page personnelle

Portail de l'informatique théorique

[1] CV d'Aleksander Mądry

[2] (en) « Aleksander Madry », sur le site du Mathematics Genealogy Project

[laudatio-3] {a et b} Presburger_Laudatio 2018

[ChristianoKelner2011-4] {a et b} Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman et Shang-Hua Teng, « Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs », Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC,‎ 2011, p. 273-282 (DOI 10.1145/1993636.1993674)

[Madry2013-5] {a et b} Aleksander Madry, « Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back », 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS,‎ 2013, p. 253–262 (DOI 10.1109/FOCS.2013.35)

[BubeckCohen2018-6] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee et Aleksander Mądry, « k-server via multiscale entropic regularization », Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC,‎ 2018, p. 3–16 (DOI 10.1145/3188745.3188798)

[AsadpourGoemans2017-7] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan et Amin Saberi, « An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem », Operations Research, vol. 65, n^o 4,‎ 2017, p. 1043–1061 (ISSN 0030-364X, DOI 10.1287/opre.2017.1603).

[8] Les résultats d'Aleksander ont été célébrés dans la communauté non seulement parce qu'il a franchi des barrières de complexité établies de longue date, mais aussi parce qu'il a introduit des techniques nouvelles et très différentes dans le domaine qui ont depuis été reprises avec succès par d'autres.

[9] Liste des orateurs du congrès international des mathématiciens#2018 Rio de Janeiro

[BansalBuchbinder2011-10] N. Bansal, N. Buchbinder, A. Madry et J. Naor, « A Polylogarithmic-Competitive Algorithm for the k-Server Problem », IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS,‎ 2011, p. 267–276 (DOI 10.1109/FOCS.2011.63).

[AsadpourGoemans2010-11] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan et Amin Saberi, « AnO(logn/log logn)-approximation Algorithm for the Asymmetric Traveling Salesman Problem », Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA,‎ 2010, p. 379–389 (DOI 10.1137/1.9781611973075.32)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]