לסלו בבאי

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

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

פרסים והוקרה

 פרס המדינה (1988) - על הישגיו הבולטים ברמה הבינלאומית בתחום האלגברה והתיאוריה החישובית ועל ההוראה המצוינת ופעילויותיו ליצירת בית ספר.
 ב-1993 זכה בפרס גדל, לצד שפי גולדווסר, סילביו מיקאלי, שלמה מורן וצ'ארלס ראקוף, על פיתוח המושג של מערכת הוכחה אינטראקטיבית.
 בשנת 2015 נבחר לחבר באקדמיה האמריקאית לאמנויות ולמדעים, וזכה בפרס קנות'.

קישורים חיצוניים



הערות שוליים

קטגוריה:מתמטיקאים הונגרים
קטגוריה:מדעני מחשב הונגרים
קטגוריה:בוגרי אוניברסיטת אטווש לוראנד בודפשט
קטגוריה:סגל אוניברסיטת שיקגו
קטגוריה:זוכי פרס גדל
קטגוריה:חברי האקדמיה ההונגרית למדעים
קטגוריה:בודפשט: אישים
קטגוריה:חברי האקדמיה האמריקאית לאמנויות ולמדעים
קטגוריה:זוכי פרס קנות'
קטגוריה:יהודים זוכי פרס המדינה (הונגריה)
קטגוריה:זוכי פרס דייקסטרה
קטגוריה:אמריקאים שנולדו ב-1950