# Schedule Week #1: May 31 – June 4, 2021

Zoom meeting information
Meeting ID: 858 0566 9192 Zoom link
Password: first 6 decimal places of π after the decimal point
May 31,
Monday
June 1,
Tuesday
June 2,
Wednesday
June 3,
Thursday
June 4,
Friday
Mini-symposia with plenary talks
Stefano Boccaletti and José Mendes
Institute for Complex Systems, Italy and University of Aveiro, Portugal
Advances in complex networks' theory and applications
14.00 - 14.10
MSK, UTC +3
Opening remarks by the Workshop's chairmen
14.10 - 15.00
MSK, UTC +3
Plenary talk
José Mendes University of Aveiro, Portugal
Show abstract   🡣
Hide abstract   🡡

Using the SIS model we will present a study about the phenomenon of localization in highly heterogeneous networks in which strongly connected nodes (hubs) play the role of centers of localization. We find that in this model the localized states below the epidemic threshold are metastable. The longevity and scale of the metastable outbreaks do not show a sharp localization transition, instead there is a smooth crossover from localized to delocalized states as we approach the epidemic threshold from below.

We will also show results on the same SIS model on unweighted and weighted networks. In contrast to the well-recognized point of view that diseases infect a finite fraction of vertices right above the epidemic threshold, we show that diseases can be localized on a finite number of vertices, where hubs and edges with large weights are centers of localization.

15.00 - 15.25
MSK, UTC +3
Invited talk
Daniil Musatov MIPT, Russia
Fair division on a graph and of a graph
Show abstract   🡣
Hide abstract   🡡

Fair division is a vast topic that brings attention of mathematicians and economists for decades. The general framework is the following: some set of agents want to split among themselves some set of goods such that some fairness condition is satisfied. An additional network structure may be added to the set of agents as well as to the set of goods. We call the first framework fair division on a graph and the second one - fair division of a graph. In these settings some new notions of fairness emerge. For instance, when a network of agents is specified, local envy-freeness means that every agent values her own bundle more than the bundle of any of her neighbors. In the same setting local proportionality means that every agent thinks that his bundle is at least as valuable as the average of his neighbors' bundles. When a network of goods is specified, one may require that all bundles are connected fragments of this network. For a given fairness notion, one may ask whether such a division exists and, if it does, how hard is it to find it. In the talk we will present some novel results about computational complexity of this problem for some particular types of the graphs.

15.25 - 16.00
MSK, UTC +3
Invited talk
Miguel Romance King Juan Carlos University, Spain
Structural and parametric strategies for mastering spectral centrality measures of complex networks
Show abstract   🡣
Hide abstract   🡡

Controlling the centrality measures of a complex networks is related to the ability of modifying the relevance of nodes in complex systems, including from social networks to communication systems. In this talk several structural and parametric techniques will be presented including computational and sharp analytical results about their effects in the value of spectral centralities such as eigenvector and PageRank centralities in complex and multilayer networks.

16.00 - 16.20
MSK, UTC +3
Invited talk
Ekaterina Serebryannikova MIPT, Russia
Multilayer representation of collaboration networks with higher-order interactions
Show abstract   🡣
Hide abstract   🡡

Collaboration patterns offer important insights into how scientific breakthroughs and innovations emerge in small and large research groups. However, links in traditional networks account only for pairwise interactions, thus making the framework best suited for the description of two-person collaborations, but not for collaborations in larger groups. We therefore study higher- order scientific collaboration networks where a single link can connect more than two individuals, which is a natural description of collaborations entailing three or more people. We also consider different layers of these networks depending on the total number of collaborators, from one upwards. By doing so, we obtain novel microscopic insights into the representativeness of researchers within different teams and their links with others. In particular, we can follow the maturation process of the main topological features of collaboration networks, as we consider the sequence of graphs obtained by progressively merging collaborations from smaller to bigger sizes starting from the single-author ones. We also perform the same analysis by using publications instead of researchers as network nodes, obtaining qualitatively the same insights and thus confirming their robustness. We use data from the arXiv to obtain results specific to the fields of physics, mathematics, and computer science, as well as to the entire coverage of research fields in the database.

16.20 - 16.40
MSK, UTC +3
Invited talk
Karin Alfaro-Bittner Federico Santa María Technical University, Chile
Growing scale-free simplices
Show abstract   🡣
Hide abstract   🡡

Pairwise interactions have had a principal role in the understanding of real-world networks and in the establishment of generative models that recover their observed macroscopic patterns. However, pairwise interactions provide limited insight into higher-order structures. Simplicial complexes can represent these high-order interactions.

In this talk, I will discuss a model to grow simplicial complexes of order two, i.e., nodes, links, and triangles, using preferential and/or non-preferential attachment mechanisms. The proposed model always yields a power-law scaling in P(k), recovering the observed scale-free property and allows full control over the generalized degree distribution.

16.40 - 17.00
MSK, UTC +3
Invited talk
Kirill Kovalenko MIPT, Russia
D-dimensional oscillators in simplicial structures
Show abstract   🡣
Hide abstract   🡡

All collective properties emerging in complex systems arise from the specific way in which the elementary components interact. In past years, many relevant cases in physics, biology, social sciences and engineering have been successfully modelled as networks of coupled dynamical systems. Such a representation, however, implies a too strong limitation, in that it explicitly assumes that the interplay among the system’s units can always be factorized into the sum of pairwise interactions. Various recent studies have instead revealed that higherorder (many-body) interactions have to be accounted for a suitable representation of the structure and function of complex systems.

I will discuss the recent result on the D-dimensional Kuramoto model with 2-simplex interactions and compare this model with the D-dimensinal Kuramoto model with only pair-wise interactions.

17.00 - 17.50
MSK, UTC +3
Plenary talk
Stefano Boccaletti Institute for Complex Systems, Italy
Synchronization in complex networks, hypergraphs and simplicial complexes
Show abstract   🡣
Hide abstract   🡡

All interesting and fascinating collective properties of a complex system arise from the intricate way in which its components interact. Various systems in physics, biology, social sciences and engineering have been successfully modelled as networks of coupled dynamical systems, where the graph links stand for pairwise interactions. This is, however, too strong a limitation, as recent studies have revealed that higher-order many-body interactions are present in social groups, ecosystems and in the human brain, and they actually affect the emergent dynamics of all these systems.

I will discuss a general framework that allows to study coupled dynamical systems accounting for the precise microscopic structure of their interactions at any possible order. Namely, I will consider an ensemble of identical dynamical systems, organized on the nodes of a simplicial complex, and interacting through synchronization-non-invasive coupling function. The simplicial complex can be of any dimension, meaning that it can account, at the same time, for pairwise interactions (networks), three-body interactions and so on. In such a broad context, complete synchronization, a circumstance where all the dynamical units arrange their evolution in unison, exists as an invariant solution, and I will describe the necessary condition for it to be observed as a stable state in terms ofa Master Stability Function.

This generalizes the existing results valid for pairwise interactions (i.e. graphs) to the case of complex systems with the most general possible architecture.

17.50 - 18.00
MSK, UTC +3
Concluding remarks by the Workshop's chairmen
Mini-symposia
Roman Karasev
IITP, Russia
Geometric Topology and Hypergraphs
11.00 - 11.40
MSK, UTC +3
Invited talk
Makoto Ozawa Komazawa University, Japan
Multibranched surfaces in 3-manifolds
Show abstract   🡣
Hide abstract   🡡

This talk is a survey including recent joint works with Kazufumi Eto, Shosaku Matsuzaki, ‪Mario Eudave-Muñoz, Kai Ishihara, Yuya Koda and Koya Shimokawa.

As a generalization of a graph, we define a multibranched surface as follows. Let $B$ be a closed 1-dimensional manifold, $S$ be a compact 2-dimensional manifold with non-empty boundary and $\phi: \partial S\to B$ be a covering map. Then the quotient space $X=B\cup_{\phi} S$ is called a multibranched surface.

Similarly to the genus of a graph, we define the genus of a regular multibranched surface $X$ as the minimum Heegaard genus of closed orientable 3-manifolds into which $X$ can be embedded. We give several upper bounds and lower bounds for the genus of a regular multibranched surface.

Similarly to the graph minor, we also introduce a minor on multibranched surfaces, and consider the obstruction set $\Omega(\mathcal{P}_{S^3})$ for the set of multibranched surfaces embedded in the 3-sphere. We summarize all known results on the obstruction set $\Omega(\mathcal{P}_{S^3})$ at the present moment.

1. K. Eto, S. Matsuzaki, M. Ozawa, An obstruction to embedding 2-dimensional complexes into the 3-sphere. Topol. Appl. 198 (2016), 117-125.
2. M. Eudave-Muñoz, M. Ozawa, Characterization of 3-punctured spheres in non-hyperbolic link exteriors. Topol. Appl. 264 (2019), 300-312.
3. M. Eudave-Muñoz, M. Ozawa, The maximum and minimum genus of a multibranched surface. Topol. Appl. (2020), 107502.
4. K. Ishihara, Y. Koda, M. Ozawa, K. Shimokawa, Neighborhood equivalence for multibranched surfaces in 3-manifolds. Topol. Appl. 257 (2019), 11-21.
5. S. Matsuzaki, M. Ozawa, Genera and minors of multibranched surfaces. Topol. Appl. 230 (2017), 621–638.
6. M. Ozawa, A partial order on multibranched surfaces in 3-manifolds. Topol. Appl. 272 (2020), 107074.
11.45 - 12.25
MSK, UTC +3
Invited talk
Arkadiy Skopenkov MIPT and Independent University of Moscow, Russia
Hypergraph drawings without multiple self-intersections
Show abstract   🡣
Hide abstract   🡡

Algorithms for recognizing graph planarity are well-known. The classical topics in mathematics and computer science is recognizing realizability of hypergraphs in $d$-dimensional Euclidean space $\mathbb R^d$. In these studies, as well as in studies of Radon–Tverberg-type problems from topological combinatorics, the following notion appeared, see e.g. survey [5]. Denote by $\Delta_n$ a simplex with $n$ vertices. The body (or geometric realization) $|K|$ of a hypergraph $K=(V,E)$ is the union of faces of $\Delta_{|V|}$ corresponding to elements of $E$. An almost $r$-embedding of a hypergraph $K$ is a piecewise-linear (PL) map $f\colon |K|\to \mathbb R^d$ such that the images of any $r$ pairwise disjoint faces of $|K|$ do not have a common point. A $k$-dimensional hypergraph is a hypergraph whose maximal hyperedge has $k$ elements. By general position, for $(r-1)d>rk$ every $k$-dimensional hypergraph almost $r$-embeds in $\mathbb R^d$. For fixed $r$ and $d$, a polynomial algorithm for recognition almost $r$-embeddability of $k$-hypergraphs in $\mathbb R^d$ was constructed

• in [2, 1] for $(r-1)d=rk$;
• in [4] for $rd\ge(r+1)k+3$, see also [3].
1. S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, Eliminating Higher-Multiplicity Intersections, III. Codimension 2. Israel J. Math., to appear, arXiv:1511.03501.
2. I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems. arXiv:1508.02349.
3. I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the $r$-Metastable Range. arXiv:1601.00876.
4. A. Skopenkov, Eliminating higher-multiplicity intersections in the metastable dimension range. arXiv:1704.00143.
5. A. Skopenkov, Invariants of graph drawings in the plane. abridged version: Arnold Math. J. 2020, full version: arXiv:1805.10237.
12.30 - 13.10
MSK, UTC +3
Invited talk
Roman Karasev IITP, Russia
Envy-free division using mapping degree
Show abstract   🡣
Hide abstract   🡡

We discuss some classical problems of mathematical economics, in particular, the so-called envy-free division problems. The classical approach to some of such problem reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster–Kuratowski–Mazurkiewicz theorem and the Gale theorem) is a boundary condition on the map.

We try to replace the boundary condition by a certain equivariance condition under all permutations, or a weaker condition of "pseudoequivariance", which has a certain real-life meaning for the problem of partitioning a segment and distributing the parts among the players. It turns out that we can guarantee the existence of a solution for a certain type of the segment partition problem. The solution can be guaranteed if and only if the number of players is a prime power. The case of three players was solved previously be Segal–Halevi, the prime case and the case of four players were solved by Meunier and Zerbib.

Going back to the true equivariance setting, we provide, in the case when the number of players is not a prime power and not a double prime power, the counterexamples showing that the topological configuration space / text map scheme for a wide class of equipartition problems fails (this result was completed in the follow-up paper [4] by Sergey Avvakumov and Sergey Kudrya). The existence of equivariant maps is applicable, for example, to building stronger counterexamples for the topological Tverberg conjecture (in another joint work [3] with Sergey Avvakumov and Arkadiy Skopenkov).

Though, under additional assumptions that every piece is estimated independently of the other pieces and the every player's estimate is the same we cannot drop the prime power assumption and have equipartitions, as in [1, 5].

1. Arseniy Akopyan, Sergey Avvakumov, and Roman Karasev, Convex fair partitions into an arbitrary number of pieces. arXiv:1804.03057.
2. Sergey Avvakumov and Roman Karasev, Envy-free division using mapping degree. arXiv:1907.11183.
3. Sergey Avvakumov, Roman Karasev, Arkadiy Skopenkov, Stronger counterexamples to the topological Tverberg conjecture. arXiv:1908.08731.
4. Sergey Avvakumov and Sergey Kudrya, Vanishing of all equivariant obstructions and the mapping degree. arXiv:1910.12628.
5. Sergey Avvakumov and Roman Karasev, Equipartition of a segment. arXiv:2009.09862.
13.15 - 13.45
MSK, UTC +3
Invited talk
Egor Kolpakov Moscow State University, Russia
A “converse” to the Constraint Lemma
Show abstract   🡣
Hide abstract   🡡

A particular case of the main result is a direct proof of the implication $(LVKF_{1,3})\Rightarrow( LTT_{2,3})$:

• ($LVKF_{1,3}$) From any 11 points in $\mathbb{R}^{3}$ one can choose 3 pairwise disjoint triples whose convex hulls have a common point.
• ($LTT_{2,3}$) Any 7 points in $\mathbb{R}^{2}$ can be decomposed into 3 subsets whose convex hulls have a common point.

These statements are true, but the purpose of this paper is the direct derivation of one statement from another.

1. E. Kolpakov, A 'converse' to the Constraint Lemma. arXiv:1903.08910.
13.45 - 14.20
MSK, UTC +3
Break
14.20 - 15.00
MSK, UTC +3
Invited talk
Gaiane Panina St. Petersburg Department of V.A. Steklov Mathematical Institute RAS
Envy-free division via configuration spaces
Show abstract   🡣
Hide abstract   🡡

Joint work with Rade T. Živaljević

The classical approach to envy-free division problems arising in mathematical economics typically relies on the Knaster–Kuratowski–Mazurkiewicz theorem, Sperner's lemma or some extension involving mapping degree. We propose a different approach which uses equivariant topology, originally developed for applications in discrete and computational geometry (Tverberg type problems, necklace splitting problem in the sense of N. Alon and D. West, etc.).

We prove several relatives of the classical envy-free division theorem, where the emphasis is on preferences allowing the players to choose degenerate pieces of the cake.

Assume that a group of $r$ players want to divide among themselves a "cake", that is, the interval $I=[0, 1]$, which should be cut into $r$ tiles. Therefore a cut of the cake in this model is a sequence of numbers $$0 \leqslant x_1 \leqslant x_2 \leqslant \dots \leqslant x_{r-1} \leqslant 1 \, .$$ After a cut is fixed, each of the players expresses his own individual preferences over the tiles, by pointing to one (or more) intervals which they like more than the rest.

A classical theorem, found independently by Stromquist and by Woodall in 1980 states that, under two conditions: (1) the closeness condition, and (2) "no player prefers a tile which degenerates to a single point", it is possible to divide the cake into $r$ connected tiles and distribute these shares to $r$ players in an envy-free manner: each player prefers a preferred share.

In our research we relax the condition (2) and instead make a very mild assumption $\mathbf{(P_{dte})}$: All degenerate tiles are equal. That is, for a fixed cut, each player either prefers all the degenerate tiles, or prefers none of the degenerate tiles.

What is known:

1. If $r$ is a prime power then an envy-free division always exists if the preferences satisfy some additional partition equivalence condition (Avvakumov and Karasev; see also Meunier and Zerbib in the cases when $r$ is a prime or $r=4$).
2. If $r$ is not a prime power, (a) is no longer true (Avvakumov and Karasev).
3. If it is allowed to drop some of the tiles, an envy-free division always exists under the condition $\mathbf{P_{dte}}$ (Avvakumov, Karasev, Meunier and Zerbib).

What is new:

1. We modify the rules of the game. In the presence of degenerate tiles only one of the guests may be given two tiles (instead of one) in which case one of them must be the rightmost tile. Then, if either $r$ is a prime number or $r=4$, under the condition $\mathbf{P_{dte}}$, an envy-free division always exists.
2. If $r$ is neither a prime nor equal to $4$, the statement A is not true.
3. Let $r$ be a prime number or $r=4$. Suppose that we are allowed to drop at most one of the non-degenerate tiles. With an additional small assumption concerning the tile number $r$, an envy-free division always exist under the condition $\mathbf{P_{dte}}$.
4. Statement A yields an alternative proof of the result a of Avvakumov and Karasev.
5. Assume that the tiles may be distributed among the players without any restrictions, in particular a player may receive several tiles at a time. Then under the condition $\mathbf{P_{dte}}$, an envy-free division always exists if $r$ is a prime power.
15.05 - 15.45
MSK, UTC +3
Invited talk
Rade Živaljević Mathematical Institute SASA, Serbia
Optimal colored Tverberg theorems for prime powers
Show abstract   🡣
Hide abstract   🡡

Joint work with Duško Jojić and Gaiane Panina

The colored Tverberg theorem of Blagojević, Matschke, and Ziegler provides optimal bounds for the colored Tverberg problem, under the condition that the number of intersecting rainbow simplices is a prime number.

One of our principal new ideas is to replace the ambient simplex $\Delta^N$, used in the original Tverberg theorem, by an "abridged simplex" of smaller dimension, and to compensate for this reduction by allowing vertices to repeatedly appear a controlled number of times in different rainbow simplices.

Following this strategy we obtain an extension of the result of Blagojević, Matschke, and Ziegler to an optimal colored Tverberg theorem for multisets of colored points, which is valid for each prime power $r=p^k$, and reduces to their result for $k=1$.

Configuration spaces, used in the proof, are combinatorial pseudomanifolds which can be represented as multiple chessboard complexes. Our main topological tool is the Eilenberg–Krasnoselskii theory of degrees of equivariant maps for non-free actions.

15.50 - 16.30
MSK, UTC +3
Invited talk
Marek Filakovský Masaryk University, Czech Republic
Computing homotopy classes of equivariant maps and polynomial-time decidability of the $r$-Tverberg problem
Show abstract   🡣
Hide abstract   🡡

Joint work with L. Vokřínek

The study of algorithmic solutions to classical problems in homotopy theory such as the computation of set $[X,Y]$ of homotopy classes of maps or the lifting-extension problem can be traced back to the 50's. In recent years, the area saw a rapid development and new results were applied to problems of computational topology, such as the embeddability problem i.e. the question whether a $k$-dimensional simplicial complex $K$ is embeddable in $\mathbb{R}^d$, see [1, 2].

We present a polynomial-time algorithm that, given topological spaces $X,Y$ (modeled by finite simplicial complexes) with an action of a finite group $G$, computes the set $[X,Y]_G$ of homotopy classes of equivariant maps under the so-called stable condition $\dim X^H \leq 2~\mathrm{conn}(Y^H) > 1$, for all subgroups $H\leq G$. In fact the result follows from a more general study of homotopy classes of maps between diagrams of spaces.

Consider now the $r$-Tverberg problem: Given a $k$-dimensional simplicial complex $K$, decide whether there is a (piecewise-linear) map (called $r$-Tverberg map) $K \to \mathbb{R}^{d}$ without $r$-tuple intersection points on $r$ pairwise disjoint faces. Notice that if $r = 2$, we obtain the embeddability problem.

For $r>2$, Mabillard and Wagner [3, 4] established a version of the Haefliger–Weber theorem: In the metastable range $rd \geq (r+1)k +3$, the $r$-Tverberg problem is equivalent to deciding an existence of an equivariant map between spaces with non-free actions of the symmetric group $\mathsf{S}_r$. Thus to solve the problem it is enough to determine whether certain set of the form $[X,Y]_{\mathsf{S}_r}$ is nonempty. Applying our result here, we conclude that in the metastable range of dimensions, the $r$-Tverberg problem is decidable in polynomial time.

1. Martin Čadek, ‪Marek Krčál, Lukáš Vokřínek, Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom., 57(4):915--965, 2017.
2. Marek Filakovský, Uli Wagner, and Stephan Zhechev, Embeddability of simplicial complexes is undecidable. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767--785. Society for Industrial and Applied Mathematics, January 2020.
3. I. Mabillard and U. Wagner, Eliminating Tverberg points, I. An analogue of the Whitney trick. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 171:171--171:180, New York, NY, USA, 2014. ACM.
4. Isaac Mabillard and Uli Wagner, Eliminating higher-multiplicity intersections, II. The deleted product criterion in the $r$-metastable range. In Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), pages 51:1--51:12, 2016.
16.35 - 17.15
MSK, UTC +3
Invited talk
Pavel Paták Charles University, Czech Republic
Almost-embeddings of k-complexes into 2k-manifolds
Show abstract   🡣
Hide abstract   🡡

Joint work with M. Tancer

Proving many combinatorial and geometrical results such as Radon's or Helly's theorem requires a stronger notion of non-embeddability. Namely, we require that for any continuous map $f\colon K\to X$ of the given simplicial complex $K$ into the target topological space $X$ there are two disjoint simplices in $K$, whose images in $X$ intersect. Fortunately the classical approach via equivariant topology establishes even stronger $\mathbb Z_2$-version of non-embeddability.

In this talk we focus on non-embedabbility of $k$-complexes $K$ into $2k$-manifolds $M$. There are many cases where all the notions of non-embeddability coincide, e.g. if $M$ is a projective plane or torus, or if $K$ is a complete $k$-skeleton of a simplex and $M=\mathbb R^{2k}$.

However, if $M$ is a surface of sufficiently high genus, the situation is different. Fulek and Kynčl have found a graph that can be $\mathbb Z_2$-almost embedded into a surface of genus $4$, but cannot be embedded there. Hence, if we want to establish tight non-almost-embeddability results for surfaces, we need to study more general $\mathbb Z$-almost embeddability.

We describe a general obstruction for non-embeddability of $k$-complexes into $2k$-manifolds over $\mathbb Z$. The obstruction leads to an explicit system of quadratic diophantine equations. In many cases it can be shown that these equations cannot be satisfied, and hence there is no $\mathbb Z$-embedding. We note that there have been some prior work on embeddings of $k$-complexes into manifolds, however we are the first ones who describe such an obstruction explicitly. As an example, let us mention that in 1969 Harris published an obstruction for embeddings of simplicial complexes into manifolds. However, constructing Harris's obstruction requires several steps that are provably undecidable. Our work produces a system of quadratic diophantine equations of a very special form. The decidability of such systems is yet to be determined.

17.20 - 18.00
MSK, UTC +3
Invited talk
Salman Parsa Saint Louis University, USA
Embeddability of join of two simplicial complexes into double dimension
Show abstract   🡣
Hide abstract   🡡

We say a $d$-dimensional simplicial complex embeds into double dimension if it embeds into the Euclidean space of dimension $2d$. For instance, a graph is planar if and only if it embeds into the double dimension. If two simplicial complexes K and L are not embeddable into double dimension, what can we say about their join complex K*L? In this talk, I consider this problem and sketch a proof of the fact that, quite unexpectedly, there are complexes K and L which are not embeddable into double dimension but their join is embeddable into double dimension. More generally, I discuss conditions under which the join is non-embeddable into double dimension.

The classical obstruction for embedding a simplicial complex $K$ into double dimension is called the van Kampen obstruction. This is a cohomology class in the quotient of the deleted product of $K$. This class can also be defined as an Smith classes. Simth classes are our main tool and I discuss these classes. Moreover, it is possible to use the deleted join instead of the deleted product to define the obstruction to embeddability. It follows that the problem of embeddability of the join complex $K*L$ relates to the behavior of the Smith index of a $\mathbb{Z}_2$-complex under join. We determine this behavior to some extent for Smith classes of $\mathbb{Z}_p$-complexes, for $p$ prime.

In order to show that a cohomology class is non-zero, we use chains, which we call certificates, with special properties. This method allows us to prove that some "product" of cohomology classes is non-zero by constructing certificates for the product class based on certificates for the factors. Details can be found in [1].

1. S. Parsa, Instability of the Smith Index Under Joins and Applications to Embeddability. Arxiv preprint: arXiv:2103.02563, 2021.
Mini-symposia
Aleksandr Gasnikov
MIPT, Russia
Modern Convex Optimization and Applications
10.00 - 10.30
MSK, UTC +3
Invited talk
Pavel Dvurechensky WIAS, Germany and MIPT, HSE, Russia
Wasserstein barycenters from the computational perspective
Show abstract   🡣
Hide abstract   🡡

In this talk we give an overview of several works devoted to numerical methods for the Wasserstein barycenter problem. Wasserstein barycenter allows to generalize the notion of average object to the space of probability measures and has a number of applications in machine learning and data analysis. We discuss the complexity of this problem in the discrete-discrete setting as well as efficient algorithms, in particular distributed optimization methods that allow one to scale up the computations.

10.35 - 11.05
MSK, UTC +3
Invited talk
Darina Dvinskikh WIAS, Germany and MIPT, Russia
Decentralized Algorithms for Wasserstein Barycenters
Show abstract   🡣
Hide abstract   🡡

We consider the Wasserstein barycenter problem from the computantional and statistical sides in two scenarios: (i) the measures are given and we need to compute their Wasserstein barycenter, and (ii) the measures are generated from a probability distribution and we need to calculate the population barycenter of the distribution defined by the notion of Fréchet mean. The statistical issues are estimating the sample size and the question of regularization. The computantional issues are developing decentralized algorithms to calculate the barycenters.

11.10 - 11.30
MSK, UTC +3
Invited talk
Eduard Gorbunov MIPT, HSE, Russia
MARINA: Faster Non-Convex Distributed Learning with Compression
Show abstract   🡣
Hide abstract   🡡

We develop and analyze MARINA: a new communication efficient method for non-convex distributed learning over heterogeneous datasets. MARINA employs a novel communication compression strategy based on the compression of gradient differences which is reminiscent of but different from the strategy employed in the DIANA method of Mishchenko et al (2019). Unlike virtually all competing distributed first-order methods, including DIANA, ours is based on a carefully designed biased gradient estimator, which is the key to its superior theoretical and practical performance. To the best of our knowledge, the communication complexity bounds we prove for MARINA are strictly superior to those of all previous first order methods. Further, we develop and analyze two variants of MARINA: VR-MARINA and PP-MARINA. The first method is designed for the case when the local loss functions owned by clients are either of a finite sum or of an expectation form, and the second method allows for partial participation of clients -- a feature important in federated learning. All our methods are superior to previous state-of-the-art methods in terms of the oracle/communication complexity. Finally, we provide convergence analysis of all methods for problems satisfying the Polyak-Lojasiewicz condition.

11.35 - 11.55
MSK, UTC +3
Invited talk
Dmitry Kamzolov MIPT, Russia
Hyperfast Second-Order Local Solvers for Efficient Statistically Preconditioned Distributed Optimization
Show abstract   🡣
Hide abstract   🡡

Statistical preconditioning can be used to design fast methods for distributed large-scale empirical risk minimization problems, for strongly convex and smooth loss functions, allowing fewer communication rounds. Multiple worker nodes compute gradients in parallel, which are then used by the central node to update the parameter by solving an auxiliary (preconditioned) smaller-scale optimization problem. However, previous works require an exact solution of an auxiliary optimization problem by the central node at every iteration, which may be impractical. This paper proposes a method that allows the inexact solution of the auxiliary problem, reducing the total computation time. Moreover, for loss functions with high-order smoothness, we exploit the structure of the auxiliary problem and propose a hyperfast second-order method with complexity $\tilde{O}(\kappa^{1/5})$, where $\kappa$ is the local condition number. Combining these two building blocks (inexactness and hyperfast methods), we show complexity estimates for the proposed algorithm, which is provably better than classical variance reduction methods and has the same convergence rate as statistical preconditioning with exact solutions. Finally, we illustrate the proposed method's practical efficiency by performing large-scale numerical experiments on logistic regression models.

12.00 - 12.30
MSK, UTC +3
Invited talk
Artem Agafonov MIPT, Russia
Inexact Tensor Methods and Their Application to Stochastic Convex Optimization
Show abstract   🡣
Hide abstract   🡡

We propose general non-accelerated and accelerated tensor methods under inexact information on higher-order derivatives, analyze its convergence rate, and provide sufficient conditions for this method to have similar complexity as the exact tensor method. As a corollary, we propose the firststochastic tensor method for convex optimization and obtain sufficient mini-batch sizes for eachderivative.

12.30 - 13.00
MSK, UTC +3
Break
13.00 - 13.30
MSK, UTC +3
Invited talk
Aleksandr Beznosikov MIPT, HSE, Russia
Show abstract   🡣
Hide abstract   🡡

GAN is one of the most popular and commonly used neural network models. When the model is large and there is a lot of data, the learning process can be delayed. The standard way out is to use multiple devices. Therefore, the methods of distributed and federated training for GANs are an important question. But from an optimization point of view, GANs are saddle-point problems: $\min_x \max_y f(x,y)$. Therefore, this paper focuses on the distributed optimization of smooth stochastic saddle-point problems. The first part of the paper is devoted to lower bounds for the distributed methods for saddle-point problems as well as the optimal algorithms by which these bounds are achieved. Next, we present a new algorithm for distributed saddle-point problems -- Extra Step Local SGD. In the experimental part of the paper, we use the Local SGD technique in practice. In particular, we train GANs in a distributed manner.

13.35 - 14.05
MSK, UTC +3
Invited talk
Alexander Rogozin MIPT, HSE, Russia
Decentralized optimization for saddle point problems with local and global variables
Show abstract   🡣
Hide abstract   🡡

We consider distributed convex-concave saddle point problems over arbitrary connected undirected networks and propose a decentralized distributed algorithm for their solution. The local functions distributed across the nodes are assumed to have global and local groups of variables. For the proposed algorithm we prove non-asymptotic convergence rate estimates with explicit dependence on the network characteristics. To supplement the convergence rate analysis, we propose lower bounds for strongly-convex-strongly-concave and convex-concave saddle-point problems over arbitrary connected undirected networks. We illustrate the considered problem setting by a particular application to distributed calculation of non-regularized Wasserstein barycenters.

14.10 - 14.30
MSK, UTC +3
Invited talk
Vaidya's cutting plane method for stochastic optimization in small dimension
Show abstract   🡣
Hide abstract   🡡

The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a number of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are often used to solve such problems. We propose to use Vaidya's cutting plane method with minibatching, which converges linearly and hence requires significantly less iterations than SGD. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of target function to achieve linear convergence. We prove that the method arrives at approximate solution with given probability when using minibatches of size proportional to the desired precision to the power -2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, Vaidya's cutting plane method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quasi linear in dimension of the problem, hence the method is suitable for relatively small dimensionalities.

14.35 - 14.55
MSK, UTC +3
Invited talk
Alexander Titov MIPT, Russia
Some Modifications of Mirror Prox Algorithm for Strongly Monotone Variational Inequalities and Related Results
Show abstract   🡣
Hide abstract   🡡

The report is devoted to the development of numerical methods for solving variational inequalities with some simplified requirements for the smoothness conditions of functionals. We consider the Mirror Prox algorithm for solving both variational inequalities and saddle point problems. We compare its effectiveness with the recently proposed accelerated method. Further we focus on strongly monotone operators and corresponding variational inequalities. We propose the modification of the Mirror Prox algorithm in the case of relatively strongly monotone operator and compare its effectiveness with the restarted version of the classical Mirror Prox algorithm.

15.00 - 15.30
MSK, UTC +3
Invited talk
Seydamet Ablaev CFU, Russia
Adaptive Methods for Convex Optimization Problems with Relative Accuracy
Show abstract   🡣
Hide abstract   🡡

This talk is devoted to some first-order methods for convex optimization problems with relative accuracy with respect to the objective functional. We develop the previously known works of Yu. E. Nesterov on this topic. According to this approach, it is reasonable to reduce convex minimization problems with relative accuracy to problems with positively homogeneous functions. Such functions are non-smooth generally. Therefore, we consider 2 approaches known for non-smooth optimization problems. The first approach is devoted to modifications of gradient-typr methods with inexact oracle, bit for problems with relative accuracy. The second approach is related to subgradient methods with B. T. Polyak stepsize. Result on the linear convergence rate for some methods of this type with adaptive step adjustment is obtained for some class of non-smooth problems. Some generalization to a special class of non-convex non-smooth problems is also considered.

14.00
MSK,
UTC +3
Plenary Talk
Brendan McKay
Australian National University
Degree sequences of random uniform hypergraphs
Show abstract   🡣
Hide abstract   🡡

Joint work with Catherine Greenhill, Mikhail Isaev and Tamás Makai

Let $\mathbf{d}=(d_1,\ldots,d_n)$ be a sequence of integers, and let $P_r(\mathbf{d})$ be the probability that a uniformly random $r$-uniform hypergraph has degree sequence $\mathbf{d}$. Our aim is to estimate this probability. The best results so far were obtained by Kamčev, Liebenau and Wormald (arXiv, 2020), who covered degree sequences from very sparse to moderately dense. In the moderately dense range, which overlaps with ours, they require $r=o(n^{1/4})$, a density $O(1/r)$ of the complete hypergraph, and a maximum variation of the degrees that is small but large enough to cover the typical degrees of random hypergraphs. In our work we extend their result into the arbitrarily dense domain. We also remove the restriction on $r$ completely, and allow a much greater variation of degrees. One of the corollaries is a proof (for our range of densities) of a conjecture of Kamčev et al that the degrees of random hypergraphs almost everywhere match a vector of independent hypergeometric variables conditioned on given sum.

16.00
MSK,
UTC +3
Plenary Talk
Ola Svensson
Ecole Polytechnique Fédérale de Lausanne, Switzerland
Learning-Augmented Online Algorithms and the Primal-Dual Method
Show abstract   🡣
Hide abstract   🡡

The design of learning-augmented online algorithms is a new and active research area. The goal is to understand how to best incorporate predictions of the future provided e.g. by machine learning algorithms that rarely come with guarantees on their accuracy.

In the absence of guarantees, the difficulty in the design of such learning-augmented algorithms is to find a good balance: on the one hand, following blindly the prediction might lead to a very bad solution if the prediction is misleading. On the other hand, if the algorithm does not trust the prediction at all, it will simply never benefit from an excellent prediction. An explosion of recent results solve this issue by designing smart algorithms that exploit the problem structure to achieve a good trade-off between these two cases.

In this talk, we will discuss this emerging line of work. In particular, we will show how to unify and generalize some of these results by extending the powerful primal-dual method for online algorithms to the learning augmented setting.

18.00
MSK,
UTC +3
Plenary Talk
József Balogh
University of Illinois, USA
On Robustness of The Erdös–Ko–Rado Theorem
Show abstract   🡣
Hide abstract   🡡

It is joint work with Lina Li, Ramon Garcia, Adam Wagner; and with Robert Krueger and Haoran Luo.

A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics, starting with the well-known Erdös–Ko–Rado Theorem. We consider two extensions of it:

Counting variant: Frankl–Kupavskii and Balogh–Das–Liu–Sharifzadeh–Tran showed that for $n\geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $n\geq 2k+ 100\ln k$.

Random variant: For positive integers $n$ and $k$ with $n\geq 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollob\'as, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. Building on work of Das and Tran and of Devlin and Kahn, we resolve this question.

Our proofs uses, among others, the graph container method and the Das–Tran removal lemma.

Mini-symposia
Thang Pham
University of Rochester, USA
9.55 - 10.25
MSK, UTC +3
Invited talk
Ben Lund Institute for Basic Science, Korea
Finite field Kakeya and Furstenberg sets
Show abstract   🡣
Hide abstract   🡡

An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008 [3]. Dvir’s proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area.

I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao [5]. A $(k,m)$-Furstenberg set $S \subset \mathbb{F}_q^n$ has the property that, parallel to every $k$-dimensional subspace $V$, there is a $k$-plane $W$ such that $|W \cap S| > m$. Using sophisticated ideas from algebraic geometry, Ellenberg and Erman [4, 1] showed that if $S$ is a $(k,m)$-Furstenberg set, then $|S| > c m^{n/k}$, where $c$ depends on $n$ and $k$. In recent joint work with Manik Dhar and Zeev Dvir [2], we give simpler proofs of stronger bounds. For example, if $m > 2^{n + 7 - k} q$, then $|S| = (1 - o(1)) m q^{n-k}$, which is tight up to the $o(1)$ term.

1. Manik Dhar, Zeev Dvir, and Ben Lund. Furstenberg sets in finite fields: Explaining and improving the Ellenberg-Erman proof. Preprint arXiv:1909.02431.
2. Manik Dhar, Zeev Dvir, and Ben Lund. Simple proofs for Furstenberg sets over finite fields.. Preprint arXiv:1909.03180.
3. Zeev Dvir. On the size of Kakeya sets in finite fields.. Journal of the American Mathematical Society, 22(4):1093--1097, 2009.
4. Jordan Ellenberg and Daniel Erman. Furstenberg sets and Furstenberg schemes over finite fields.. Algebra & Number Theory, 10(7):1415--1436, 2016.
5. Jordan S. Ellenberg, Richard Oberlin, and Terence Tao. The Kakeya set and maximal conjectures for algebraic varieties over finite fields.. Mathematika, 56(1):1–25, 2010.
10.30 - 11.00
MSK, UTC +3
Invited talk
Ali Mohammadi Institute for Research in Fundamental Sciences, Iran
Almost orthogonal subsets of vector spaces over finite fields
Show abstract   🡣
Hide abstract   🡡

A set of non-zero vectors is said to be almost orthogonal if among any three of its elements, at least two are mutually orthogonal. Rosenfeld proved that the largest almost orthogonal subsets of $\mathbb{R}^n$ are of size $2n$, giving a positive answer to a question of Erdös. Various finite field variants of this result were later conjectured by Ahmadi and Mohammadian. In this talk, I will discuss a recent joint work with Giorgis Petridis, in which we have resolved these conjectures, obtaining sharp analogues of Rosenfeld's theorem.

11.05 - 11.35
MSK, UTC +3
Invited talk
Doowon Koh Chungbuk National University, Korea
Mattila-Sjölin type functions: A finite field model
Show abstract   🡣
Hide abstract   🡡

This is a joint work with Daewoong Cheong, Thang Pham, and Chun-Yen Shen.

Let $\mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting, we say that a function $\phi\colon \mathbb{F}_q^d\times \mathbb{F}_q^d\to \mathbb{F}_q$ is a Mattila-Sj\"{o}lin type function in $\mathbb{F}_q^d$ if for any $E\subset \mathbb{F}_q^d$ with $|E|\gg q^{\frac{d}{2}}$, we have $\phi(E, E)=\mathbb{F}_q$. The main purpose of this talk is to present the existence of such a function. More precisely, we will construct a concrete function $\phi: \mathbb{F}_q^4\times \mathbb{F}_q^4\to \mathbb{F}_q$ with $q\equiv 3 \mod{4}$ such that if $E\subset \mathbb F_q^4$ with $|E|>q^2,$ then $\phi(E,E)=\mathbb F_q.$

11.40 - 12.10
MSK, UTC +3
Invited talk
Le Anh Vinh Vietnam National University
Expanding polynomials over arbitrary finite fields
Show abstract   🡣
Hide abstract   🡡

Let $\mathbb{F}$ be a field and $E$ be a finite subset of $\mathbb{F}^d$, the $d$-dimensional vector space over the field $\mathbb{F}$. Given a function $f : \mathbb{F} \rightarrow \mathbb{F}$, definite $$f(E) = f(x) : x \in E$$ the image of $f$ under the subset $E$. We say that $f$ is a $d$-variable expander with expansion index if $|f(E)| \geq C_\epsilon|E|^{1/d+\epsilon}$ for every subset E, possibly under some general density or structural assumptions on E.

In this talk, we present a number of results on whether certain polynomials have the expander properties. These results are based on point-plane incidence bounds over finite vector spaces and spectral graph theory techniques.

12.15 - 12.45
MSK, UTC +3
Invited talk
Thang Pham ETH Zurich, and Vietnam National University
Erdös-Falconer distance conjecture over finite fields
Show abstract   🡣
Hide abstract   🡡

The Erdös-Falconer distance problem asks for the smallest number $\alpha$ such that if $E\subset \mathbb{F}_q^d$ and $|E|\ge C q^{\alpha}$ then the distance set $\Delta(E)$ contains the whole field $\mathbb{F}_q$ or covers a positive proportion of all distances. Iosevich and Rudnev (2004) proved that if $|E|\ge 4q^{\frac{d+1}{2}}$ then $\Delta(E)=\mathbb{F}_q$. It has been proved that the exponent $\frac{d+1}{2}$ can not be improved in odd dimensions, even we only wish to cover a positive proportion of all distances. In even dimensions, it has been conjectured that in order to cover a positive proportion of all distances, the right exponent should be $d/2$. In this talk, we are going to discuss about recent progress on this conjecture.

12.45 - 14.00
MSK, UTC +3
Break
14.00 - 14.50
MSK, UTC +3
Plenary Talk
Ilya Shkredov Steklov Institute of Mathematics and MIPT, Russia
On noncommutative methods in Additive Combinatorics and Number Theory
Show abstract   🡣
Hide abstract   🡡

We give a survey on recent applications of growth in non—abelian groups to a series of problems of Number Theory and Additive Combinatorics. We discuss Zaremba’s problem from the theory of continued fractions, the sum—product phenomenon, Incidence Geometry, affine sieve and other questions.

15.00 - 15.30
MSK, UTC +3
Invited talk
Steven Senger University of Missouri, USA
Bounds on chains determined by angles
Show abstract   🡣
Hide abstract   🡡

We study a variant of the Erdös unit distance problem, concerning angles between successive triples of points chosen from a large finite point set. Specifically, given a large finite set of $n$ points $E$, and a sequence of angles $(\alpha_1,\dots,\alpha_k)$, we give upper and lower bounds on the maximum possible number of tuples of distinct points $(x_1,\dots, x_{k+2})\in E^{k+2}$ satisfying $\angle (x_j,x_{j+1},x_{j+2})=\alpha_j$ for every $1\leq j \leq k$.