Наградата Абел за 2021 г. отбеляза съюза на математиката и компютърните науки (видео)

Двама пионери в теорията на изчисленията са спечелили наградата Абел за 2021 г., едно от най-престижните отличия в математиката.

Унгарският математик Ласло Ловаш (László Lovász) и израелският компютърен учен Ави Уигдърсън (Avi Wigderson) ще си поделят наградата на стойност 7,5 милиона норвежки крони (886 000 щатски долара), „за техния основен принос към теоретичните компютърни науки и дискретна математика и водещата им роля в оформянето им като централни области на съвременното математик“, съобщи Норвежката академия за наука и литература.

Уигдърсън, който е от Института за напреднали изследвания (IAS) в Принстън, Ню Джърси, заяви пред Nature, че наградата потвърждава теорията на изчисленията, а не само собствената му работа. „Мисля, че това е изключително важно за тази област“, коментира лауреатът.

„Днес е все по-трудно - и мисля, че това е добро развитие - да се разграничат чистата математика и приложната математика“, отбелязва Ловаш от Университета Eötvös Loránd в Будапеща.

Алгоритмите - които включват прости процедури, които децата учат в училище, като делене на стълбичка - са от основно значение за математиката още от времето на древна Гърция. Но от появата на компютрите през двадесети век акцентът в изследванията се промени от „може ли алгоритъмът да реши тази задача?“ до „може ли алгоритъмът, поне по принцип, да реши тази задача на реален компютър и за разумно време?“

_{Ласло Ловаш (László Lovász) (вляво) и Ави Уигдърсън (Avi Wigderson) са удостоени съвместно с наградата Абел за 2021 г. Кредити: вляво, Hungarian Academy of Sciences/Laszlo Mudra/AbelPrize; вдясно, Cliff Moore/Institute for Advanced Study, Princeton/AbelPrize}

От математика до компютри

Ловаш е роден през 1948 г. в Будапеща и е израснал в среда, която насърчава талантливите деца да се състезават в решаването на трудни задачи. Голяма част от ранното му вдъхновение идва от Пол Ердес, най-плодовитият математик от модерната епоха. Работата на Ердес се фокусира върху математиката на дискретни обекти и техните взаимоотношения - като възлите в мрежата - вместо върху непрекъснатите променливи, които са типични за области като геометрията.

Ловаш започва кариерата си по времето, когато теми в дискретната математика като теорията на мрежите - някога гледани с пренебрежение от „чистите“ математици, стават от решаващо значение както за други области на математиката, така и за приложения като анализа на „големи данни“. Той се интересува от фундаментални изследвания, както и от приложенията им, и работи като редовен изследовател в Microsoft в продължение на седем години, заедно с академичната си дейност. Той решава основни проблеми в математическата теория на мрежите, като например изчислява броя на възможните начини за оцветяване на възлите, като същевременно гарантира, че всеки два съседни възла са винаги с различни цветове ¹.

Един от най-известните резултати на Ловаш е алгоритъм, който той измисля заедно с двама холандски теоретици на числата, братята Ариен и Хендрик Ленстра (Arjen and Hendrik Lenstra) ². Алгоритъмът, известен като LLL, разделя голям вектор, направен от цели числа, в сума от възможно най-кратките вектори от този тип. Той има приложения в различни области на чистата математика и е от решаващо значение за изучаването на криптирането на данни. Криптографските ключове, базирани на целочислени вектори, се разглеждат като обещаващи за бъдещата интернет сигурност, тъй като за разлика от ключовете, използвани често в съвременните комуникации, се смята, че те няма да бъдат уязвими от пробив от бъдещите квантови компютри.

Ловаш е бил президент на Международния математически съюз от 2007 до 2010 г. Той също така е ръководил Унгарската академия на науките от 2014 до 2020 г. и през тези години е предпримал дръзки, но в крайна сметка неуспешни усилия да попречи на унгарското правителство да завладее изследователските институти на академията. Той и много други твърдят, че този ход ще намали независимостта на изследователите.

От изчисленията до математиката

Уигдърсън е роден в Хайфа, Израел, през 1956 г. Учи в Израел и Съединените щати и заема различни академични длъжности, преди да се премести в IAS през 1999 г., където е и досега. Наградата Абел е признание за приноса му на практика във всички области на компютърните науки, в които той атакува всеки проблем с каквито и да било математически инструменти, които е успял да намери, дори от далечни области на изследване. 

Едно от най-известните постижения на Уигдърсън е в изясняването на ролята на случайността в изчисленията. В много ситуации, като например търсене на изход от лабиринта, преносно подхвърляне на монети, позволява алгоритмите да намерят решение бързо, но по причини, които не са веднага очевидни. Много програми на практика се изпълняват много по-бързо, ако им позволите да направят този произволен избор.

Работейки със сътрудници през 90-те години, Уигдърсън показа, че ако даден алгоритъм, използващ случайността, изглежда работи ефективно, тогава трябва да съществува друг, неслучаен алгоритъм, който е почти толкова ефективен ³. Това дава теоретично потвърждение, че случайните алгоритми наистина намират правилните решения.

Друга важна част от работата на Уигдърсън става все по-актуална в информационната икономика. Тя включва „доказателство за нулева информация“, начин да се позволи на някого да провери верността на дадено твърдение, без да се разкрива каквато и да е информация за това, което се казва в твърдението.

Доказателствата за нулева информация са от решаващо значение за сертифициране на дигиталните валути като биткойна и могат също да помогнат за проверка на самоличността на човек. Отговаряйки на въпросите на проверяващия, някой може да даде доказателство за нула знания, че има правилна парола например, без да разкрива самата парола. Уигдърсън и неговите сътрудници показват през 1991 г. ⁴, че по същество всички математически твърдения могат да бъдат преведени по начин, който позволява доказателство за нулево знание - „вероятно най-изненадващото и най-парадоксалното“ от неговите резултати, отбелязва Уигдърсън.

Откакто е учредена наградата Абел през 2003 г., Ловаш е третият победител от Унгария, а Вигдерсън е вторият израелец. С изключение на Карън Кескула Уленбек през 2019 г. , всички победители досега са били мъже.

Източник: Abel Prize celebrates union of mathematics and computer science, Nature

doi: https://doi.org/10.1038/d41586-021-00694-9

Препратки

1. Lovász, L. J. Comb. Theory A 25, 319–324 (1978). Article Google Scholar

2. Lenstra, A. K., Lenstra, H. W. & Lovász, L. Mathematische Ann. 261, 515–534 (1982). Article Google Scholar

3. Impagliazzo, R. & Wigderson, A. Proceedings of the 29th Symposium on Theory of Computing (STOC) 220–229 (1997).

4. Goldreich, O., Micali, S. & Wigderson, A. J. ACM 38, 691–729 (1991). Article Google Scholar

Още по темата

19/03/2022

Физика

На тази дата за първи път жена получи престижната награда за математика Абел

05/08/2022

Математика

На днешната дата е роден Нилс Абел, живял 27 години, но с изключителен принос в математиката

18/03/2020

Математика

Обявиха лауреатите на математическия Нобел, наградата Абел

31/03/2019

Математика

Какво откри първата жена, носител на математическия Нобел, наградата Абел