Внезапно уже сейчас (до завтрашнего утра) просят составлять план по спецкурсам на осенний семестр. Обычно я этот опрос делаю после завершения курса, но теперь придётся заранее. Традиционно я читаю спецкурс на одну из продвинутых тем курса сложности вычислений. Раньше было только осенью, но последние 2 года по просьбам слушателей продолжаю и весной. Вот несколько возможных тем, в комментариях будут примерные программы, а также неанонимный консультативный опрос (т.е. будет выбран не обязательно вариант, набравший большинство голосов).
Вероятностно проверяемые доказательства - это то, что мы проходим сейчас, так что подробное представление, думаю, не нужно. В этом курсе доказывается "большая" PCP-теорема и её вариации вроде трёхбитной теоремы Хостада, а также изучаются сложности приближённого решения разных конкретных задач. Этого курса давно не было, так что мои симпатии на его стороне.
Псевдослучайность и дерандомизация - этот курс читается сейчас, так что будет повторён только при очень большом интересе. Там изучаются разные псевдослучайные конструкции, которые в конечном итоге могут привести к доказательству BPP=P.
Вычислительная сложность задач поиска - изучается сложность задач поиска, прежде всего тех, где ответ точно есть (и потому вопрос о существовании ответа тривиален). Есть много приложений к разного рода экономическим моделям на базе теорем о неподвижных точках.
Рациональные интерактивные доказательства - изучается делегирование вычислений, при котором мощный сервер выполняет вычисления за деньги, максимизируя вознаграждение. Нужно так выстроить стимулы, чтобы при этом сервер выявил правильный ответ.

Можно также предлагать свои варианты, если мне один из них приглянётся, то можно будет изучить что-нибудь вместе. Имеющиеся программы курсов и опрос в комментариях.