Please note: This PhD seminar will take place in DC 1304 and online.
Avantika Agarwal, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Shalev Ben-David, Eric Blais
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure:
Information equals amortized size complexity: We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function.
Information allows for tree size compression: We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability.
Direct Product Theorems: We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).
This talk is based on joint work with Shalev Ben-David and Eric Blais.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.