Может быть, для многих это уже давно не новость, но премию Геделя в 2007 году получили Александр Разборов (Математический институт им. Стеклова РАН, Россия) и Steven Rudich (Carnegie Mellon University, USA) за работу о так называемых "естественных доказательствах" ("natural proofs"). Работа была впервые представлена на Twenty-sixth Annual ACM Symposium on Theory of computing в 1994 году. _Премия Геделя была учреждена SIGACT ACM (Special Interest Group on Algorithms and Computing Theory) и EATCS (European Association for Theoretical Computer Science) и присуждается с 1993 года. Ею награждают за важнейшие статьи работы по математической логике и теоретической информатике._ На фотографии ниже: лауреаты премии Геделя 2007 - Александр Разборов и Steven Rudich. Цитата с Ascribe.org:

...the authors found that a wide class of proof techniques cannot be used to resolve this challenge unless widely held conventions are violated. These conventions involve well-defined instructions for accomplishing a task that rely on generating a sequence of numbers (known as pseudo-random number generators). The authors' findings apply to computational problems used in cryptography, authentication, and access control. They show that other proof techniques need to be applied to address this basic, unresolved challenge. ... The paper proves that there is no so-called "Natural Proof" that certain computational problems often used in cryptography are hard to solve. Such cryptographic methods are critical to electronic commerce, and though these methods are widely thought to be unbreakable, the findings imply that there are no Natural Proofs for their security.

Англоязычные блоггеры и СМИ почти как один характеризуют работу как "выдающуюся", а в рунете, к сожалению, удалось найти всего пару упоминаний о награждении российского математика. К слову сказать, лауреаты премии Геделя 2007 были объявлены еще в мае. В связи с этим снова обращаюсь к нашим читателям. Это коллективный блог, и добавлять в него записи может каждый зарегистрированный пользователь. У вас есть интересная информация по theoretical computer science - от новостей до анонса собственного исследования, проекта? Пишите!