Teaching a graduate algorithms course this semester (introductory graduate level).  I've been mainly using Kleinberg/Tardos and Cormen/Leiserson/Rivest/Stein textbooks,  a little of Johnsonbaugh/Schaefer and Skiena.

( More on these textbooks... )

Вопрос по самокопирующимся программам (recursion theorem). Ответ:  "Programs cannot self-replicate.  If they did, they could verify whether the program is itself. "  (вируса третьекурсник никогда не видел, что ли? Объяснение такое философское...)

Вопрос к широкой публике -- а читаете ли вы блоги по вашей работе (для нас теоретиков это подборка из Theory Blog Aggregator, в частности блоги Fortnow и Lipton'a, но Slashdot тоже считается)? Пишете ли в оные? Пользуетесь ли StackExchange  и подобными ресурсами, и если да,  то  какими?  И только читаете, или и пишете тоже?

В продолжение вопроса ( Read more... )

Вопрос к вам, знатокам английского. В рекомендательном письме надо сказать кем приходишься студенту -- in which capacity you know the applicant. До этого было просто -- студенты были у меня в классах, и ответ был "in capacity of an instructor". Нынешний студент у меня работает research assistant'ом -- занимается наукой, а я ему за это плачу из ( Read more... )

Не прошло и двух недель как главная канадская газета Globe&Mail опубликовала статью про   P vs. NP и доказательство Деолаликара, под  большой фотографией Стива Кука. Несколько странно что  BBC отреагировали за несколько дней,  даже lenta.ru не особенно отстала -- а канадцы, которым гораздо проще Стива поймать и расспросить, две недели тормозили... ( Read more... )

И вот уже многие из моих немногих френдов пишут о возможном доказательстве P != NP, гуляющем по сети... А было это так.

В субботу Стив Кук послал емайл группе теории Торонтовского универа (включающей бывших аспирантов) мол посмотрите на такое-то доказательство, вроде не полный бред.  Он подобные доказательства получает регулярно, и если не может ( Read more... )

Из забавностей -- на STOC'е вместо кофе с печеньками во второй половине дня выдавали popcorn и кока-колу, имитируя атмосферу кинотеатра. Народу понравилось -- как-никак, разнообразие ;-) 

Три конференции, две недели подряд слушать  доклады. Много интересного, но в какой-то момент начинаешь путаться кто что о чем доказал.

Из интересностей -- много approximation algorithms, непонятно почему. Всё ещё бурно обсуждается unique games conjecture, есть сильные статьи за и сильные статьи против.

( Unique games conjecture это... )

Через неделю, если всё будет хорошо, едем обратно в Ванкувер. На этот раз самой прямой дорогой, должно занять немногим больше недели. Дорога через Питтсбург, Чикаго, потом по южной Дакоте, и дальше на запад.

Жалко покидать Институт, жалко что не получилось тут побыть подольше. Уникальное место, такая ivory tower где заниматься чистой наукой ( Read more... )

От R. I., известного теоретика с архетипичной рассеяностью ( Read more... )