1 Search Results for "Maharjan, Ramita"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.26
Complexity of Fault Tolerant Query Complexity

Authors: Ramita Maharjan and Thomas Watson

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
In the model of fault tolerant decision trees introduced by Kenyon and Yao, there is a known upper bound E on the total number of queries that may be faulty (i.e., get the wrong bit). We consider this computational problem: Given as input the truth table of a function f: {0,1}ⁿ → {0,1} and a value of E, find the minimum possible height (worst-case number of queries) of any decision tree that computes f while tolerating up to E many faults. We design an algorithm for this problem that runs in time Õ(binom(n+E,E)⋅(2E+3)ⁿ), which is polynomial in the size of the truth table when E is a constant. This generalizes a standard algorithm for the non-fault tolerant setting.
Cite as

Ramita Maharjan and Thomas Watson. Complexity of Fault Tolerant Query Complexity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maharjan_et_al:LIPIcs.FSTTCS.2022.26,
  author =	{Maharjan, Ramita and Watson, Thomas},
  title =	{{Complexity of Fault Tolerant Query Complexity}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-174185},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.26},
  annote =	{Keywords: Fault, Tolerant, Query, Complexity}
}
  • Refine by Author
  • 1 Maharjan, Ramita
  • 1 Watson, Thomas

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Complexity
  • 1 Fault
  • 1 Query
  • 1 Tolerant

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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