[Proof Complexity] MIAO seminar Wed Oct 25 at 14:00 with Yogesh Dahiya: Randomness gives little advantage for decision tree size

[Jakob Nordström]

Dear all,

Again with apologies for the somewhat short notice, we are happy to announce that on Wednesday October 25 at 14:00 we will have the opportunity to enjoy a seminar with Yogesh Dahiya from the Institute of Mathematical Sciences, Chennai, who will give a talk titled "Randomness gives little advantage for decision tree size". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to room N116B at Universitetsparken 1. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can usually be found with somewhat better forward notice at http://www.jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Wednesday Oct 25 at 14:00 in seminar room N116B, Universitetsparken 1, University of Copenhagen, and on Zoom
Randomness gives little advantage for decision tree size
(Yogesh Dahiya, Institute of Mathematical Sciences, Chennai)

Nisan's classic result [SICOMP '91] shows that the deterministic decision tree depth complexity of a total Boolean function is at most the cube of its randomized decision tree depth complexity. However, the role of randomness on decision tree size complexity has not been explored. Adding to Nisan's result, we show that the logarithm of the deterministic decision tree size complexity of any total Boolean function is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, up to a polylogarithmic factor in the input dimension. Drawing an analogy, one can associate the depth of a decision tree with time complexity and its size with space complexity. Consequently, Nisan's result can be viewed as derandomizing time, while our result can be seen as derandomizing space.

Our result has several implications for derandomizing query complexity in more generalized variants of decision trees. Specifically, we show that for total Boolean functions:
- The deterministic AND-OR query complexity is at most the fourth power of its randomized counterpart, ignoring a polylog n factor.
- The deterministic AND (OR) query complexity is at most the cube of its randomized counterpart, ignoring a polylog n factor. This resolves an open question by Knop, Lovett, McGuire, and Yuan [SIGACT News '21].

Combining our result with Ehrenfeucht and Haussler's [Information and Computation'89] work, we also get that the class of functions computable by randomized decision trees of polynomial size is PAC-learnable in quasi-polynomial time.

To obtain our main result on decision tree size, we use as an intermediate measure the block number of a Boolean function, studied first by Midrijanis [Arxiv’05], which can be thought of as a counting analogue of block sensitivity of a Boolean function that played a central role in Nisan's aforementioned result.

This is joint work with Arkadev Chattopadhyay, Nikhil Mande, Jaikumar Radhakrishnan, and Swagato Sanyal that appeared in STOC 2023.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se