Some Basic Linear Algebraic Techniques for Proving Lower Bounds

by Mr Tulsi Mohan Molli (School of Technology and Computer Science, TIFR)

Friday 8 Aug 2014, 14:30 → 16:00 Asia/Kolkata

D-405 (D-Block Seminar Room) (Colaba Campus)

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.