2 Search Results for "Sah, Ashwin"

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-dev.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.50
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Authors: Abhijit S. Mudigonda and R. Ryan Williams

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

Abstract
A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the SAT problem and related problems within the polynomial-time hierarchy. For example, for the SAT problem, the state-of-the-art is that the problem cannot be solved by random-access machines in n^c time and n^o(1) space simultaneously for c < 2cos(π/7) ≈ 1.801. We extend this lower bound approach to the quantum and randomized domains. Combining Grover’s algorithm with components from SAT time-space lower bounds, we show that there are problems verifiable in O(n) time with quantum Merlin-Arthur protocols that cannot be solved in n^c time and n^o(1) space simultaneously for c < (3+√3)/2 ≈ 2.366, a super-quadratic time lower bound. This result and the prior work on SAT can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in O(n) time with (classical) Merlin-Arthur protocols that cannot be solved in n^c randomized time and O(log n) space simultaneously for c < 1.465, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to c < 1.5.
Cite as

Abhijit S. Mudigonda and R. Ryan Williams. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mudigonda_et_al:LIPIcs.ITCS.2021.50,
  author =	{Mudigonda, Abhijit S. and Williams, R. Ryan},
  title =	{{Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{50:1--50:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.50},
  URN =		{urn:nbn:de:0030-drops-135897},
  doi =		{10.4230/LIPIcs.ITCS.2021.50},
  annote =	{Keywords: Time-space tradeoffs, lower bounds, QMA}
}
  • Refine by Author
  • 1 Liu, Yang P.
  • 1 Mudigonda, Abhijit S.
  • 1 Sah, Ashwin
  • 1 Sawhney, Mehtaab
  • 1 Williams, R. Ryan

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 1 Discrepancy
  • 1 Partial Coloring
  • 1 QMA
  • 1 Time-space tradeoffs
  • 1 lower bounds

  • 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