DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.44

Density Frankl–Rödl on the Sphere

Authors: Venkatesan Guruswami and Shilun Li

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

Abstract

We establish a density variant of the Frankl–Rödl theorem on the sphere 𝕊^{n-1}, which concerns avoiding pairs of vectors with a specific distance, or equivalently, a prescribed inner product. In particular, we establish lower bounds on the probability that a randomly chosen pair of such vectors lies entirely within a measurable subset A ⊆ 𝕊^{n-1} of sufficiently large measure. Additionally, we prove a density version of spherical avoidance problems, which generalize from pairwise avoidance to broader configurations with prescribed pairwise inner products. Our framework encompasses a class of configurations we call inductive configurations, which include simplices with any prescribed inner product -1 < r < 1. As a consequence of our density statement, we show that all inductive configurations are sphere Ramsey.

Cite as

Venkatesan Guruswami and Shilun Li. Density Frankl–Rödl on the Sphere. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2025.44,
  author =	{Guruswami, Venkatesan and Li, Shilun},
  title =	{{Density Frankl–R\"{o}dl on the Sphere}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.44},
  URN =		{urn:nbn:de:0030-drops-244108},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.44},
  annote =	{Keywords: Frankl–R\"{o}dl, Sphere Ramsey, Sphere Avoidance, Reverse Hypercontractivity, Forbidden Angles}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.50

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble

Authors: Venkatesan Guruswami and Shilun Li

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

Abstract

We present an explicit construction of a sequence of rate 1/2 Wozencraft ensemble codes (over any fixed finite field 𝔽_q) that achieve minimum distance Ω(√k) where k is the message length. The coefficients of the Wozencraft ensemble codes are constructed using Sidon Sets and the cyclic structure of 𝔽_{q^k} where k+1 is prime with q a primitive root modulo k+1. Assuming Artin’s conjecture, there are infinitely many such k for any prime power q.

Cite as

Venkatesan Guruswami and Shilun Li. A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2023.50,
  author =	{Guruswami, Venkatesan and Li, Shilun},
  title =	{{A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{50:1--50:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.50},
  URN =		{urn:nbn:de:0030-drops-188751},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.50},
  annote =	{Keywords: Algebraic codes, Pseudorandomness, Explicit Construction, Wozencraft Ensemble, Sidon Sets}
}

Search Results

Documents authored by Li, Shilun

Density Frankl–Rödl on the Sphere

Abstract

Cite as

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble

Abstract

Cite as

Thanks for your feedback!

Could not send message