Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-034 | 19th February 2024 00:49

The hardness of decision tree complexity

RSS-Feed




TR24-034
Authors: Bruno Loff, Alexey Milovanov
Publication: 25th February 2024 07:27
Downloads: 117
Keywords: 


Abstract:

Let $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.



ISSN 1433-8092 | Imprint