9 Search Results for "Pavan, A."

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.37
Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations

Authors: Michael Chen, A. Pavan, and N. V. Vinodchandran

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

Abstract
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^{Σ₂^{𝖯}}.
Cite as

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-dev.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
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-dev.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-dev.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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2015.236
On the NP-Completeness of the Minimum Circuit Size Problem

Authors: John M. Hitchcock and A. Pavan

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2014.445
Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis

Authors: Debasis Mandal, A. Pavan, and Rajeswari Venugopalan

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2014.585
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs

Authors: Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin Forrest Yang

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.STACS.2010.2462
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Authors: Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2009.2320
Kolmogorov Complexity in Randomness Extraction

Authors: John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran

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

Abstract
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$.
Cite as

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-dev.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}
}
  • Refine by Author
  • 7 Pavan, A.
  • 6 Vinodchandran, N. V.
  • 3 Dixon, Peter
  • 3 Hitchcock, John M.
  • 2 Mandal, Debasis
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Probabilistic computation
  • 1 Computing methodologies → Massively parallel algorithms
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 3 NP-completeness
  • 2 Pseudodeterminism
  • 1 AMPC
  • 1 Approximation Algorithms
  • 1 BBRS Bound
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2014
  • 1 2009
  • 1 2010
  • 1 2015
  • 1 2016
  • Show More...

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