2 Search Results for "Ďuriš, Pavol"


Document
Randomization in Non-Uniform Finite Automata

Authors: Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.

Cite as

Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith. Randomization in Non-Uniform Finite Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 30:1-30:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{duris_et_al:LIPIcs.MFCS.2020.30,
  author =	{\v{D}uri\v{s}, Pavol and Kr\'{a}lovi\v{c}, Rastislav and Kr\'{a}lovi\v{c}, Richard and Pardubsk\'{a}, Dana and Pa\v{s}en, Martin and Rossmanith, Peter},
  title =	{{Randomization in Non-Uniform Finite Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.30},
  URN =		{urn:nbn:de:0030-drops-126987},
  doi =		{10.4230/LIPIcs.MFCS.2020.30},
  annote =	{Keywords: finite automata, non-uniform computation, randomization}
}
Document
Tribes Is Hard in the Message Passing Model

Authors: Arkadev Chattopadhyay and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each n-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear. In this work, we prove a tight lower bound of \Omega(kn) on the communication needed for computing the Tribes function, when the underlying graph is a star of k+1 nodes that has k leaves with inputs and a center with no input. A lower bound on this topology easily implies comparable bounds for others. Our lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et al. ([4], FOCS'13) and combining it with the earlier work of Jayram, Kumar and Sivakumar ([10], STOC'03). This approach yields information complexity bounds that are of independent interest.

Cite as

Arkadev Chattopadhyay and Sagnik Mukhopadhyay. Tribes Is Hard in the Message Passing Model. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 224-237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.STACS.2015.224,
  author =	{Chattopadhyay, Arkadev and Mukhopadhyay, Sagnik},
  title =	{{Tribes Is Hard in the Message Passing Model}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{224--237},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.224},
  URN =		{urn:nbn:de:0030-drops-49162},
  doi =		{10.4230/LIPIcs.STACS.2015.224},
  annote =	{Keywords: communication complexity, Tribes, information complexity, direct-sum}
}
  • Refine by Author
  • 1 Chattopadhyay, Arkadev
  • 1 Královič, Rastislav
  • 1 Královič, Richard
  • 1 Mukhopadhyay, Sagnik
  • 1 Pardubská, Dana
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Automata extensions

  • Refine by Keyword
  • 1 Tribes
  • 1 communication complexity
  • 1 direct-sum
  • 1 finite automata
  • 1 information complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2020

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