Tata Institute of Fundamental Research
Some Basic Linear Algebraic Techniques for Proving Lower Bounds
Student Seminar
Speaker:
Tulsi Mohan Molli (School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Navy Nagar
Mumbai 400005)
Organiser:
Nikhil S Mande
Date:
Friday, 8 Aug 2014, 14:30 to 16:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: In this talk I will discuss some linear algebraic methods to prove lower bounds. In particular I will discuss Graham Pollak theorem, a graph theoretic result which gives us a lower bound on the number of bipartite cliques needed to cover a complete graph. Also, I will talk about Razbarov's result that threshold functions cannot be approximated by small degree polynomials and may be more if time permits.
| Speaker: | Tulsi Mohan Molli (School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Navy Nagar Mumbai 400005) |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 8 Aug 2014, 14:30 to 16:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: In this talk I will discuss some linear algebraic methods to prove lower bounds. In particular I will discuss Graham Pollak theorem, a graph theoretic result which gives us a lower bound on the number of bipartite cliques needed to cover a complete graph. Also, I will talk about Razbarov's result that threshold functions cannot be approximated by small degree polynomials and may be more if time permits.