Katalin Marton

The native form of this personal name is Marton Katalin. This article uses Western name order when mentioning individuals.
Katalin Marton
Born9 December 1941[1]
Budapest, Hungary
Died13 December 2019 (aged 78)[2]
Alma materEötvös Loránd University
Known forInformation theory, concentration of measure, probability theory
AwardsClaude E. Shannon Award (2013) Alfréd Rényi Prize (1996)
Scientific career
FieldsMathematics
InstitutionsAlfréd Rényi Institute of Mathematics
Websitewww.renyi.hu/~marton/

Katalin Marton (9 December 1941 – 13 December 2019) was a Hungarian mathematician, born in Budapest.

Education and career

Marton obtained her PhD from Eötvös Loránd University in 1965 and worked at the Department of Numerical Mathematics, Central Research Institute for Physics, Budapest from 1965 to 1973. Important influences on her early career were her attendance at the combinatorics seminar organised by Alfréd Rényi from 1966, meeting Roland Dobrushin in Debrecen in 1967 (which led to her visiting the Institute for Problems in Information Transmission in Moscow in 1969[3]), and her collaboration with Imre Csiszár which began in 1972. From 1973 she worked at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences in Budapest, visiting the United States in 1977 (for the International Symposium on Information Theory in Ithaca) and in 1979–80 (meeting Robert Gallager at MIT and Robert M. Gray at Stanford).

Research interests

Marton worked on various areas of mathematics, including information theory, concentration of measure and probability theory. In a 1974 paper on information theory she used a combinatorics approach to characterize error in discrete memoryless sources under distortion.[1] She was particularly well known for her two-page proof, based on an information-theoretic coupling inequality, of the blowing-up lemma,[4] published in 1986. This result, which arose out of work of Grigory Margulis in 1974[5] and which was developed further by Rudolf Ahlswede, Peter Gács and János Körner,[6] shows that (in product measures) the neighbourhood of a set of greater than exponentially small size has size close to 1. This result is used in a variety of contexts including strong converse results for coding theorems, classification and model selection.

Marton was also responsible for the polynomial Freiman–Ruzsa conjecture,[7] a central question of additive combinatorics, now also called Freiman's theorem. This was published by Imre Ruzsa but as he mentions[8] this conjecture came from Marton. It states that if a subset of a group (a power of a cyclic group) has small doubling constant then lies in the union of a bounded polynomial number of cosets of some subgroup . This conjecture is deeply characteristic to the way Marton fed back particular information-theoretic results into the mainstream of mathematics. In 2012 Tom Sanders gave an almost polynomial bound of the conjecture for abelian groups.[9][10] In 2023 a solution over a field of characteristic 2 has been posted as a preprint by Tim Gowers, Ben Green, Freddie Manners and Terry Tao.[11][10]

Marton's other major contributions included coding theorems for the broadcast channel[12][13] (with the former paper proving the best-known inner bound on the capacity region of the two-receiver general broadcast channel, often referred to as "Marton's inner bound"[14]) and many other results in concentration of measure,[15][16] rate-distortion theory[17][18] and graph capacity.[19][20] Marton had an Erdős number of 2, for example via her collaboration[21] with Imre Csiszár and László Lovász.

Awards and recognition

In 1996, Marton won the Alfréd Rényi Prize from the Alfréd Rényi Institute. In 2013, she was the first (and so far only) female winner of the Claude E. Shannon Award, the top prize in information theory, from the IEEE. As a result, she delivered the Shannon Lecture at the International Symposium on Information Theory in Istanbul in 2013, with her talk being entitled Distance-Divergence Inequalities.[22][23][24] The citation and biographical sketch[25] paid tribute to her scientific contributions, with Fields Medallist Cédric Villani writing:

"Marton is one of the leading authorities about the applications of information theory techniques to concentration theory, in particular in the setting of Markov Chains. Most importantly, in the mid-nineties, Marton pointed out the interest and importance of entropy inequalities in the study of the concentration phenomena. Talagrand has acknowledged the influence of Marton in this respect, and this motivated him to establish the famous Talagrand inequality[26] controlling the Wasserstein distance by the square root of the Boltzmann-Shannon information. In turn, the Talagrand inequality triggered the development a whole field, which I explored with Otto, McCann, Lott and others, involving entropy, concentration, transport, Ricci curvature, with very far reaching geometric consequences."

In 2013, Marton was also awarded the József Eötvös Wreath [hu] by the Hungarian Academy of Science.[2]

References

  1. ^ a b Csiszár, Imre; Körner, János (September 2020). El Rouayheb, Salim (ed.). "In Memoriam: Katalin Marton 1941–2019". IEEE Information Theory Society Newsletter. 70 (3). IEEE: 11–12. ISSN 1045-2362. Retrieved 20 October 2020.
  2. ^ a b "Elhunyt Marton Katalin". Alfréd Rényi Institute of Mathematics (in Hungarian). 18 December 2019. Retrieved 5 January 2020.
  3. ^ El Gamal, Abbas (2010). "Katalin Marton" (PDF). Withits 2010. Stanford University.
  4. ^ Marton, K. (1986). "A simple proof of the blowing-up lemma (Corresp.)". IEEE Transactions on Information Theory. 32 (3): 445–446. doi:10.1109/TIT.1986.1057176.
  5. ^ Margulis, G. A. (1974). "Probabilistic characteristics of graphs with large connectivity". Problemy Peredachi Informatsii. 10 (2): 101–108.
  6. ^ Ahlswede, R.; P. Gács; J. Körner (1976). "Bounds on conditional probabilities with applications in multi-user communication". Z. Wahrscheinlichkeitstheorie Verw. Gebiete. 34 (3): 157–177. doi:10.1007/BF00535682. S2CID 13901122.
  7. ^ Blogpost by Ben Green https://terrytao.wordpress.com/2007/03/11/ben-green-the-polynomial-freiman-ruzsa-conjecture/
  8. ^ Ruzsa, I. (1999). "An analog of Freiman's theorem in groups" (PDF). Astérisque. 258: 323–326.
  9. ^ Sanders, Tom (2012-10-15). "On the Bogolyubov–Ruzsa lemma". Analysis & PDE. 5 (3): 627–655. arXiv:1011.0107. doi:10.2140/apde.2012.5.627. ISSN 1948-206X.
  10. ^ a b Sloman, Leila (2023-12-06). "'A-Team' of Math Proves a Critical Link Between Addition and Sets". Quanta Magazine. Retrieved 2023-12-11.
  11. ^ Gowers, W. T.; Green, Ben; Manners, Freddie; Tao, Terence (2023). "On a conjecture of Marton". arXiv:2311.05762 [math.NT].
  12. ^ Marton, K. (1979). "A coding theorem for the discrete memoryless broadcast channel". IEEE Transactions on Information Theory. 25 (3): 306–311. doi:10.1109/TIT.1979.1056046.
  13. ^ Körner, J.; K. Marton (1977). "General broadcast channels with degraded message sets". IEEE Transactions on Information Theory. 23 (1): 60–64. doi:10.1109/TIT.1977.1055655.
  14. ^ Gohari, A.A.; V. Anantharam (2012). "Evaluation of Marton's inner bound for the general broadcast channel". IEEE Transactions on Information Theory. 58 (2): 608–619. arXiv:1006.5166. doi:10.1109/TIT.2011.2169537. S2CID 415264.
  15. ^ Marton, K. (1996). "Bounding -distance by informational divergence: A method to prove measure concentration". Annals of Probability. 24 (2): 857–866. doi:10.1214/aop/1039639365.
  16. ^ Marton, K. (2004). "Measure concentration for Euclidean distance in the case of dependent random variables". Annals of Probability. 32 (3B): 2526–2544. arXiv:math/0410168. Bibcode:2004math.....10168M. doi:10.1214/009117904000000702.
  17. ^ Marton, K. (1971). "Asymptotic behavior of the rate distortion function of discrete stationary processes". Problemy Peredachi Informatsii. VII (2): 3–14.
  18. ^ Marton, K. (1975). "On the rate distortion function of stationary sources". Problems of Control and Information Theory. 4: 289–297.
  19. ^ Körner, J.; K. Marton (1988). "Random access communication and graph entropy". IEEE Transactions on Information Theory. 34 (2): 312–314. doi:10.1109/18.2639.
  20. ^ Marton, K. (1993). "On the Shannon capacity of probabilistic graphs". Journal of Combinatorial Theory. 57 (2): 183–195. doi:10.1006/jctb.1993.1015.
  21. ^ Csiszár, I.; J. Körner; L. Lovász; K. Marton; G. Simonyi (1990). "Entropy splitting for antiblocking corners and perfect graphs". Combinatorica. 10 (1): 27–40. doi:10.1007/BF02122693. S2CID 16508298.
  22. ^ Slides of 2013 Shannon lecture https://www.itsoc.org/resources/videos/isit-2013-istanbul/MartonISIT2013.pdf/view
  23. ^ Video of 2013 Shannon Lecture: https://vimeo.com/135256376
  24. ^ Blogpost about 2013 Shannon Lecture: https://infostructuralist.wordpress.com/2013/07/29/isit-2013-two-plenaries-on-concentration-of-measure/
  25. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2018-02-01. Retrieved 2019-12-18.{{cite web}}: CS1 maint: archived copy as title (link)
  26. ^ Talagrand, M. (1996). "Transportation cost for Gaussian and other product measures". Geometric and Functional Analysis. 6 (3): 587–600. doi:10.1007/BF02249265. S2CID 120778404. (note paper Acknowledgement "The author is grateful to Professor Marton for sending him her paper which motivated this work")