DROPS

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 Õ(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.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}
}

Search Results

Documents authored by Maharjan, Ramita

Complexity of Fault Tolerant Query Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message