3 Search Results for "Pemantle, Robin"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.102
Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Authors: Ittai Rubinstein

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the trace reconstruction problem, one is given many outputs (called traces) of a noise channel applied to the same input message x, and is asked to recover the input message. Common noise channels studied in the context of trace reconstruction include the deletion channel which deletes each bit w.p. δ, the insertion channel which inserts a G_j i.i.d. uniformly distributed bits before each bit of the input message (where G_j is i.i.d. geometrically distributed with parameter σ) and the symmetry channel which flips each bit of the input message i.i.d. w.p. γ. De et al. and Nazarov and Peres [De et al., 2017; Nazarov and Peres, 2017] showed that any string x can be reconstructed from exp(O(n^{1/3})) traces. Holden et al. [Holden et al., 2018] adapted the techniques used to prove this upper bound, to construct an algorithm for average-case trace reconstruction from the insertion-deletion channel with a sample complexity of exp(O(log^{1/3} n)). However, it is not clear how to apply their techniques more generally and in particular for the recent worst-case upper bound of exp(Õ(n^{1/5})) shown by Chase [Chase, 2021] for the deletion channel. We prove a general reduction from the average-case to smaller instances of a problem similar to worst-case and extend Chase’s upper-bound to this problem and to symmetry and insertion channels as well. Using this reduction and generalization of Chase’s bound, we introduce an algorithm for the average-case trace reconstruction from the symmetry-insertion-deletion channel with a sample complexity of exp(Õ(log^{1/5} n)).
Cite as

Ittai Rubinstein. Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rubinstein:LIPIcs.ICALP.2023.102,
  author =	{Rubinstein, Ittai},
  title =	{{Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.102},
  URN =		{urn:nbn:de:0030-drops-181542},
  doi =		{10.4230/LIPIcs.ICALP.2023.102},
  annote =	{Keywords: Trace Reconstruction, Synchronization Channels, Computational Learning Theory, Computational Biology}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.12
Diagonal Asymptotics for Symmetric Rational Functions via ACSV

Authors: Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We consider asymptotics of power series coefficients of rational functions of the form 1/Q where Q is a symmetric multilinear polynomial. We review a number of such cases from the literature, chiefly concerned either with positivity of coefficients or diagonal asymptotics. We then analyze coefficient asymptotics using ACSV (Analytic Combinatorics in Several Variables) methods. While ACSV sometimes requires considerable overhead and geometric computation, in the case of symmetric multilinear rational functions there are some reductions that streamline the analysis. Our results include diagonal asymptotics across entire classes of functions, for example the general 3-variable case and the Gillis-Reznick-Zeilberger (GRZ) case, where the denominator in terms of elementary symmetric functions is 1 - e_1 + c e_d in any number d of variables. The ACSV analysis also explains a discontinuous drop in exponential growth rate for the GRZ class at the parameter value c = (d-1)^{d-1}, previously observed for d=4 only by separately computing diagonal recurrences for critical and noncritical values of c.
Cite as

Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub. Diagonal Asymptotics for Symmetric Rational Functions via ACSV. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baryshnikov_et_al:LIPIcs.AofA.2018.12,
  author =	{Baryshnikov, Yuliy and Melczer, Stephen and Pemantle, Robin and Straub, Armin},
  title =	{{Diagonal Asymptotics for Symmetric Rational Functions via ACSV}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.12},
  URN =		{urn:nbn:de:0030-drops-89055},
  doi =		{10.4230/LIPIcs.AofA.2018.12},
  annote =	{Keywords: Analytic combinatorics, generating function, coefficient, lacuna, positivity, Morse theory, D-finite, smooth point}
}
Document
DOI: 10.4230/DagSemProc.05021.19
Some Notes On ``When is 0.999... equal to 1?

Authors: Carsten Schneider

Published in: Dagstuhl Seminar Proceedings, Volume 5021, Mathematics, Algorithms, Proofs (2006)

Abstract
In joint work Robin Pemantle and I (2004) consider a doubly infinite sum which is not equal to 1, as first suspected, but evaluates to a sum of products of values of the zeta function. Subsequently, I report on this project.
Cite as

Carsten Schneider. Some Notes On ``When is 0.999... equal to 1?. In Mathematics, Algorithms, Proofs. Dagstuhl Seminar Proceedings, Volume 5021, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schneider:DagSemProc.05021.19,
  author =	{Schneider, Carsten},
  title =	{{Some Notes On ``When is 0.999... equal to 1?}},
  booktitle =	{Mathematics, Algorithms, Proofs},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5021},
  editor =	{Thierry Coquand and Henri Lombardi and Marie-Fran\c{c}oise Roy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05021.19},
  URN =		{urn:nbn:de:0030-drops-2755},
  doi =		{10.4230/DagSemProc.05021.19},
  annote =	{Keywords: Symbolic summation, computer algebra, proofs, harmonic numbers, zeta-relations}
}
  • Refine by Author
  • 1 Baryshnikov, Yuliy
  • 1 Melczer, Stephen
  • 1 Pemantle, Robin
  • 1 Rubinstein, Ittai
  • 1 Schneider, Carsten
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Sample complexity and generalization bounds

  • Refine by Keyword
  • 1 Analytic combinatorics
  • 1 Computational Biology
  • 1 Computational Learning Theory
  • 1 D-finite
  • 1 Morse theory
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2006
  • 1 2018
  • 1 2023

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