Abstract: 

Let f:{0,1}^n -> {0,1} be a Boolean function. We will discuss the connection between various notions of complexity associated with f: its sensitivity, block sensitivity, degree, approximate degree, and decision tree depth. We will present the recent breakthrough of Hao Huang (2019) who showed that  if f cannot be represented by a polynomial of low degree then it must be highly sensitive.  Finally, we will show a new upper bound on the size of the deterministic decision tree computing f in terms of the size of  the corresponding randomized decision tree. The last result is from a recent joint work with Arkadev Chattopadhyay, Yogesh Dahia, Nikhil Mande and Swagato Sanyal. The talk will be accessible to a general scientific audience; we will assume nothing beyond basic linear algebra and combinatorics. 

About the Speaker:

Jaikumar Radhakrishnan is a theoretical computer scientist with research interests in complexity theory, randomness and computation, quantum information and computation, combinatorics, and information theory. Radhakrishnan obtained his BTech in Computer Science and Engineering from IIT Kharagpur in 1991, and his PhD in Computer Science from Rutgers University, NJ, USA, in 1991.  He joined the Tata Institute of Fundamental Research in 1991, where is currently a senior professor at the School of Technology and Computer Science (STCS), TIFR, Mumbai, and at the International Centre for Theoretical Sciences (ICTS-TIFR), Bengaluru.