לסלו בבאי

מתוך ויקיפדיה, האנציקלופדיה החופשית
לסלו בבאי
Babai László
לידה 20 ביולי 1950 (בן 73)
בודפשט, הרפובליקה העממית ההונגרית עריכת הנתון בוויקינתונים
ענף מדעי קומבינטוריקה, חבורה סופית, תורת הסיבוכיות, מערכת הוכחה אינטראקטיבית עריכת הנתון בוויקינתונים
מקום לימודים
מנחה לדוקטורט פאל טוראן, Vera T. Sós עריכת הנתון בוויקינתונים
מוסדות אוניברסיטת שיקגו עריכת הנתון בוויקינתונים
תלמידי דוקטורט Mario Szegedy, Samuel Kutin, Thomas Hayes, Evelin Toumpakari, Daniel Štefankovič, Peter Kimmel, Katalin Friedl, Aytek Erdil, Murali Krishnan Ganapathy, Paolo Codenotti, Sourav Chakraborty, Youming Qiao, Satyanarayana V. Lokam, Albert J. Goodman, Péter Hajnal, Carsten Lund, גאבור טרדוש, Robert M. Beals, Péter Pál Pálfy, José Augusto Ramos Soares, Barry Guiduli, Lajos Rónyai, Tamás Lengyel, John Wilmes עריכת הנתון בוויקינתונים
פרסים והוקרה
האתר הרשמי
לעריכה בוויקינתונים שמשמש מקור לחלק מהמידע בתבנית

לאסלו "לצי" בבאיהונגרית: Babai László; נולד ב-20 ביולי 1950 בבודפשט, הונגריה) הוא פרופסור למתמטיקה ולמדעי המחשב באוניברסיטת שיקגו. מחקריו מתמקדים בתורת הסיבוכיות, אלגוריתמים, קומבינטוריקה וקבוצות סופיות, עם דגש על יחסי הגומלין בין תחומים אלה.

הישגים[עריכת קוד מקור | עריכה]

בשנת 2015 הוכיח שבעיית הכרעה של גרפים איזומורפיים (אנ') ניתנת לחישוב בזמן קואזי-פולינומי, בהשוואה לפתרון נאיבי שרץ בזמן !n עבור קלט (גודל גרף) n. בשנת 2017 גילה הראלד הלפגוט טעות בהוכחה זו, ובבאי תיקן את הטעות.[1]

פרסים והוקרה[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא לסלו בבאי בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Erica Klarreich, Graph Isomorphism Vanquished — Again, Quanta Magazine, January 14, 2017
ערך זה הוא קצרמר בנושא אישים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.