Search Results

Documents authored by Kupavskii, Andrey

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.18
Sketching Distances in Monotone Graph Classes

Authors: Louis Esperet, Nathaniel Harms, and Andrey Kupavskii

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We study the problems of adjacency sketching, small-distance sketching, and approximate distance threshold (ADT) sketching for monotone classes of graphs. The algorithmic problem is to assign random sketches to the vertices of any graph G in the class, so that adjacency, exact distance thresholds, or approximate distance thresholds of two vertices u,v can be decided (with probability at least 2/3) from the sketches of u and v, by a decoder that does not know the graph. The goal is to determine when sketches of constant size exist. Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size small-distance sketches exist if and only if the class has bounded expansion; constant-size ADT sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has a constant-size ADT sketch; and a class may have arbitrarily small expansion without admitting a constant-size ADT sketch.
Cite as

Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching Distances in Monotone Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.APPROX/RANDOM.2022.18,
  author =	{Esperet, Louis and Harms, Nathaniel and Kupavskii, Andrey},
  title =	{{Sketching Distances in Monotone Graph Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.18},
  URN =		{urn:nbn:de:0030-drops-171406},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.18},
  annote =	{Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.48
Almost Sharp Bounds on the Number of Discrete Chains in the Plane

Authors: Nóra Frankl and Andrey Kupavskii

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3.
Cite as

Nóra Frankl and Andrey Kupavskii. Almost Sharp Bounds on the Number of Discrete Chains in the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.48,
  author =	{Frankl, N\'{o}ra and Kupavskii, Andrey},
  title =	{{Almost Sharp Bounds on the Number of Discrete Chains in the Plane}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.48},
  URN =		{urn:nbn:de:0030-drops-122064},
  doi =		{10.4230/LIPIcs.SoCG.2020.48},
  annote =	{Keywords: unit distance problem, unit distance graphs, discrete chains}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.38
The Crossing Tverberg Theorem

Authors: Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
Cite as

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38,
  author =	{Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli},
  title =	{{The Crossing Tverberg Theorem}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.38},
  URN =		{urn:nbn:de:0030-drops-104423},
  doi =		{10.4230/LIPIcs.SoCG.2019.38},
  annote =	{Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.54
New Lower Bounds for epsilon-Nets

Authors: Andrey Kupavskii, Nabil Mustafa, and János Pach

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilon-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilon-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^4 by a family of half-spaces such that the size of any epsilon-net for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R^d, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilon-nets is tight.
Cite as

Andrey Kupavskii, Nabil Mustafa, and János Pach. New Lower Bounds for epsilon-Nets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kupavskii_et_al:LIPIcs.SoCG.2016.54,
  author =	{Kupavskii, Andrey and Mustafa, Nabil and Pach, J\'{a}nos},
  title =	{{New Lower Bounds for epsilon-Nets}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.54},
  URN =		{urn:nbn:de:0030-drops-59467},
  doi =		{10.4230/LIPIcs.SoCG.2016.54},
  annote =	{Keywords: epsilon-nets; lower bounds; geometric set systems; shallow-cell complexity; half-spaces}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact