Mar. 10th, 2011

plakhov: (Default)
Лесли Валиант получил Turing Award - самую почетную награду в области Computer Science. Ура!

Что сделал Валиант:
- создал PAC-learning framework
- показал (вместе с Вазирани), что NP полиномиально сводится к UNIQUE-SAT, а значит, и к PARITY-SAT; это стало первым шагом для доказательства теоремы Тода, а еще это источник некоторых несбыточных мечт для меня лично
- заметил, что умение считать перманент матрицы (почти то же, что детерминант, только все коэффициенты при слагаемых - плюс единицы) означает умение решать #P; это очень странно - интуитивно совершенно не ясно, почему эти две операции настолько отличаются по своей вычислительной сложности
- написал несколько отличных (к сожалению, боюсь, сильно недооцененных) работ о том, как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения
- умудрился придумать noninteracting-fermion quantum circuits из чисто математических соображений, не понимая (по крайней мере, так утверждает Ааронсон), что он на самом деле придумывает

И наверняка еще кучу всего, о чем я не в курсе.

Profile

plakhov: (Default)
plakhov

August 2017

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 02:37 am
Powered by Dreamwidth Studios