04 Oct Talk: Communication Complexity and Big Data - An Introduction

[Vinayak]

Dear all,

Kindly find the details of the following talk to be held on Friday, 4th October 2019.

Speaker: Siddhartha Jain

Title: Communication Complexity and Big Data - An Introduction

Abstract: Communication Complexity is a relatively new but very successful field of Complexity Theory. Streaming/Sketching algorithms are also a recent focus of interest to deal with problems involving Big Data - where the input is so large we cannot hope to store it in working memory. This talk will introduce both these fields. But we will then focus on how they relate to each other! Lower bounds in communication complexity help us prove lower bounds for Streaming algorithms, and we will see an example of this by proving that F_{\infty} has a linear lower bound by reducing it to Disjointness. F_{\infty} is a problem in the Frequency Moment Estimation family, an important topic in Streaming.

Venue: A006

Time: 1:30 - 2:30 pm, 04 October 2019

PS: In addition, a talk on "Beating Sorting Lower Bounds" by Agastya Jha will be held tomorrow at A006 from 1:30 - 2:30 pm.  

Calendar link to the event(s): http://bit.ly/EvaristeCal  

--

Regards,

Vinayak

Coordinator | Évariste

B.Tech CSE, 3rd Year | IIIT-Delhi