Found 2 Possible Name Variants:

Document

Brief Announcement

**Published in:** LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

In this work, we study the class of problems solvable by (deterministic) Adaptive Massively Parallel Computations in constant rounds from a computational complexity theory perspective. A language L is in the class AMPC⁰ if, for every ε > 0, there is a deterministic AMPC algorithm running in constant rounds with a polynomial number of processors, where the local memory of each machine s = O(N^ε). We prove that the space-bounded complexity class ReachUL is a proper subclass of AMPC⁰. The complexity class ReachUL lies between the well-known space-bounded complexity classes Deterministic Logspace (DLOG) and Nondeterministic Logspace (NLOG). In contrast, we establish that it is unlikely that PSPACE admits AMPC algorithms, even with polynomially many rounds. We also establish that showing PSPACE is a subclass of nonuniform-AMPC with polynomially many rounds leads to a significant separation result in complexity theory, namely PSPACE is a proper subclass of EXP^{Σ₂^{𝖯}}.

Michael Chen, A. Pavan, and N. V. Vinodchandran. Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.DISC.2023.37, author = {Chen, Michael and Pavan, A. and Vinodchandran, N. V.}, title = {{Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {37:1--37:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.37}, URN = {urn:nbn:de:0030-drops-191634}, doi = {10.4230/LIPIcs.DISC.2023.37}, annote = {Keywords: Massively Parallel Computation, AMPC, Complexity Classes, LogSpace, NL, PSPACE} }

Document

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

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.

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

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

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.

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

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

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.

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} }

Document

**Published in:** LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

We study the Minimum Circuit Size Problem (MCSP): given the
truth-table of a Boolean function f and a number k, does there
exist a Boolean circuit of size at most k computing f? This is a
fundamental NP problem that is not known to be NP-complete. Previous
work has studied consequences of the NP-completeness of MCSP. We
extend this work and consider whether MCSP may be complete for NP
under more powerful reductions. We also show that NP-completeness of
MCSP allows for amplification of circuit complexity.
We show the following results.
- If MCSP is NP-complete via many-one reductions, the following circuit complexity amplification result holds: If NP cap co-NP requires 2^n^{Omega(1)-size circuits, then E^NP requires 2^Omega(n)-size circuits.
- If MCSP is NP-complete under truth-table reductions, then
EXP neq NP cap SIZE(2^n^epsilon) for some epsilon> 0 and EXP neq ZPP. This result extends to polylog Turing reductions.

John M. Hitchcock and A. Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 236-245, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2015.236, author = {Hitchcock, John M. and Pavan, A.}, title = {{On the NP-Completeness of the Minimum Circuit Size Problem}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {236--245}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.236}, URN = {urn:nbn:de:0030-drops-56613}, doi = {10.4230/LIPIcs.FSTTCS.2015.236}, annote = {Keywords: Minimum Circuit Size, NP-completeness, truth-table reductions, circuit complexity} }

Document

**Published in:** LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a worst-case hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time O(2^2^n^c) (for some c > 1) accepting Sigma^* whose accepting computations cannot be computed by bounded-error, probabilistic machines running in time O(2^2^{beta * 2^n^c) (for some beta > 0). This is the first result that separates completeness notions for NP under a worst-case hardness hypothesis.

Debasis Mandal, A. Pavan, and Rajeswari Venugopalan. Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 445-456, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mandal_et_al:LIPIcs.FSTTCS.2014.445, author = {Mandal, Debasis and Pavan, A. and Venugopalan, Rajeswari}, title = {{Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {445--456}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.445}, URN = {urn:nbn:de:0030-drops-48621}, doi = {10.4230/LIPIcs.FSTTCS.2014.445}, annote = {Keywords: Cook reduction, Karp reduction, NP-completeness, Turing completeness, many-one completeness} }

Document

**Published in:** LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time, O(n^{2/3} * g^{1/3})-space algorithm for directed graphs embedded on orientable surfaces of genus g. (2) A polynomial-time, O(n^{2/3})-space algorithm for all H-minor-free graphs given the tree decomposition, and (3) for K_{3,3}-free and K_5-free graphs, a polynomial-time, O(n^{1/2 + epsilon})-space algorithm, for every epsilon > 0.
For the general directed reachability problem, the best known simultaneous time-space upper bound is the BBRS bound, due to Barnes, Buss, Ruzzo, and Schieber, which achieves a space bound of O(n/2^{k * sqrt(log(n))}) with polynomial running time, for any constant k. It is a significant open question to improve this bound for reachability over general directed graphs. Our algorithms beat the BBRS bound for graphs embedded on surfaces of genus n/2^{omega(sqrt(log(n))}, and for all H-minor-free graphs. This significantly broadens the class of directed graphs for which the BBRS bound can be improved.

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin Forrest Yang. New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 585-595, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2014.585, author = {Chakraborty, Diptarka and Pavan, A. and Tewari, Raghunath and Vinodchandran, N. V. and Yang, Lin Forrest}, title = {{New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {585--595}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.585}, URN = {urn:nbn:de:0030-drops-48730}, doi = {10.4230/LIPIcs.FSTTCS.2014.585}, annote = {Keywords: Reachability, Space complexity, Time-Space Efficient Algorithms, Graphs on Surfaces, Minor Free Graphs, Savitch's Algorithm, BBRS Bound} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

This paper presents the following results on sets that are complete for $\NP$.
\begin{enumerate}
\item If there is a problem in $\NP$ that requires $\twonO$ time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
\item If there is a problem in $\CoNP$ that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
\item If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in $\NP \cap \CoNP$, then there is a Turing complete language for $\NP$
that is not many-one complete.
\end{enumerate}
Our first two results use worst-case hardness hypotheses whereas
earlier work that showed similar results relied on average-case or
almost-everywhere hardness assumptions. The use of average-case and
worst-case hypotheses in the last result is unique as previous results
obtaining the same consequence relied on almost-everywhere hardness
results.

Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan. Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 429-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.STACS.2010.2462, author = {Gu, Xiaoyang and Hitchcock, John M. and Pavan, Aduri}, title = {{Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {429--440}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2462}, URN = {urn:nbn:de:0030-drops-24627}, doi = {10.4230/LIPIcs.STACS.2010.2462}, annote = {Keywords: Computational complexity, NP-completeness} }

Document

**Published in:** LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

We clarify the role of Kolmogorov complexity in the area of randomness
extraction. We show that a computable function is an almost
randomness extractor if and only if it is a Kolmogorov complexity
extractor, thus establishing a fundamental equivalence between two
forms of extraction studied in the literature: Kolmogorov extraction
and randomness extraction. We present a distribution ${\cal M}_k$
based on Kolmogorov complexity that is complete for randomness
extraction in the sense that a computable function is an almost
randomness extractor if and only if it extracts randomness from ${\cal
M}_k$.

John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran. Kolmogorov Complexity in Randomness Extraction. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2009.2320, author = {Hitchcock, John M. and Pavan, Aduri and Vinodchandran, N. V.}, title = {{Kolmogorov Complexity in Randomness Extraction}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {215--226}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2320}, URN = {urn:nbn:de:0030-drops-23201}, doi = {10.4230/LIPIcs.FSTTCS.2009.2320}, annote = {Keywords: Extractors, Kolmogorov extractors, randomness} }