Complexity of Fault Tolerant Query Complexity
| Autor: | Maharjan, Ramita, Watson, Thomas |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.4230/lipics.fsttcs.2022.26 |
| Popis: | 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. LIPIcs, Vol. 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), pages 26:1-26:11 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|