2026-07-25T02:44:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17418 2024-03-06T10:59:42Z ddc:004 open_access

Complexity of Fault Tolerant Query Complexity Maharjan, Ramita Watson, Thomas Fault Tolerant Query Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ramita Maharjan and Thomas Watson 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.26 urn:nbn:de:0030-drops-174185 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.26 eng https://creativecommons.org/licenses/by/4.0/legalcode