Просмотр кода страницы Бабаи, Ласло

{{учёный
 |оригинал имени = {{lang-hu|{{Hungarianname|Babai László}}}}
}}
'''Ласло Бабаи''' ({{lang-hu|{{Hungarianname|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=2014-02-11 }} // [http://people.cs.uchicago.edu/~laci/CV.html Babai’s web site] {{Wayback|url=http://people.cs.uchicago.edu/~laci/CV.html |date=20171107003055 }}</ref> — венгерский и американский учёный, профессор математики и информатики (computer science) в [[Чикагский университет|Чикагском университете]]. Его исследования сосредоточены в следующих отраслях: [[теория сложности вычислений]], [[теория алгоритмов]], [[комбинаторика]], и [[Конечная группа|конечные группы]] с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов.<ref name=cv/>

== Биография ==
Бабаи изучал математику в [[Будапештский университет|Будапештском университете]] имени [[Этвёш, Лоранд|Лоранда Этвёша]] с 1968 по 1973 год, получил Ph.D. в [[Венгерская академия наук|Венгерской академии наук]] в 1975 году, и получил D.Sc. в Венгерской академии наук в 1984 году.<ref name=cv/><ref>{{MathGenealogy|id=78102}}</ref> В США работает с 1987 года.

Автор [[Лас-Вегас (алгоритм)|алгоритма Лас-Вегас]] (1979), версии [[Метод Монте-Карло|метода Монте-Карло]].<ref>«'Ласло Бабаи»', [http://people.cs.uchicago.edu/~laci/lasvegas79.pdf Monte-Carlo algorithms in graph isomorphism testing] {{Wayback|url=http://people.cs.uchicago.edu/~laci/lasvegas79.pdf |date=20171208122851 }}, Université de Montréal, D. M. S. № 79-10.</ref>

== Graph Isomorphism in Quasipolynomial Time ==
С 10 ноября по 1 декабря 2015 года на семинаре «Combinatorics and Theoretical Computer Science» в [[Чикагский университет|Чикагском университете]] сделал три доклада «Graph Isomorphism in [[:en:quasi-polynomial time|Quasipolynomial Time]]», в которых изложил алгоритм, который решает {{iw|проблема изоморфизма графов|проблему||Graph isomorphism problem}} [[Изоморфизм графов|изоморфизма графов]] за квазиполиномиальный <math>\exp \left( P \left( \log(n) \right) \right)</math> период времени, где <math>\displaystyle n\ -</math> количество вершин, <math>P \left( \log(n) \right) \ -</math> многочлен от <math>\log(n)</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] {{Wayback|url=https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ |date=20170710180503 }} // November 4, 2015, [https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ A Fast Graph Isomorphism Algorithm] {{Wayback|url=https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ |date=20170729155154 }} // 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=2015-12-22 }} calendar // [http://theory.cs.uchicago.edu/index.php Theoretical Computer Science at the University of Chicago] {{Wayback|url=http://theory.cs.uchicago.edu/index.php |date=20171022042014 }}. 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] {{Wayback|url=http://www.technologyreview.com/news/543511/claimed-breakthrough-slays-classic-computing-problem-encryption-could-be-next/ |date=20160122074854 }} // 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] {{Wayback|url=https://www.youtube.com/watch?v=qYIhA3O9Nz0 |date=20180912094208 }}, lecture seminar 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] {{Wayback|url=http://arxiv.org/abs/1512.03547v1 |date=20171122174710 }} // [[arXiv.org]] > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT</ref>.
{{hider | title = abstract <!-- резюме / --> | title-style = text-align: left; | content-style = text-align: left; | hidden=y | content = 
<font face="Times New Roman">
<blockquote>
We show that the [[Изоморфизм графов|Graph Isomorphism]] {{iw|проблема изоморфизма графов|(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] {{Wayback|url=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=20180328231735 }} // Google Books, in: [http://www.springer.com/gp/book/9783642020964 Transactions on Computational Science V] {{Wayback|url=http://www.springer.com/gp/book/9783642020964 |date=20180329120833 }}. 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. Гаврилова, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan] {{Wayback|url=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=20180328231737 }} / {{iw|Lecture Notes in Computer Science}} / Volume 5540, [[Springer Verlag]], 2009</ref> (under action group) (SI) and Coset Intersection (CI)<ref>[http://groupprops.subwiki.org/wiki/Coset_intersection_problem Coset intersection problem] {{Wayback|url=http://groupprops.subwiki.org/wiki/Coset_intersection_problem |date=20180329054352 }} // [http://groupprops.subwiki.org/wiki/Main_Page The Group Properties Wiki] {{Wayback|url=http://groupprops.subwiki.org/wiki/Main_Page |date=20171022031513 }} (beta)</ref><ref>[http://cstheory.stackexchange.com/questions/25868/complexity-of-the-coset-intersection-problem Complexity of the coset intersection problem] {{Wayback|url=http://cstheory.stackexchange.com/questions/25868/complexity-of-the-coset-intersection-problem |date=20151224104154 }} // Theoretical Computer Science Stack Exchange <br> [http://cstheory.stackexchange.com/questions/18889/graph-isomorphism-problem Graph Isomorphism Problem] {{Wayback|url=http://cstheory.stackexchange.com/questions/18889/graph-isomorphism-problem |date=20180329120750 }} // [[ibid.]] <br> [http://cstheory.stackexchange.com/questions/31907/complexity-of-simple-undirected-graph-isomorphism-problem/33431#33431 Complexity of simple undirected graph isomorphism problem] {{Wayback|url=http://cstheory.stackexchange.com/questions/31907/complexity-of-simple-undirected-graph-isomorphism-problem/33431#33431 |date=20180329121424 }} // [[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 ({{iw|Юджин 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 group by theoretic «local certificates and combinatorial canonical partitioning techniques. We show that in a well-defined sense, {{iw|граф Джонсона|Johnson graphs|uk}} are the only obstructions to effective canonical partitioning.
</blockquote>
</font>
}}

== См. также ==
* [[:en:List of unsolved problems in computer science|List of unsolved problems in computer science]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20171228054616/http://physical-sciences.uchicago.edu/news/professor-l%C3%A1szl%C3%B3-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 
* [http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory Mathematician claims breakthrough in complexity theory] {{Wayback|url=http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory |date=20160112090700 }}, by Adrian Cho 10 November 2015 17:45 // Posted in [http://news.sciencemag.org/category/math Math] {{Wayback|url=http://news.sciencemag.org/category/math |date=20151016110956 }}, Science [[:en: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] {{Wayback|url=http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ |date=20170917130745 }} + 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] {{Wayback|url=https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/ |date=20170425205152 }}, 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] {{Wayback|url=https://rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm/ |date=20170710094259 }} // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
* [http://lenta.ru/news/2015/11/20/graphtheory/ <nowiki>[Ласло]</nowiki> Бабай приблизился к решению «проблемы тысячелетия»] {{Wayback|url=http://lenta.ru/news/2015/11/20/graphtheory/ |date=20160530170803 }} // Наука Lenta.ru, 14:48, 20 ноября 2015
: [http://texnomaniya.ru/babaiy-priblizilsya-k-resheniyu-problemi-tisyacheletiya copy] {{Wayback|url=http://texnomaniya.ru/babaiy-priblizilsya-k-resheniyu-problemi-tisyacheletiya |date=20160304105532 }} from Lenta.ru // texnomaniya.ru, 20 ноября 2015
* [http://habrahabr.ru/post/273231/ Опубликован быстрый алгоритм для задачи изоморфизма графов] {{Wayback|url=http://habrahabr.ru/post/273231/ |date=20160807050156 }} // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
: [http://it-ua.info/news/2015/12/16/opublkovano-shvidkiy-algoritm-dlya-zadach-zomorfzmu-grafv.html Опубликован быстрый алгоритм для задачи изоморфизма графов] {{Wayback|url=http://it-ua.info/news/2015/12/16/opublkovano-shvidkiy-algoritm-dlya-zadach-zomorfzmu-grafv.html |date=20170703165721 }} // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30
{{вс}}
{{Лауреаты премии Кнута}}
{{Лауреаты премии Гёделя}}

[[Категория:Математики Венгрии]]
[[Категория:Лауреаты премии Гёделя]]
[[Категория:Лауреаты премии Кнута]]
[[Категория:Преподаватели Чикагского университета]]