В Петербурге хочется рассказать про две вещи:

• Про один из результатов статьи "The limits of two-party differential privacy" с FOCS 2010. Собственно "differential privacy" в этой части почти нет, быстро устанавливается связь с "semi-random sources" и дальше речь идет о экстракторах для них. Весьма неожиданно и красиво, по-моему. В это воскресенье ( Read more... )

Встретил сегодня в АФТУ Колю vyahhi. Оказывается, создается магистерская программа по биоинформатике. Вроде на первый взгляд всё звучит довольно разумно и достаточно глубоко (например, про суффиксные структуры данных будет рассказано). Набор идёт ( Read more... )

Я уже не один год считаю, что в Петербурге ужасно не хватает чего-то вроде ШАД (см. программу). Поездка в Москву добавила уверенности в этом настолько, что я даже решил об этом написать здесь. Аргументов настолько много, что я их сразу писать не буду, потому что возможно, что это и так всем очевидно. Если нет, то могу написать.

Мне предлагают в Америке поучаствовать в воркшопе(!) для 13-летних девочек. Там надо что-нибудь минут на 20 девочкам рассказать про Computer Science, а потом минут 30 что-нибудь с ними поделать.

Идеи и вопросы:

• Рассказать про знакомые девочкам сервисы что-нибудь интересное (про поиск Google, про Facebook), кстати, что?
  
• Рассказать что-нибудь и ( Read more... )

Друзья, кажется, среди вас много людей, которые разбираются в анализе данных. Я в нем ничего не понимаю, так что некоторое время назад мне даже пришлось отказаться от того, чтобы прорецензировать статью по Data Mining. Теперь появилось свободное время, чтобы наверстать упущенное и все-таки узнать хоть что-нибудь из этой области ( Read more... )

После этой записи я написал письмо Антону Геращенко с вопросом о том, как создать свой сайт для вопросов из TCS на движке StackExchange. Оказалось, что проблем на этом пути хватает --- StackExchange дает free trial только на 45 дней и т.п. А главное, что у сообщества нет четкого понимания необходимости такого сайта (см. тогдашний пост на meta. ( Read more... )

Сегодня удалось наблюдать замечательное. На Mathoverflow появилась красивая комбинаторика, начало доказательства которой предложил Питер Шор (да, тот которого алгоритм). Я честно пытался его доделать, но в это время красивую доделку предложил Сергей Иванов из ПОМИ.

Увы, на Mathoverflow по-прежнему мало Computer Science. Зато народ можно удивить ( Read more... )

Случайно заметил на кафедре в АФТУ книгу "Графы. Модели вычислений. Структуры данных", материал которой соответствует программе курса по алгоритмам на ВМК ННГУ.

Можете попробовать догадаться, что скрывается за следующими терминами из книги (или нажать Ctrl-A):

• Шарниры (в графе) = Точки сочленения
  
• Равнодоступная адресная машина (РАМ) = RAM
  
• ( Read more... )

Провел сегодня последнее занятие на спецкурсе. Занятие было не обязательное, поскольку зачет уже был, так что можно было рассказывать то, что хочется. Очень просили рассказать про то, как что-нибудь взломать. Пришлось расстроить, сказав, что об этом я рассказывать не буду, поскольку теоретического интереса в этом особого нет, и предупредить, что ( Read more... )

У меня вопрос к читателям этого журнала, которые занимаются/интересуются теоретической информатикой: если бы вас попросили выбрать лучший результат в этой области, полученный учёными, работавшими в момент получения этого результата в России (не СССР), то что бы вы выбрали ( Read more... )