Теорія навченого
Валіант дав означення: клас понять навченний, якщо існує алгоритм, що за поліноміальний час і розумну кількість прикладів дає майже правильну відповідь з великою ймовірністю.
Чому це важливо
Навчання отримало означення, у якому можна довести неможливість, — і питання «скільки прикладів треба» стало математичним.
Модель відома як імовірно приблизно правильне навчання. Ключове те, що вимога послаблена двічі: відповідь має бути приблизною і лише ймовірно такою. Без цих послаблень майже нічого не навченне. З моделі виросла обчислювальна теорія навчання, зв'язок із розмірністю Вапника-Червоненкіса і бустинг. Валіант отримав премію Тюрінга 2010 року.