15 Mar Talk: Razborov-Smolensky method and a standard application

[Vinayak]

Dear all,

This is to inform everyone that I, Vinayak, have taken over the responsibility of organizing Theory talks from Siddhartha Jain.

Please find the details of the semester's first T-Talk to be held this Friday (15 March 2019).

Speaker: Siddhartha Jain

Title: Razborov-Smolensky method and a standard application

Abstract: The Razborov-Smolensky trick is a celebrated result in Complexity theory. It essentially gives us a way to approximate circuits using low degree polynomials. Although appreciating its implications requires background, the method itself is quite accessible to anyone who's comfortable with a little bit of probability and polynomial algebra.

In this talk we will work our way through a popular application of the method, proving that PARITY \not\in AC_0. All the mentioned terms will be defined in the talk. 2nd-year and motivated 1st-year students are encouraged to come.

Venue: C03

Time: 1:30 pm - 2:30 pm, 15 March 2019

PS: From this semester onwards, talks will be conducted either on Thursday or Friday during lunchtime. The flexibility of the schedule ensures that everyone is accommodated.

--

Regards,

Vinayak

Coordinator | Évariste

B.Tech CSE, 2nd Year | IIIT-Delhi