Complexity Workshop 2020

Sensitivity, Query Complexity, Communication Complexity and Fourier Analysis of Boolean Function

10:00-10:15 Introductory talk
10:15-11:15 Talk by Yuval Filmus on AND testing
11:45-12:45 Talk by Nitin Saurabh on Improved upper bounds on Fourier entropy (Slides)
12:45-14:30 Lunch
14:30-15:30 Talk by Prahladh Harsha High Dimensional Expanders: Introduction and some recent applications (Slides)
16:00-17:00 Talk by Anupa Sunny Sensitivity lower bounds from linear dependencies (Slides)

10:00-11:00 Talk by Rajat Mittal Exact degree of a symmetric Boolean function (Slides)
11:30-12:30 Talk by Arkadev Chattopadyay Equality Alone Does Not Simulate Randomness (Slides)
12:30-13:00 Photo and trip to geology museum
13:00-14:30 Lunch
14:30-15:30 Talk by Rahul Jain Partition Bound Is Quadratically Tight for Product Distributions (Picture of Board: Pic1 , Pic2 , Pic3 )
16:00-17:00 Talk by Suhail Sherif Refuting the Log-Approximate-Rank Conjecture (Slides)
17:00-18:00 Talk by Manaswi Paraashar Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead (Slides)

10:00-11:00 Talk by Amey Bhangale Hardness of approximating hypergraph coloring
11:30-12:30 Talk by Diptarka Chakraborty Hardness of Approximation of (Multi-)LCS over Small Alphabet (Slides)
12:30-13:30 Talk by Arnab Bhattacharyya New approaches for proving lower bounds on the length of locally decodable codes (Picture of Board: Pic1 , Pic2 , Pic3 , Pic4 , Pic5 , Pic6 , Pic7 )
13:30-15:30 Lunch
15:30-16:30 Talk by Swagato Sanyal On decision tree complexity of Boolean functions (Slides)
16:30-16:45 Concluding Remarks