Дистанционно регулярные антиподальные накрытия полных графов образуют обширный класс графов, который тесно связан со многими важными алгебраическими или комбинаторными объектами, такими как обобщенные матрицы Адамара, проективные плоскости, обобщенные четырехугольники, делимые дизайны и коды. Кроме того, такие накрытия оказываются источником некоторых специальных множеств равноугольных прямых (ETFs, SIC-POVMs), применяемых в дискретной геометрии и квантовой теории информации. Несмотря на то, что полное их описание представляется недостижимым, можно надеяться на получение новых их конструкций и частичную классификацию при дополнительных ограничениях групповой природы.

Доклад посвящен исследованию реберно-транзитивных дистанционно регулярных антиподальных накрытий полных графов. Пусть $\Gamma$ --- это такое накрытие и $G$ --- это его полная группа автоморфизмов. Обозначим через $\Omega$ и $\mathcal{S}$ множество вершин накрытия $\Gamma$ и множество орбиталов группы $G$ на $\Omega$ соответственно. Тогда пара ${\rm Inv}(G)=(\Omega,\mathcal{S})$ образует шурову схему отношений, ассоциированную с группой $G$.
При этом множество дуг накрытия является объединением набора из не более двух орбиталов группы $G$ и кроме того, $G$ индуцирует $2$-однородную группу подстановок $G^{\Sigma}$ на множестве $\Sigma$ антиподальных классов накрытия $\Gamma$, которая ввиду теорем Кантора и Бернсайда является либо почти простой, либо аффинной. В данном докладе будут представлены результаты автора по классификации накрытий $\Gamma$, полученные в обоих указанных случаях для $G^{\Sigma}$, а также по их характеризации как графов базисных отношений схем ${\rm Inv}(G)$ в случае, когда $G^{\Sigma}$ --- почти простая группа.

We introduce the following variant of the VC-dimension. Given S ⊆ {0, 1} and a positive integer d, we define U_d(S) to be the size of the largest subset I ⊆ [n] such that the projection of S on every subset of I of size d is the d-dimensional cube. We show that determining the largest cardinality of a set with a given Ud dimension is equivalent to a Turán-type problem related to the total number of cliques in a d-uniform hypergraph. This allows us to beat the Sauer-Shelah lemma for this notion of dimension. We use this to obtain several results on Σ_3^k-circuits, i.e., depth-3 circuits with top gate OR and bottom fan-in at most k:

* Tight relationship between the number of satisfying assignments of a 2-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. ’00).

* Improved Σ_3^3 -circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement.

This is a joint work with Peter Frankl and Navid Talebanfard.

В докладе будет рассказано о серии результатов о различных подходах к доказательству нижних оценок на размер формул для булевых функций методами коммуникационной сложности.

Сначала будет рассказано об улучшении работы Меира и Вигдерсона о предсказании битов строки при помощи семейств сертификатов. Улучшение позволяет получить альтернативное доказательство для точной нижней оценки на формулы формулы глубины три (имеются в виду формулы с гейтами неограниченной арности) для функций чётности и внутреннего произведения.

Далее будет рассказано о гипотезе Карчмера - Раза - Вигдерсона и её варианте для композиции с мультиплексером. При рассмотрении этой задачи естественным образом возникает необходимость рассмотреть альтернативную модель вычисления для коммуникационной сложности. В качестве такой модели будет предложена концепция полудуплексной коммуникационной сложности и рассказано о результатах в этой области.

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