Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Пятница 21.01. Д. М. Ицыксон (ПОМИ РАН): "Нижние оценки и вопросы оптимальности для систем доказательств"

Speaker: 
Д. М. Ицыксон (ПОМИ РАН)
Date: 
Friday, January 21, 2022 - 13:00
Place: 
Zoom
Abstract: 

В докладе будет дан обзор результатов докладчика на следующие темы:

(1) сложность вывода в системах доказательств, основанных на OBDD;
(2) сложность вывода цейтинских формул в зависимости от древесной ширины графа;
(3) нижние оценки на сложность вывода в подсистемах системы Res(+) (резолюция над дизъюнкциями линейных равенств по модулю 2); 
(4) оптимальные эвристические и вероятностные аксепторы.

Подключиться к докладу можно по ссылке: https://zoom.us/j/95294301096?pwd=dXJXOWtqcjVZcy9qdXZZUTNFRjl0UT09



Воскресенье 26.12. Kirill Simonov (University of Bergen): "Fine-grained complexity of graph homomorphism for bounded cliquewidth"

Speaker: 
Kirill Simonov (University of Bergen)
Date: 
Sunday, December 26, 2021 - 12:00
Place: 
PDMI & Zoom (hybrid format)
Abstract: 

For a fixed graph H, consider the graph homomorphism problem Hom(H), i.e. find an edge-preserving mapping from V(G) to V(H). Specifically, if H is the complete graph K_k, Hom(H) is equivalent to k-Coloring. Thus, even in this special case the problem is NP-complete for each k ≥ 3, and it is also NP-complete for nearly all other graphs H.

Okrasa и Rzaͅżewski [SODA 2020] showed the following dichotomy for Hom(H) with respect to treewidth of G: Hom(H) can be solved in time |H|^tw(G) poly(|V(G)|), but for any ε > 0 there is no algorithm for Hom(H) with running time (|H| - ε)^tw(G) poly(|V(G)|), assuming SETH.
As stated, the result holds only if H is a projective core, however a similar dichotome follows for nearly all graphs. Moreover, assuming a long-standing hypothesis from algebraic graph theory, this classsification covers all graphs H.

In this talk, we show a similar dichotomy with respect to cliquewidth of G. Cliquewidth, similarly to treewidth, is a structural width parameter of the graph, albeit a more general one: cliquewidth is always bounded when treewidth is bounded, but also for other dense graph classes, e.g. cliques. The conditions under which the dichotomy is given repear the conditions obtained for treewidth, however the preciese running time bound is f(H)^cw(G) poly(|V(G)|), where cw(G) is the cliquewidth of G, and f(H) is a certain structural parameter of H, specifically the number of distinct open neighborhoods of subsets of V(H).

This is a joint work with Robert Ganian, Thekla Hamm, Viktoria Korchemna and Karolina Okrasa.



Пятница 12.11. Людмила Циовкина ( ИММ УрО РАН): " Накрытия полных графов и связанные с ними схемы отношений"

Speaker: 
Людмила Циовкина ( ИММ УрО РАН)
Date: 
Friday, November 12, 2021 - 11:00
Place: 
Zoom
Abstract: 

Дистанционно регулярные антиподальные накрытия полных графов образуют обширный класс графов, который тесно связан со многими важными алгебраическими или комбинаторными объектами, такими как обобщенные матрицы Адамара, проективные плоскости, обобщенные четырехугольники, делимые дизайны и коды. Кроме того, такие накрытия оказываются источником некоторых специальных множеств равноугольных прямых (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}$ --- почти простая группа.



Пятница 29.10. Svyatoslav Gryaznov: "A variant of the VC-dimension with applications to depth-3 circuits"

Speaker: 
Svyatoslav Gryaznov
Date: 
Friday, October 29, 2021 - 11:30
Place: 
Zoom
Abstract: 

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.



Понедельник 11.10. А.В. Смаль (ПОМИ РАН): "Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности"

Speaker: 
А.В. Смаль (ПОМИ РАН)
Date: 
Monday, October 11, 2021 - 11:00
Place: 
Zoom
Abstract: 

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

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

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

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


Pages