2 Search Results for "Sawhney, Mehtaab"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.101
A Gaussian Fixed Point Random Walk

Authors: Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this note, we design a discrete random walk on the real line which takes steps 0,±1 (and one with steps in {±1,2}) where at least 96% of the signs are ±1 in expectation, and which has 𝒩(0,1) as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk’s discrepancy result for partial colorings and ±1,2 signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.
Cite as

Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney. A Gaussian Fixed Point Random Walk. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 101:1-101:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2022.101,
  author =	{Liu, Yang P. and Sah, Ashwin and Sawhney, Mehtaab},
  title =	{{A Gaussian Fixed Point Random Walk}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{101:1--101:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.101},
  URN =		{urn:nbn:de:0030-drops-156975},
  doi =		{10.4230/LIPIcs.ITCS.2022.101},
  annote =	{Keywords: Discrepancy, Partial Coloring}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.18
Circular Trace Reconstruction

Authors: Shyam Narayanan and Michael Ren

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Trace reconstruction is the problem of learning an unknown string x from independent traces of x, where traces are generated by independently deleting each bit of x with some deletion probability q. In this paper, we initiate the study of Circular trace reconstruction, where the unknown string x is circular and traces are now rotated by a random cyclic shift. Trace reconstruction is related to many computational biology problems studying DNA, which is a primary motivation for this problem as well, as many types of DNA are known to be circular. Our main results are as follows. First, we prove that we can reconstruct arbitrary circular strings of length n using exp(Õ(n^{1/3})) traces for any constant deletion probability q, as long as n is prime or the product of two primes. For n of this form, this nearly matches what was the best known bound of exp(O(n^{1/3})) for standard trace reconstruction when this paper was initially released. We note, however, that Chase very recently improved the standard trace reconstruction bound to exp(Õ(n^{1/5})). Next, we prove that we can reconstruct random circular strings with high probability using n^O(1) traces for any constant deletion probability q. Finally, we prove a lower bound of Ω̃(n³) traces for arbitrary circular strings, which is greater than the best known lower bound of Ω̃(n^{3/2}) in standard trace reconstruction.
Cite as

Shyam Narayanan and Michael Ren. Circular Trace Reconstruction. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{narayanan_et_al:LIPIcs.ITCS.2021.18,
  author =	{Narayanan, Shyam and Ren, Michael},
  title =	{{Circular Trace Reconstruction}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.18},
  URN =		{urn:nbn:de:0030-drops-135573},
  doi =		{10.4230/LIPIcs.ITCS.2021.18},
  annote =	{Keywords: Trace Reconstruction, Deletion Channel, Cyclotomic Integers}
}
  • Refine by Author
  • 1 Liu, Yang P.
  • 1 Narayanan, Shyam
  • 1 Ren, Michael
  • 1 Sah, Ashwin
  • 1 Sawhney, Mehtaab

  • Refine by Classification
  • 2 Mathematics of computing → Probabilistic algorithms

  • Refine by Keyword
  • 1 Cyclotomic Integers
  • 1 Deletion Channel
  • 1 Discrepancy
  • 1 Partial Coloring
  • 1 Trace Reconstruction

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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