Летящий кирпич (kirpich_spb) wrote,
Летящий кирпич
kirpich_spb

Про сборку генома, схемную сложность, CSR'11 и CS центр

Привет, дорогой журнальчик! Писать в тебя опять времени нет совсем, так что опять придётся обо всём понемножку.

Сборка генома


Это картинка из постера, который мы с Максом Алексеевым и Мишей Дворкиным представляли на ISMB 2011. Она должна дать представление о том, как принято собирать геном, даже тем, кто ничего об этом не знает. Да, вынужден признать, что на самой конференции я понял довольно мало. Учиться и учиться мне ещё.

Схемная сложность булевых функций


А это картинка из нашей с Женей Деменковым статьи про нижнюю оценку 3n-o(n) на схемную сложность. Такая же оценка в 1984 году была доказана Блюмом, и с тех пор улучшить её не удаётся никак.

Рассказать же мне здесь хочется не про саму оценку, а про то, как она доказалась. Года три примерно назад мы сообразили, что для получения этой оценки нужно построить булеву функцию, удовлетворяющую некоторому специальному условию (она не должна обращаться в константу ни на каком аффинном подпространстве достаточно большой размерности). Построить же такую функцию явно никак не получалось. Я периодически доставал на конференциях учёных мужей вопросами о том, где же её взять, но никто мне так и не помог. Отчаявшись, я решил спросить на cstheory.stackexchange — и мне тут же ответили, что такая функция была построена совсем недавно (но с абсолютно другой целью). Забавно, что я как-то угадал правильный момент, когда нужно спрашивать. В общем же случае, видимо, разумно спросить на форуме после пары безуспешных попыток найти ответ самому.

The 6th International Computer Science Symposium in Russia

Провели конференцию и провели очень хорошо, я считаю. Таможня вот пыталась подпортить общее впечатление, но мы её побороли.

Программа получилась довольно сильной. Особенно стоит отметить приглашённых докладчиков. Николаю Константиновичу Верещагину, председателю программного комитета, удалось пригласить очень сильных и известных исследователей. Видеозаписи и слайды их лекций доступны в разделе "Invited speakers" на сайте.

За помощь на всех этапах организации конференции хочу сказать огромное спасибо Сане Смалю. Благодарю также Ваню Близнеца, Сашу Головнёва, Женю Деменкова и Ваню Михайлина за помощь в проведении.

Вообще же, что-то я уже третье лето подряд что-нибудь организовываю. Не говоря уже о том, что и во время учебного года у меня организационной работы хватает. Стремительно превращаюсь в менеджеришку, в общем.

Computer Science Сenter
Набор в CS центр идёт полным ходом. Мы хотели успеть всех желающих отсобеседовать до 15 июля, но в последние несколько дней пришла такая гора заявок, что мы не успели. Не первый раз, в общем-то, отбираем студентов уже, и я знаю, что они, студенты, в последний момент любят всё делать, но всё равно неожиданно вышло. В общем, теперь будем пытаться до конца июля всех обработать. Поблагодарить же хочется Женю Смольникову, которая героически все эти заявки разбирает и отвечает на все вопросы поступающих.

Tags: csclub, наука
  • Post a new comment

    Error

    default userpic
  • 3 comments