Search Results

Documents authored by Dixon, Peter

Document
DOI: 10.4230/LIPIcs.ITCS.2021.66
Complete Problems for Multi-Pseudodeterministic Computations

Authors: Peter Dixon, A. Pavan, and N. V. Vinodchandran

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

Abstract
We exhibit several computational problems that are complete for multi-pseudodeterministic computations in the following sense: (1) these problems admit 2-pseudodeterministic algorithms (2) if there exists a pseudodeterministic algorithm for any of these problems, then any multi-valued function that admits a k-pseudodeterministic algorithm for a constant k, also admits a pseudodeterministic algorithm. We also show that these computational problems are complete for Search-BPP: a pseudodeterministic algorithm for any of these problems implies a pseudodeterministic algorithm for all problems in Search-BPP.
Cite as

Peter Dixon, A. Pavan, and N. V. Vinodchandran. Complete Problems for Multi-Pseudodeterministic Computations. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 66:1-66:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dixon_et_al:LIPIcs.ITCS.2021.66,
  author =	{Dixon, Peter and Pavan, A. and Vinodchandran, N. V.},
  title =	{{Complete Problems for Multi-Pseudodeterministic Computations}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{66:1--66:16},
  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.66},
  URN =		{urn:nbn:de:0030-drops-136050},
  doi =		{10.4230/LIPIcs.ITCS.2021.66},
  annote =	{Keywords: Pseudodeterminism, Completeness, Collision Probability, Circuit Acceptance, Entropy Approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.61
On Pseudodeterministic Approximation Algorithms

Authors: Peter Dixon, A. Pavan, and N. V. Vinodchandran

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We investigate the notion of pseudodeterminstic approximation algorithms. A randomized approximation algorithm A for a function f is pseudodeterministic if for every input x there is a unique value v so that A(x) outputs v with high probability, and v is a good approximation of f(x). We show that designing a pseudodeterministic version of Stockmeyer's well known approximation algorithm for the NP-membership counting problem will yield a new circuit lower bound: if such an approximation algorithm exists, then for every k, there is a language in the complexity class ZPP^{NP}_{tt} that does not have n^k-size circuits. While we do not know how to design such an algorithm for the NP-membership counting problem, we show a general result that any randomized approximation algorithm for a counting problem can be transformed to an approximation algorithm that has a constant number of influential random bits. That is, for most settings of these influential bits, the approximation algorithm will be pseudodeterministic.
Cite as

Peter Dixon, A. Pavan, and N. V. Vinodchandran. On Pseudodeterministic Approximation Algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 61:1-61:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dixon_et_al:LIPIcs.MFCS.2018.61,
  author =	{Dixon, Peter and Pavan, A. and Vinodchandran, N. V.},
  title =	{{On Pseudodeterministic Approximation Algorithms}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{61:1--61:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.61},
  URN =		{urn:nbn:de:0030-drops-96431},
  doi =		{10.4230/LIPIcs.MFCS.2018.61},
  annote =	{Keywords: Approximation Algorithms, Circuit lower bounds, Pseudodeterminism}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.31
A Note on the Advice Complexity of Multipass Randomized Logspace

Authors: Peter Dixon, Debasis Mandal, A. Pavan, and N. V. Vinodchandran

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Investigating the complexity of randomized space-bounded machines that are allowed to make multiple passes over the random tape has been of recent interest. In particular, it has been shown that derandomizing such probabilistic machines yields a weak but new derandomization of probabilistic time-bounded classes. In this paper we further explore the complexity of such machines. In particular, as our main result we show that for any epsilon<1, every language that is accepted by an O(n^epsilon)-pass, randomized logspace machine can be simulated in deterministic logspace with linear amount of advice. This result extends an earlier result of Fortnow and Klivans who showed that RL is in deterministic logspace with linear advice.
Cite as

Peter Dixon, Debasis Mandal, A. Pavan, and N. V. Vinodchandran. A Note on the Advice Complexity of Multipass Randomized Logspace. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 31:1-31:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dixon_et_al:LIPIcs.MFCS.2016.31,
  author =	{Dixon, Peter and Mandal, Debasis and Pavan, A. and Vinodchandran, N. V.},
  title =	{{A Note on the Advice Complexity of Multipass Randomized Logspace}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{31:1--31:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.31},
  URN =		{urn:nbn:de:0030-drops-65003},
  doi =		{10.4230/LIPIcs.MFCS.2016.31},
  annote =	{Keywords: space-bounded computations, randomized machines, advice}
}
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