„Babai László” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a →Források: Kategória:Élő személyek hozzáadása |
Syp (vitalap | szerkesztései) Címke: HTML-sortörés |
||
31. sor:
Több mint száznyolcvan kombinatorikával, algebrával és számítástudománnyal foglalkozó tudományos publikációja jelent meg, amelyeket jelentős részben [[angol nyelv]]en adott ki. [[Erdős-szám]]a 1.<ref>László Babai, Paul Erdős, Stanley M. Selkow: Random Graph Isomorphism. SIAM J. Comput. 9(3): 628-635 (1980)</ref>
=== Gráfizomorfizmus kvázipolinomiális időben ===
2015. november 10. és december 1. között Babai három előadást tartott a Chicagói Egyetem «Kombinatorika és elméleti számítástudomány» szemináriumán «[[Gráfizomorfizmus]] [[kvázipolinomiális]] időben» témakörben. Az általa körvonalazott bizonyítás megmutatta, hogy a [[gráfizomorfizmus-probléma]] [[kvázipolinomiális]] időben (a polinomiális és az exponenciális közötti idő alatt) megoldható.<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 November 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] // November 4, 2015, [https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ A Fast Graph Isomorphism Algorithm] // November 11, 2015</ref><ref>[http://www.math.uchicago.edu/calendar?calendar=Combinatorics%20and%20Theoretical%20Computer%20Science Combinatorics and Theoretical Computer Science] calendar // [http://theory.cs.uchicago.edu/index.php Theoretical Computer Science at the University of Chicago]. 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] // MIT Technology Review, by Tom Simonite on November 13, 2015</ref> Az előadás videofelvételét 2015. december 10-én tették közzé<ref>[https://www.youtube.com/watch?v=qYIhA3O9Nz0 Graph Isomorphism in Quasipolynomial Time I], seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015</ref>, majd egy előzetes változata a cikknek másnap felkerült az [[arXiv.org]] oldalra.<ref name=arXiv>László Babai. [http://arxiv.org/pdf/1512.03547v1 Graph Isomorphism in Quasipolynomial Time], 84 pages / [http://arxiv.org/abs/1512.03547v1 abstract] // [[arXiv.org]] > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT</ref>
{{rejtett|header=Absztrakt|content=
<blockquote>
We show that the [[Gráfizomorfizmus-probléma|Graph Isomorphism (GI) problem]] and the related problems of String Isomorphism<ref>[https://books.google.com/books?id=YBlrCQAAQBAJ&pg=PA103 '''Definition 2.3.''' String Isomorphism], in: [http://www.springer.com/gp/book/9783642020964 Transactions on Computational Science V]. Special Issue on Cognitive Knowledge Representation. [https://books.google.com/books?id=R2SvCCXPChMC&pg=PR11 Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan] / [[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] // [http://groupprops.subwiki.org/wiki/Main_Page The Group Properties Wiki] (beta)</ref><ref>[http://cstheory.stackexchange.com/questions/25868/complexity-of-the-coset-intersection-problem Complexity of the coset intersection problem] // Theoretical Computer Science Stack Exchange, asked Sep 25 2014 at 9:43</ref> can be solved in quasipolynomial <math>\exp \left( \left( \log n \right)^{O \left( 1 \right)} \right)</math> time. The best previous bound for GI was <math> \exp \left( O \left( \sqrt {n\log n} \right) \right),</math> where <math>n</math> is the number of vertices ([[Eugene M. Luks|Luks]], 1983); for the other two problems, the bound was similar, <math>\quad \qquad \exp \left( \tilde O \left( \sqrt n \right) \right),</math> 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-gráf|Johnson graphs]] are the only obstructions to effective canonical partitioning.
</blockquote>
}}
== Díjai, elismerései ==
| |||