ECCC-Report TR24-034https://eccc.weizmann.ac.il/report/2024/034Comments and Revisions published for TR24-034en-usSun, 25 Feb 2024 07:27:39 +0200
Paper TR24-034
| The hardness of decision tree complexity |
Bruno Loff,
Alexey Milovanov
https://eccc.weizmann.ac.il/report/2024/034Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is tight, and the first bound is close to being tight.
Sun, 25 Feb 2024 07:27:39 +0200https://eccc.weizmann.ac.il/report/2024/034