Перегляд вихідного коду сторінки Ласло Бабай

{{Науковець 
| ім'я               = Ласло Бабай
| ім'я_мовою_оригіналу = {{lang-hu|{{угорське ім'я|Babai László}}}}
| жінка              = 
| зображення         = Laszlo Babai.jpg
| зображення_розмір  = 
| громадянство       = 
| національність     = [[угорець]]
| галузь             = [[математика]]
| заклад             = [[Чиказький університет]]
| Alma Mater         = [[Будапештський університет|Університет Лоранда Етвеша]] , <br> [[Угорська академія наук]]
| посада             = <!--інша суспільно значуща посада-->
| відомий завдяки    = 
| звання             = 
| ступінь            = 
| керівник           = 
| учні               = 
| батько             =
| мати               =
| дружина            =
| чоловік            =
| діти               =
| нагороди           = [[Премія Геделя]] (1993) <br> [[Премія Кнута]] (2015)
<!-- 
{{(!}} style="background: transparent"
{{!}} {{шаблон_вищої_нагороди}}
{{!)}}
{{(!}} style="background: transparent"
{{!}} {{шаблон_нагороди}} {{!!}} {{шаблон_нагороди}} 
{{!}}-
{{!}} {{шаблон_нагороди}} {{!!}} {{шаблон_нагороди}} 
{{!)}} 
--> 
| автограф           =
| примітки           = 
| особиста_сторінка  = [https://cs.uchicago.edu/directory/lászló-babai László Babai]
}}

'''Ласло Бабай''' ({{lang-hu|{{угорське ім'я|Babai László}}}}; {{ДН|20|7|1950}}, {{місце народження|Будапешт}})<ref name=cv>[http://people.cs.uchicago.edu/~laci/CV.pdf Curriculum vitae] {{Webarchive|url=https://web.archive.org/web/20140211143337/http://people.cs.uchicago.edu/~laci/CV.pdf |date=11 лютого 2014 }} // [http://people.cs.uchicago.edu/~laci/CV.html Babai's web site] {{Webarchive|url=https://web.archive.org/web/20171107003055/http://people.cs.uchicago.edu/~laci/CV.html |date=7 листопада 2017 }}</ref> — угорський та американський математик, професор математики та інформатики (computer science) в [[Чиказький університет|Чиказькому університеті]]. Його дослідження зосереджені у галузях: [[теорія складності обчислень]], [[теорія алгоритмів]], [[комбінаторика]], та [[Скінченна група|скінченні групи]], з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць.<ref name=cv/>

Бабай вивчав математику в [[Будапештський університет|Будапештському університеті]] імені [[Етвеш Лоранд|Лоранда Етвеша]] з 1968 по 1973, отримав Ph.D. в [[Угорська академія наук|Угорській академії наук]] у 1975, і отримав D.Sc. в Угорській академії наук у 1984.<ref name=cv/><ref>{{MathGenealogy|id=78102}}</ref>

Автор [[Лас-Вегас (алгоритм)|алгоритму Лас-Вегас]] (1979), версії [[Метод Монте-Карло|методу Монте-Карло]].<ref>'''Ласло Бабай''', [http://people.cs.uchicago.edu/~laci/lasvegas79.pdf  Monte-Carlo algorithms in graph isomorphism testing] {{Webarchive|url=https://web.archive.org/web/20171208122851/http://people.cs.uchicago.edu/~laci/lasvegas79.pdf |date=8 грудня 2017 }}, Université de Montréal, D.M.S. No. 79-10.</ref>

== Graph Isomorphism in Quasipolynomial Time ==

З 10 листопада по 1 грудня 2015 року на семінарі «Combinatorics and Theoretical Computer Science» в [[Чиказький університет|Чиказькому університеті]] зробив три доповіді «Graph Isomorphism in [[квазіполіноміальний час|Quasipolynomial Time]]», у яких виклав алгоритм, який вирішує {{iw2|проблема ізоморфізму графів|проблему||Graph isomorphism problem}} [[Ізоморфізм графів#Обчислювальна складність|ізоморфізму графів]] за квазіполіноміальний <math>e^{\log(n)^{O(1)}}</math> час.<ref>Laszlo Babai (University of Chicago): [https://calendar.google.com/calendar/render?eid=czNzOXNtZ2tydG00OG5obDJlZ3I3c21uY2cgYzU3c2hpY2k0NW0xN3FsMGdodmw1NmVrMzhAZw&ctz=America/Chicago&pli=1&t=AKUaPmbNo4fEHI_fQA5RP4AEOVRvY_38tKCShSSp7z2RGnSSoAFNkqX7djaXeyZLSyiagv-Jnb0pK6iajFFbAnvp8q5SsF0K4g&sf=true&output=xml#eventpage_6 Graph Isomorphism in Quasipolynomial Time I]: The "Local Certificates Algorithm" // Combinatorics and Theoretical Computer Science seminar, 10 листопада 2015, 15:00 – 16:00</ref><ref>[https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ A Big Result On Graph Isomorphism] {{Webarchive|url=https://web.archive.org/web/20170710180503/https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ |date=10 липня 2017 }} // November 4, 2015, [https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ A Fast Graph Isomorphism Algorithm] {{Webarchive|url=https://web.archive.org/web/20170729155154/https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ |date=29 липня 2017 }} // November 11, 2015</ref><ref>[http://www.math.uchicago.edu/calendar?calendar=Combinatorics%20and%20Theoretical%20Computer%20Science Combinatorics and Theoretical Computer Science] {{Webarchive|url=https://web.archive.org/web/20151222101053/http://www.math.uchicago.edu/calendar?calendar=Combinatorics%20and%20Theoretical%20Computer%20Science |date=22 грудня 2015 }} calendar // [http://theory.cs.uchicago.edu/index.php Theoretical Computer Science at the University of Chicago] {{Webarchive|url=https://web.archive.org/web/20171022042014/http://theory.cs.uchicago.edu/index.php |date=22 жовтня 2017 }}. November 24, 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The "Split-or-Johnson routine" (Combinatorics and TCS seminar)</ref><ref>[http://www.technologyreview.com/news/543511/claimed-breakthrough-slays-classic-computing-problem-encryption-could-be-next/ Claimed Breakthrough Slays Classic Computing Problem] {{Webarchive|url=https://web.archive.org/web/20160122074854/http://www.technologyreview.com/news/543511/claimed-breakthrough-slays-classic-computing-problem-encryption-could-be-next/ |date=22 січня 2016 }} // MIT Technology Review, by Tom Simonite on November 13, 2015</ref>
10 грудня 2015 опубліковано відео першої доповіді<ref>[https://www.youtube.com/watch?v=qYIhA3O9Nz0 Graph Isomorphism in Quasipolynomial Time I] {{Webarchive|url=https://web.archive.org/web/20180912094208/https://www.youtube.com/watch?v=qYIhA3O9Nz0 |date=12 вересня 2018 }}, seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015</ref>.

11 грудня 2015 у [[arXiv.org]] оприлюднено однойменну статтю «Graph Isomorphism in Quasipolynomial Time»<ref>László Babai. [http://arxiv.org/pdf/1512.03547v1 Graph Isomorphism in Quasipolynomial Time], 84 pages / [http://arxiv.org/abs/1512.03547v1 abstract] {{Webarchive|url=https://web.archive.org/web/20171122174710/https://arxiv.org/abs/1512.03547v1 |date=22 листопада 2017 }} // [[arXiv.org]] > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT</ref>.
{{приховати|abstract}} <!-- резюме / -->
<font face="Times New Roman">
<big><big>
<blockquote>
We show that the [[Ізоморфізм графів|Graph Isomorphism]] {{iw2|проблема ізоморфізму графів|(GI) problem||Graph isomorphism problem}} and the related problems of String Isomorphism<ref>[https://books.google.com.ua/books?id=YBlrCQAAQBAJ&pg=PA103&lpg=PA103&dq=%22String+Isomorphism%22&source=bl&ots=N1v1e0JezJ&sig=ucko9x9WPrwYadL_dKAA3g-Lzoo&hl=uk&sa=X&ved=0ahUKEwip5K3VmeXJAhXJBiwKHZzqCsIQ6AEIVjAI#v=onepage&q=%22String%20Isomorphism%22&f=false '''Definition 2.3.''' String Isomorphism] {{Webarchive|url=https://web.archive.org/web/20180328231735/https://books.google.com.ua/books?id=YBlrCQAAQBAJ&pg=PA103&lpg=PA103&dq=%22String+Isomorphism%22&source=bl&ots=N1v1e0JezJ&sig=ucko9x9WPrwYadL_dKAA3g-Lzoo&hl=uk&sa=X&ved=0ahUKEwip5K3VmeXJAhXJBiwKHZzqCsIq6aeivjai#v=onepage&q=%22String%20Isomorphism%22&f=false |date=28 березня 2018 }} // Google Books, in: [http://www.springer.com/gp/book/9783642020964 Transactions on Computational Science V] {{Webarchive|url=https://web.archive.org/web/20180329120833/http://www.springer.com/gp/book/9783642020964 |date=29 березня 2018 }}. Special Issue on Cognitive Knowledge Representation. [https://books.google.com.ua/books?id=R2SvCCXPChMC&pg=PR11&lpg=PR11&dq=Transactions+on+Computational+Science+V&source=bl&ots=l_2MEooTI_&sig=sn2x14gsOcN8pCpIgh8141DOq_k&hl=uk&sa=X&ved=0ahUKEwjx0ujbmuXJAhVi1XIKHbpdAKQQ6AEIOTAE#v=onepage&q=Transactions%20on%20Computational%20Science%20V&f=false Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan] {{Webarchive|url=https://web.archive.org/web/20180328231737/https://books.google.com.ua/books?id=R2SvCCXPChMC&pg=PR11&lpg=PR11&dq=Transactions+on+Computational+Science+V&source=bl&ots=l_2MEooTI_&sig=sn2x14gsOcN8pCpIgh8141DOq_k&hl=uk&sa=X&ved=0ahUKEwjx0ujbmuXJAhVi1XIKHbpdAKQq6aeiotae#v=onepage&q=Transactions%20on%20Computational%20Science%20V&f=false |date=28 березня 2018 }} / {{iw2|Lecture Notes in Computer Science}} / Volume 5540, [[Springer Verlag]], 2009</ref> (under group action) (SI) and Coset Intersection (CI)<ref>[http://groupprops.subwiki.org/wiki/Coset_intersection_problem Coset intersection problem] {{Webarchive|url=https://web.archive.org/web/20180329054352/https://groupprops.subwiki.org/wiki/Coset_intersection_problem |date=29 березня 2018 }} // [http://groupprops.subwiki.org/wiki/Main_Page The Group Properties Wiki] {{Webarchive|url=https://web.archive.org/web/20171022031513/https://groupprops.subwiki.org/wiki/Main_Page |date=22 жовтня 2017 }} (beta)</ref><ref>[http://cstheory.stackexchange.com/questions/25868/complexity-of-the-coset-intersection-problem Complexity of the coset intersection problem] {{Webarchive|url=https://web.archive.org/web/20151224104154/http://cstheory.stackexchange.com/questions/25868/complexity-of-the-coset-intersection-problem |date=24 грудня 2015 }} // Theoretical Computer Science Stack Exchange <br/> [http://cstheory.stackexchange.com/questions/18889/graph-isomorphism-problem Graph Isomorphism Problem] {{Webarchive|url=https://web.archive.org/web/20180329120750/https://cstheory.stackexchange.com/questions/18889/graph-isomorphism-problem |date=29 березня 2018 }} // [[ibid.]] <br/> [http://cstheory.stackexchange.com/questions/31907/complexity-of-simple-undirected-graph-isomorphism-problem/33431#33431 Complexity of simple undirected graph isomorphism problem] {{Webarchive|url=https://web.archive.org/web/20180329121424/https://cstheory.stackexchange.com/questions/31907/complexity-of-simple-undirected-graph-isomorphism-problem/33431#33431 |date=29 березня 2018 }} // [[ibid.]]</ref> can be solved in quasipolynomial <center> <math>\exp \left( \left( \log n \right)^{O \left( 1 \right)} \right)</math> </center> time. The best previous bound for GI was <center> <math> \exp \left( O \left( \sqrt {n\log n} \right) \right),</math> </center> where <math>n</math> is the number of vertices ({{iw2|Юджін M. Лукс|Luks||Eugene M. Luks}}, 1983); for the other two problems, the bound was similar, <center> <math>\quad \qquad \exp \left( \tilde O \left( \sqrt n \right) \right),</math> </center> where <math>n</math> is the size of the permutation domain (Babai, 1983).
<br/>
The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic «local certificates» and combinatorial canonical partitioning techniques. We show that in a well-defined sense, [[граф Джонсона|Johnson graphs]] are the only obstructions to effective canonical partitioning.
</blockquote>
</font></big></big>
|}

== Джерела ==

* [https://web.archive.org/web/20171228054616/http://physical-sciences.uchicago.edu/news/professor-lászló-babai%E2%80%99s-algorithm-next-big-step-conquering-isomorphism-graphs Professor László Babai’s algorithm is next big step in conquering isomorphism in graphs] // Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago <br/> 
* [http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory Mathematician claims breakthrough in complexity theory] {{Webarchive|url=https://web.archive.org/web/20160112090700/http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory |date=12 січня 2016 }}, by Adrian Cho 10 November 2015 17:45 //  Posted in [http://news.sciencemag.org/category/math Math] {{Webarchive|url=https://web.archive.org/web/20151016110956/http://news.sciencemag.org/category/math |date=16 жовтня 2015 }}, Science [[American Association for the Advancement of Science|AAAS]] News
* [http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details] {{Webarchive|url=https://web.archive.org/web/20170917130745/https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ |date=17 вересня 2017 }} + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
* [https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/ Landmark Algorithm Breaks 30-Year Impasse] {{Webarchive|url=https://web.archive.org/web/20170425205152/https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/ |date=25 квітня 2017 }}, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
* [https://rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm/ A Little More on the Graph Isomorphism Algorithm] {{Webarchive|url=https://web.archive.org/web/20170710094259/https://rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm/ |date=10 липня 2017 }} // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
* [http://lenta.ru/news/2015/11/20/graphtheory/ <nowiki>[Ласло]</nowiki> Бабай приблизился к решению «проблемы тысячелетия»] {{Webarchive|url=https://web.archive.org/web/20160530170803/https://lenta.ru/news/2015/11/20/graphtheory/ |date=30 травня 2016 }} // Наука Lenta.ru, 14:48, 20 ноября 2015
: [http://texnomaniya.ru/babaiy-priblizilsya-k-resheniyu-problemi-tisyacheletiya copy] {{Webarchive|url=https://web.archive.org/web/20160304105532/http://texnomaniya.ru/babaiy-priblizilsya-k-resheniyu-problemi-tisyacheletiya |date=4 березня 2016 }} from Lenta.ru // texnomaniya.ru, 20 ноября 2015
* [http://habrahabr.ru/post/273231/ Опубликован быстрый алгоритм для задачи изоморфизма графов] {{Webarchive|url=https://web.archive.org/web/20160807050156/https://habrahabr.ru/post/273231/ |date=7 серпня 2016 }} // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12

== Див. також ==

* {{iw|Список нерозв'язаних задач інформатики|||List of unsolved problems in computer science}}
* [[Група чорної скриньки]]

== Примітки == 
{{reflist}}

{{Лауреати премії Кнута}}

{{DEFAULTSORT:Бабай Ласло}}

[[Категорія:Угорські математики]]
[[Категорія:Лауреати премії Геделя]]
[[Категорія:Лауреати премії Кнута]]
[[Категорія:Науковці Чиказького університету]]
[[Категорія:Комбінаторики]]
[[Категорія:Угорці США]]
[[Категорія:Члени Американської академії мистецтв і наук]]
[[Категорія:Угорські емігранти до США]]
[[Категорія:Переможці Міжнародної математичної олімпіади]]