Andrey Kupavskii

activity

20242026

collaborators

15 papers

cs.DC2026

SP-Allreduce: Symmetric Tree Schedules for Tori and Beyond

Mikhail Cherniavskii, Andrey Kupavskii, Georgy Mironov +1

Allreduce is a fundamental communication primitive in large-scale distributed training, and torus interconnects remain widely deployed in high-performance systems. We introduce SP-…

cs.DS2026

Approximation algorithms via discrepancy with hard constraints

Mikhail Cherniavskii, Andrey Kupavskii, Stanislav Moiseev +1

In this paper, we present a discrepancy-based approach to cost-preserving rounding under hard constraints. Starting from a feasible fractional solution, our rounding procedure pres…

cs.DS2026

Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings

Mikhail Cherniavskii, Arseni Fedorovich, Mikhail Koshelev +4

We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a $2.77$ -approximation without release dat…

cs.DM2026

Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy

Alexander Shekhovtsov, Georgy Sokolov, Mikhail Cherniavskii +1

This paper studies the problem of fair division of indivisible goods among $k$ groups of $n_{1}, \dots, n_{k}$ agents. We look at the worst downward deviation $\textit{PROP}(n_1,\ldots…

math.CO2026

A Complete Intersection Theorem for Large Permutation Groups

Nathan Keller, Andrey Kupavskii, Noam Lifshitz +1

A family of permutations is called $t$ -intersecting if any two permutations in the family agree on at least $t$ elements. We prove that there exists $n_{0} \in N$ such that…

math.CO2026

Structure and properties of large cross-intersecting families

Yang Huang, Andrey Kupavskii

The study of intersecting families, initiated by Erdős, Ko, and Rado, is a central topic in extremal combinatorics. A classical stability result of Hilton and Milner determines the…

math.CO2026

Matchings in permutations

Eduard Inozemtsev, Dmitrii Kolupaev, Andrey Kupavskii

We say that two permutations $[n] \to [n]$ intersect if they map some element $x$ to the same element $y$ . A matching in a family of permutations is a collection of pairwise disjoin…

math.CO2026

More on the Erd\H os--Kleitman problem on matchings in set families

Andrey Kupavskii, Georgy Sokolov

Let $e (n, s)$ denote the maximum size of a family $F$ of subsets of an $n$ -element set that contains no $s$ pairwise disjoint members. In 1968, answering a question of Erd…

math.CO2026

Structure of $t$ -Intersecting Families of Vector Spaces

Ferdinand Ihringer, Andrey Kupavskii

We study $t$ -intersecting and $t$ -cross-intersecting families of $k$ -dimensional subspaces in finite vector spaces of dimension $n$ . We show that all large $t$ -intersecting familie…

math.CO2026

Families without $s$ -matchings: the other end

Andrey Kupavskii, Georgy Sokolov

In this paper, we determine the largest family $F \subset 2^{[n]}$ without $s$ pairwise disjoint sets, provided $n = m s + c$ for positive integers $m, c$ , and $s \geq s_0(m, c)…

math.CO2026

Frankl's diversity theorem for permutations

Eduard Inozemtsev, Andrey Kupavskii

In 1987, Frankl proved an influential stability result for the Erd\H os--Ko--Rado theorem, which bounds the size of an intersecting family in terms of its distance from the nearest…

cs.DM2025

Near-optimal edge partitioning via intersecting families

Alexander Yakunin, Andrey Kupavskii, Alexander Sushin +1

We study the problem of edge partitioning, where the goal is to partition the edge set of a graph into $k$ parts. The replication factor of a vertex $v$ is the number of parts that…

math.CO2024

Structure of non-trivial intersecting families

Andrey Kupavskii

We say that a family of $k$ -subsets of an $n$ -element set is {\it intersecting}, if any two of its sets intersect. In this paper, we study the structure of large intersecting famil…

math.CO2024

An almost complete $t$ -intersection theorem for permutations

Andrey Kupavskii

For any $ε > 0$ and $n > (1 + ε) t$ , $n > n_{0} (ε)$ we determine the size of the largest $t$ -intersecting family of permutations, as well as give a sharp stability result. This resolves a con…

math.CO2024

Intersecting families with covering number $3$

Andrey Kupavskii

A covering number of a family is the size of the smallest set that intersects all sets from the family. In 1978 Frankl determined for $n \geq n_{0} (k)$ the largest intersecting family…

SP-Allreduce: Symmetric Tree Schedules for Tori and Beyond

Approximation algorithms via discrepancy with hard constraints

Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings

Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy

A Complete Intersection Theorem for Large Permutation Groups

Structure and properties of large cross-intersecting families

Matchings in permutations

More on the Erd\H os--Kleitman problem on matchings in set families

Structure of t-Intersecting Families of Vector Spaces

Families without s-matchings: the other end

Frankl's diversity theorem for permutations

Near-optimal edge partitioning via intersecting families

Structure of non-trivial intersecting families

An almost complete t-intersection theorem for permutations

Intersecting families with covering number 3

Structure of $t$ -Intersecting Families of Vector Spaces

Families without $s$ -matchings: the other end

An almost complete $t$ -intersection theorem for permutations

Intersecting families with covering number $3$