Zobrazeno 1 - 10
of 2 231
pro vyhledávání: '"Á Rúzsa"'
In 1948, Shannon used a probabilistic argument to show the existence of codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, based on polynomial evaluations, con
Externí odkaz:
http://arxiv.org/abs/2411.13493
In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a $(1-\epsilon)$-approximation of maximum matching with amortized update time potentially much better than the trivial
Externí odkaz:
http://arxiv.org/abs/2406.13573
Autor:
Behnezhad, Soheil, Ghafari, Alma
We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is on algorithms that maintain the edges
Externí odkaz:
http://arxiv.org/abs/2404.06069
Autor:
Kosciuszko, Tomasz, Schoen, Tomasz
We establish new bounds in the Bogolyubov-Ruzsa lemma, demonstrating that if A is a subset of a finite abelian group with density alpha, then 3A-3A contains a Bohr set of rank O(log^2 (2/alpha)) and radius Omega(log^{-2} (2/alpha)). The Bogolyubov-Ru
Externí odkaz:
http://arxiv.org/abs/2311.04125
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Kovács, Benedek, Nagy, Zoltán Lóránt
In this paper we continue the study of a natural generalization of Tur\'an's forbidden subgraph problem and the Ruzsa-Szemer\'edi problem. Let $ex_F(n,G)$ denote the maximum number of edge-disjoint copies of a fixed simple graph $F$ that can be place
Externí odkaz:
http://arxiv.org/abs/2207.14572
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Sun, Yu-Chen
In this paper we give a short interval version of the Balog-Ruzsa theorem concerning bounds for the $L_1$ norm of the exponential sum over $r$-free numbers. As an application, we give a lower bound for the $L_1$ norm of the exponential sum defined wi
Externí odkaz:
http://arxiv.org/abs/2204.13541
Autor:
Konieczny, Jakub
We show that the Freiman--Ruzsa theorem, characterising finite sets with bounded doubling, leads to an alternative proof of a characterisation of Meyer sets, that is, relatively dense subsets of Euclidean spaces whose difference sets are uniformly di
Externí odkaz:
http://arxiv.org/abs/2103.02289
Autor:
Alon, Noga, Shraibman, Adi
We describe algorithmic Number On the Forehead protocols that provide dense Ruzsa-Szemer\'{e}di graphs. One protocol leads to a simple and natural extension of the original construction of Ruzsa and Szemer\'{e}di. The graphs induced by this protocol
Externí odkaz:
http://arxiv.org/abs/2001.00387