Майкл Лабі

Майкл Джордж Лабі (англ. Michael George Luby) — американський математик і вчений, віце-президент з технологій в компанії Qualcomm, співзасновник і колишній директор з технологій Digital Fountain.

Майкл Лабі
Народився	20 століття
Країна	США
Діяльність	криптограф, інформатик, інженер
Alma mater	Массачусетський технологічний інститут (1975)[1] Університет Каліфорнії (Берклі) (1983)[1]
Науковий керівник	Річард Карп[2]
Членство	Association for Computing Machinery[3]
Нагороди	Медаль Річарда Геммінга (2012) Дійсний член ACMd (2015) премія Канеллакіса (2015) IEEE Eric E. Sumner Awardd (2007)

Навчання

Майкл Лабі здобув ступінь бакалавра з математики в Массачусетському технологічному інституту в 1975 році. У 1983 році йому було присвоєно ступінь доктора філософії (англ. Ph.D.) в галузі комп'ютерних наук в Університеті Каліфорнії, Берклі.

Наукові досягнення

В теорії кодування він відомий тим, що керував винаходом кодів Торнадо та LT кодів. 

У 1996—1997 роках, працюючи в Міжнародному інституті комп'ютерних наук (ICSI), він очолював команду, яка винайшла коди Торнадо. Це були перші LDPC-коди, що базуються на дизайні неправильного ступеня, який виявився ключовим для всіх пізніх кодів конструкції LDPC, які гарантовано досягти пропускної здатності каналу для каналу стирання та мають лінійний алгоритм кодування та декодування. 

У 1998 році Майкл Лабі залишив ICSI та перейшов у компанію Digital Fountain, а незабаром у 1998 році він винайшов LT коди, перші практичні коди фонтану. Qualcomm придбала Digital Fountain в 2009 році.^[4]

У криптографії він відомий за його внесок у демонстрацію того, що будь-яка одностороння функція може бути використана як основа для власної криптографії, а також для його аналізу. Над цим Майкл Лабі працював у співпраці з Чарльзом Ракофом із побудови шифру Фейстеля. Його розподілений алгоритм для пошуку максимальної незалежної множини у комп'ютерній мережі також був дуже впливовим. Він також зробив внесок у середньому разі складності (англ. average-case complexity).^[5]

Отримані нагороди

• 2002 р. — IEEE Information Theory Society — нагородний лист за провідне проектування та аналіз першого нерегулярного коду LDPC, що виправляє помилки^[6]
• 2003 р. — видатна премія SIAM за основний документ, що показує, як побудувати криптографічно нерозривний псевдовипадковий генератор з будь-якої односторонньої функції 
  
• 2007 р. — IEEE Eric E. Sumner Award  (разом з Аміном Шокроллахі) «для модернізації математики, дизайну інтернету та мобільного мовлення, а також успішної стандартизації»^[7]
• 2009 р. — премія ACM SIGCOMM ^[8]
• 2012 р. — Медаль Річард Геммінга (разом з Аміном Шокроллахі «за концепцію, розробку та аналіз практичних кодів без наслідків»^[9]
• 2014 р. -  Національна технічна академія  США «За внесок у теорію кодування, включаючи створення кодів без комор»
• 2015 р. — членство в Асоціації обчислювальної технки.^[10]
• 2015 р. — премія Канеллакіса ^[11] «за новаторський внесок у стирання коректувальних кодів, які мають важливе значення для підвищення якості передачі відео у різних мережах».
• 2016 р. — премія ACM Edsger W. Dijkstra у розподілених обчисленнях «Приз нагороджується за видатні роботи на принципах розподілених обчислень, значення та вплив яких на теорію та / або практику розподілених обчислень, що було очевидними протягом щонайменше десятиліття».
  

Вибрані публікації

• Luby, Michael (1986). «A Simple Parallel Algorithm for the Maximal Independent Set Problem». SIAM Journal on Computing. 15 (4): 1036—1053. doi:10.1137/0215074.
• Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby (1989). «On the theory of average-case complexity». Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (STOC): 204—216.