4 Search Results for "Lecomte, Victor"

Document
DOI: 10.4230/LIPIcs.CCC.2022.10
New Near-Linear Time Decodable Codes Closer to the GV Bound

Authors: Guy Blanc and Dean Doron

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We construct a family of binary codes of relative distance 1/2-ε and rate ε² ⋅ 2^(-log^α (1/ε)) for α ≈ 1/2 that are decodable, probabilistically, in near-linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who gave a randomized decoding of Ta-Shma codes with α ≈ 5/6 [Ta-Shma, 2017; Jeronimo et al., 2021]. Each code in our family can be constructed in probabilistic polynomial time, or deterministic polynomial time given sufficiently good explicit 3-uniform hypergraphs. Our construction is based on a new graph-based bias amplification method. While previous works start with some base code of relative distance 1/2-ε₀ for ε₀ ≫ ε and amplify the distance to 1/2-ε by walking on an expander, or on a carefully tailored product of expanders, we walk over very sparse, highly mixing, hypergraphs. Study of such hypergraphs further offers an avenue toward achieving rate Ω̃(ε²). For our unique- and list-decoding algorithms, we employ the framework developed in [Jeronimo et al., 2021].
Cite as

Guy Blanc and Dean Doron. New Near-Linear Time Decodable Codes Closer to the GV Bound. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 10:1-10:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.CCC.2022.10,
  author =	{Blanc, Guy and Doron, Dean},
  title =	{{New Near-Linear Time Decodable Codes Closer to the GV Bound}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{10:1--10:40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.10},
  URN =		{urn:nbn:de:0030-drops-165726},
  doi =		{10.4230/LIPIcs.CCC.2022.10},
  annote =	{Keywords: Unique decoding, list decoding, the Gilbert-Varshamov bound, small-bias sample spaces, hypergraphs, expander walks}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.19
The Composition Complexity of Majority

Authors: Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {0,1} is an arbitrary function that queries only k ≪ n variables and h: {0,1}^m → {0,1} is an arbitrary combining function. We prove an optimal lower bound of m ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) larger than the ideal m = n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority. Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits. Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).
Cite as

Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The Composition Complexity of Majority. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 19:1-19:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lecomte_et_al:LIPIcs.CCC.2022.19,
  author =	{Lecomte, Victor and Ramakrishnan, Prasanna and Tan, Li-Yang},
  title =	{{The Composition Complexity of Majority}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{19:1--19:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.19},
  URN =		{urn:nbn:de:0030-drops-165818},
  doi =		{10.4230/LIPIcs.CCC.2022.19},
  annote =	{Keywords: computational complexity, circuit lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.68
Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality

Authors: Victor Lecomte and Omri Weinstein

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence X ∈ [n]^m. Both bounds play a central role in the ongoing pursuit of the dynamic optimality conjecture (Sleator and Tarjan, 1985), but their relationship remained unknown for more than three decades. We show that Wilber’s Funnel bound dominates his Alternation bound for all X, and give a tight Θ(lg lg n) separation for some X, answering Wilber’s conjecture and an open problem of Iacono, Demaine et. al. The main ingredient of the proof is a new symmetric characterization of Wilber’s Funnel bound, which proves that it is invariant under rotations of X. We use this characterization to provide initial indication that the Funnel bound matches the Independent Rectangle bound (Demaine et al., 2009), by proving that when the Funnel bound is constant, IRB_upRect is linear. To the best of our knowledge, our results provide the first progress on Wilber’s conjecture that the Funnel bound is dynamically optimal (1986).
Cite as

Victor Lecomte and Omri Weinstein. Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 68:1-68:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lecomte_et_al:LIPIcs.ESA.2020.68,
  author =	{Lecomte, Victor and Weinstein, Omri},
  title =	{{Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{68:1--68:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.68},
  URN =		{urn:nbn:de:0030-drops-129342},
  doi =		{10.4230/LIPIcs.ESA.2020.68},
  annote =	{Keywords: data structures, binary search trees, dynamic optimality, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.08271.7
Topological Complexity of omega-Powers: Extended Abstract

Authors: Olivier Finkel and Dominique Lecomte

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)

Abstract
The operation of taking the omega-power $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omega-languages. Since the set $X^omega$ of infinite words over a finite alphabet $X$ can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers of finitary languages naturally arises and has been posed by Damian Niwinski (1990), Pierre Simonnet (1992), and Ludwig Staiger (1997). We investigate the topological complexity of omega-powers. We prove the following very surprising results which show that omega-powers exhibit a great opological complexity: for each non-null countable ordinal $xi$, there exist some $Sigma^0_xi$-complete omega-powers, and some $Pi^0_xi$-complete omega-powers. On the other hand, the Wadge hierarchy is a great refinement of the Borel hierarchy, determined by Bill Wadge. We show that, for each ordinal $xi$ greater than or equal to 3, there are uncountably many Wadge degrees of omega-powers of Borel rank $xi +1$. Using tools of effective descriptive set theory, we prove some effective versions of the above results.
Cite as

Olivier Finkel and Dominique Lecomte. Topological Complexity of omega-Powers: Extended Abstract. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{finkel_et_al:DagSemProc.08271.7,
  author =	{Finkel, Olivier and Lecomte, Dominique},
  title =	{{Topological Complexity of omega-Powers: Extended Abstract}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.7},
  URN =		{urn:nbn:de:0030-drops-16505},
  doi =		{10.4230/DagSemProc.08271.7},
  annote =	{Keywords: Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}
  • Refine by Author
  • 2 Lecomte, Victor
  • 1 Blanc, Guy
  • 1 Doron, Dean
  • 1 Finkel, Olivier
  • 1 Lecomte, Dominique
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Borel ranks
  • 1 Borel sets
  • 1 Cantor topology
  • 1 Infinite words
  • 1 Unique decoding
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2022
  • 1 2008
  • 1 2020

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 Imprint Privacy Contact