MSK, UTC +3

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

MSK, UTC +3

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

- K. Eto, S. Matsuzaki, M. Ozawa, An obstruction to embedding 2-dimensional complexes into the
3-sphere .*Topol. Appl. 198 (2016)*, 117-125. - M. Eudave-Muñoz, M. Ozawa, Characterization of 3-punctured spheres in non-hyperbolic link exteriors.
*Topol. Appl. 264 (2019)*, 300-312. - M. Eudave-Muñoz, M. Ozawa, The maximum and minimum genus of a multibranched surface.
*Topol. Appl. (2020)*, 107502. - K. Ishihara, Y. Koda, M. Ozawa, K. Shimokawa, Neighborhood equivalence for multibranched surfaces in 3-manifolds.
*Topol. Appl. 257 (2019)*, 11-21. - S. Matsuzaki, M. Ozawa, Genera and minors of multibranched surfaces.
*Topol. Appl. 230 (2017)*,621–638 . - M. Ozawa, A partial order on multibranched surfaces in 3-manifolds.
*Topol. Appl. 272 (2020)*, 107074.

MSK, UTC +3

Algorithms for recognizing graph planarity are well-known.
The classical topics in mathematics and computer science is recognizing
realizability of hypergraphs in **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

- in [2, 1] for $(r-1)d=rk$;
- in [4] for $rd\ge(r+1)k+3$, see also [3].

- S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner,
Eliminating Higher-Multiplicity Intersections, III. Codimension 2.
*Israel J. Math.*, to appear, arXiv:1511.03501. - I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems. arXiv:1508.02349.
- I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the $r$-Metastable Range. arXiv:1601.00876.
- A. Skopenkov, Eliminating higher-multiplicity intersections in the metastable dimension range. arXiv:1704.00143.
- A. Skopenkov,
Invariants of graph drawings in the plane.
abridged version:
*Arnold Math. J. 2020*, full version: arXiv:1805.10237.

MSK, UTC +3

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].

- Arseniy Akopyan, Sergey Avvakumov, and Roman Karasev, Convex fair partitions into an arbitrary number of pieces. arXiv:1804.03057.
- Sergey Avvakumov and Roman Karasev, Envy-free division using mapping degree. arXiv:1907.11183.
- Sergey Avvakumov, Roman Karasev, Arkadiy Skopenkov, Stronger counterexamples to the topological Tverberg conjecture. arXiv:1908.08731.
- Sergey Avvakumov and Sergey Kudrya, Vanishing of all equivariant obstructions and the mapping degree. arXiv:1910.12628.
- Sergey Avvakumov and Roman Karasev, Equipartition of a segment. arXiv:2009.09862.

MSK, UTC +3

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.

- E. Kolpakov, A 'converse' to the Constraint Lemma. arXiv:1903.08910.

MSK, UTC +3

MSK, UTC +3

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:**

- 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$). - If $r$ is not a prime power,
**(a)**is no longer true (Avvakumov and Karasev). - 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:**

- 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.
- If $r$ is neither a prime nor equal to $4$, the statement
**A**is not true. - 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}}$. - Statement
**A**yields an alternative proof of the result**a**of Avvakumov and Karasev. - 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.

MSK, UTC +3

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.

MSK, UTC +3

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.

- Martin Čadek, Marek Krčál, Lukáš Vokřínek,
Algorithmic solvability of the lifting-extension problem.
*Discrete Comput. Geom.*, 57(4):915--965, 2017. - 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. - 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. - 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.

MSK, UTC +3

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

MSK, UTC +3

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

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].

- S. Parsa,
Instability of the Smith Index Under Joins and Applications to Embeddability.
*Arxiv preprint*: arXiv:2103.02563, 2021.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK,

UTC +3

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.

MSK,

UTC +3

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.

MSK,

UTC +3

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.

MSK, UTC +3

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.

- Manik Dhar, Zeev Dvir, and Ben Lund. Furstenberg sets in finite fields: Explaining and improving the Ellenberg-Erman proof.
*Preprint arXiv:1909.02431*. - Manik Dhar, Zeev Dvir, and Ben Lund. Simple proofs for Furstenberg sets over finite fields..
*Preprint arXiv:1909.03180*. - Zeev Dvir. On the size of Kakeya sets in finite fields..
*Journal of the American Mathematical Society*, 22(4):1093--1097, 2009. - Jordan Ellenberg and Daniel Erman. Furstenberg sets and Furstenberg schemes over finite fields..
*Algebra & Number Theory*, 10(7):1415--1436, 2016. - 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.

MSK, UTC +3

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.

MSK, UTC +3

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.$

MSK, UTC +3

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.

MSK, UTC +3

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.

MSK, UTC +3

MSK, UTC +3

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.

MSK, UTC +3

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$.