IMSc Webinar

XOR functions, log-rank conjecture and parity decision trees.

Swagato Sanyal

IIT Kharagpur

Webinar: join at https://zoom.us/j/99691787859?pwd=UGpqYWphK1o2OHhkYXV4QTFhYjNIdz09 The log-rank conjecture in communication complexity states that the deterministic communication complexity of any 0/1-valued function on the Boolean hypercube is asymptotically bounded above by a fixed polynomial of the logarithm (over real numbers) of its communication matrix. The motivation of this conjecture stems from the fundamental enquiry as to whether an interactive complexity measure can be characterized (upto a polynomial dependence) by an algebraic measure. In this talk we will consider this conjecture for a special class of functions called the XOR functions. In this case, in light of existing works, the log-rank conjecture is equivalent to some structural questions about the Fourier spectra of Boolean functions. In this talk, I will survey these connections, with a focus on a recent joint work with Nikhil Mande (FSTTCS 2020; url:https://drops.dagstuhl.de/opus/volltexte/2020/13270/pdf/LIPIcs-FSTTCS-2020-29.pdf). The talk is meant for a general theoretical computer science audience.