А можно у вас совета спросить? Извините за анонимность.
Вот я специалист, окончил Казанский университет, прикладной математик. Диплом синий, с двумя тройками. В аспирантуру идти не стал. Работаю программистом. Публикаций и побед нет.

Но я живо интересуюсь многими вещами из TCS, я знаю какие-то базовые вещи, вроде вероятностного метода, экспандеров, альтернирования, полиномиальной иерархии, ну и так далее по Ароре-Бараку (со всем этим я ознакомился в свободное время, поскольку специализация у меня была "исследование операций", а не "теоретическая кибернетика"). Я изучал в свое время байесовские сети, сейчас знакомлюсь с другими областями машинного обучения. Очень люблю теорию чисел (элементарную и алгебраическую), абстрактную алгербу, теорию категорий, логику.

В университете этим заняться профессионально не удалось, там главенствовала муштра -- решение примеров по трафарету. Было несколько курсов, которые эти штудии разбавляли, где надо было придумать алгоритм или доказательство, они меня очень радовали, но их было немного.

Так вот, стоит мне пытаться поступить в Академический Университет? Или же поступающих так много, что одной увлечённости мало, а нужен и приличный послужной список?

Стоит. Главное, способны ли вы алгоритмы придумывать, задачи решать и теоремы доказывать. Ну, и помните ли базовую математику и то, чему Вас учили. Это мы всё на собеседовании и проверяем. Собственно, пример теста висит на сайте (хотя и кроме него беседуем полчаса не просто так). Даже в этом году ещё не поздно :)

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

Кстати, к теоркибу книжка Арора-Барак ни малейшего отношения не имеет. К теоркибу принято совершенно другие вещи относить...

Вот у нас так на факультете сложилось, что вычислительной сложностью на КТК занимаются, и хоть что-то из учебника Ароры-Барака только там и можно узнать.

Спасибо большое, что ответили, очень хочется приехать в Петербург, учиться в академическом университете, посещать CS Club, я бы и в этом году приехал, да денег бы подкопить на учебу и на жизнь.

Мне кажется, что в Казани есть, с кем пообщаться по части теории сложности (Фарид Мансурович). А так, конечно, готовьтесь, приезжайте. Так, как в Вышке (по 10 тыс.), у нас платят, правда, только лучшим, но - работаем над этим вопросом...

Я руководствовался тем, что в исходном посте написано...