# Venkatesan Guruswami

Venkatesan Guruswami, né en 1976, est un informaticien théoricien, professeur d'informatique à l'université Carnegie-Mellon à Pittsburgh. Son domaine de recherche est l'informatique théorique, et notamment l'étude des codes correcteur.

## Biographie

Guruswami a fait ses études secondaires à Chennai, dans l'école Padma Seshadri Bala Bhavan (en). Il a terminé ses études undergraduate en informatique à l'Institut indien de technologie de Madras et a obtenu son Ph. D. au Massachusetts Institute of Technology sous la supervision de Madhu Sudan en 2001$^,$. Il passe l'année suivante à l'université de Californie à Berkeley en tant que Miller Fellow (en); de 2002 à 2009 il est membre de l'université de Washington. Il est chercheur invité à l'école de mathématiques de Institute for Advanced Study en 2007-2008 et à l'Université Carnegie-Mellon en 2008-2009. En juillet 2009, il rejoint l'École d'informatique à Carnegie-Mellon comme professeur associé. Il y est professeur à part entière depuis 2014.

## Travaux

Guruswami a contribué des résultats fondamentaux à la théorie du décodage en liste des codes correcteurs d'erreurs. Ses recherches sur ce sujet ont culminé dans une publication commune avec son ancien élève Artri Rudra qui donne des constructions de codes correcteurs d'erreurs avec un algorithme de décodage en liste qui atteignent une redondance minimale possible. Ceci résout l'un des problèmes théoriques ouverts les plus importants de la théorie de la communication depuis l'invention des codes correcteurs d'erreurs en 1949.
Dans sa thèse de Ph. D., Guruswami développe déjà un algorithme permettant de corriger les erreurs au-delà de la moitié de la distance minimale du code. Elle s'applique aux codes de Reed–Solomon et plus généralement aux codes géométriques algébriques. Cet algorithme de décodage en liste (en) produit une liste de mots de code et est basé sur l'interpolation et la factorisation des polynômes sur $GF(2^{m})$ et ses extensions.
Guruswami continue à travailler en informatique théorique, sur des thèmes issus de la théorie des codes correcteurs, les algorithmes d'approximation et la non-approximabilité, le pseudo-aléatoire, les preuves vérifiable en probabilité, et les algorithmes algébriques. Il est éditeur-en-chef des ACM Transactions on Computation Theory.

## Prix et distinctions

En 2002, Venkatesan Guruswami s'est vu décerner en 2002 le prix de thèse de doctorat de l'ACM pour son mémoire intitulé List Decoding of Error-Correcting Codes. Il a été conférencier invité au Congrès international des mathématiciens de 2010 à Hyderabad dans la catégorie Aspects mathématiques de l'informatique.
Venkatesan Guraswami est l'un des deux lauréats du prix Presburger de 2012, décerné par l'Association européenne d'informatique théorique. Il a été élu ACM Fellow en 2017.

## Publications (sélection)

* Venkatesan Guruswami, « List Decoding of Error-Correcting Codes », Lecture Notes in Computer Science, Springer Verlag, vol. 3282,‎ 2004, p. 1-350 (ISBN 978-3-540-24051-8) — prix de thèse 2002 de la ACM Doctoral Dissertation Competition
* Venkatesan Guruswami et Madhu Sudan, « Improved decoding of Reed-Solomon and algebraic-geometry codes », IEEE Transactions on Information Theory, vol. 45, n$^o$ 6,‎ 1999, p. 1757-1767 (ISSN 0018-9448, DOI 10.1109/18.782097)
* Joshua Brakensiek, Venkatesan Guruswami et Samuel Zbarsky, « Efficient Low-Redundancy Codes for Correcting Multiple Deletions », IEEE Transactions on Information Theory, vol. 64, n$^o$ 5,‎ 2018, p. 3403-3410 (ISSN 0018-9448, DOI 10.1109/TIT.2017.2746566, arXiv 1507.06175).