Search Results

Documents authored by Eskenazis, Alexandros

Document
DOI: 10.4230/LIPIcs.SoCG.2024.55
Dimensionality of Hamming Metrics and Rademacher Type

Authors: Alexandros Eskenazis

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Let X be a finite-dimensional normed space. We prove that if the Hamming cube {-1,1}ⁿ embeds into X with bi-Lipschitz distortion at most D ≥ 1, then dim(X) ≳ sup_{p ∈ [1,2]} n^p/(D^p 𝖳_p(X)^p), where 𝖳_p(X) is the Rademacher type p constant of X. This estimate yields a mutual refinement of distortion lower bounds which follow from works of Oleszkiewicz (1996) and Ivanisvili, van Handel and Volberg (2020). The proof relies on a combination of semigroup techniques on the biased hypercube with the Borsuk-Ulam theorem from algebraic topology.
Cite as

Alexandros Eskenazis. Dimensionality of Hamming Metrics and Rademacher Type. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eskenazis:LIPIcs.SoCG.2024.55,
  author =	{Eskenazis, Alexandros},
  title =	{{Dimensionality of Hamming Metrics and Rademacher Type}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.55},
  URN =		{urn:nbn:de:0030-drops-200004},
  doi =		{10.4230/LIPIcs.SoCG.2024.55},
  annote =	{Keywords: Hamming cube, Rademacher type, metric embeddings, Borsuk-Ulam theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.40
ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

Authors: Alexandros Eskenazis

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Fix p ∈ [1,∞), K ∈ (0,∞) and a probability measure μ. We prove that for every n ∈ ℕ, ε ∈ (0,1) and x₁,…,x_n ∈ L_p(μ) with ‖max_{i ∈ {1,…,n}}|x_i|‖_{L_p(μ)} ≤ K, there exists d ≤ (32e² (2K)^{2p}log n)/ε² and vectors y₁,…, y_n ∈ 𝓁_p^d such that ∀i,j∈{1,…,n}, ‖x_i-x_j‖^p_{L_p(μ)}-ε ≤ ‖y_i-y_j‖_{𝓁_p^d}^p ≤ ‖x_i-x_j‖^p_{L_p(μ)}+ε. Moreover, the argument implies the existence of a greedy algorithm which outputs {y_i}_{i = 1}ⁿ after receiving {x_i}_{i = 1}ⁿ as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of ε-isometric dimension reduction of the unit ball B_E of a normed space (E,‖⋅‖_E) and we prove that B_{𝓁_p} does not admit ε-isometric dimension reduction by linear operators for any value of p≠2.
Cite as

Alexandros Eskenazis. ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eskenazis:LIPIcs.SoCG.2022.40,
  author =	{Eskenazis, Alexandros},
  title =	{{\epsilon-Isometric Dimension Reduction for Incompressible Subsets of 𝓁\underlinep}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.40},
  URN =		{urn:nbn:de:0030-drops-160486},
  doi =		{10.4230/LIPIcs.SoCG.2022.40},
  annote =	{Keywords: Dimension reduction, \epsilon-isometric embedding, Maurey’s empirical method, change of measure}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact