Some Basic Linear Algebraic Techniques for Proving Lower Bounds


Tulsi Mohan Molli


School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Navy Nagar
Mumbai 400005


Friday, 8 August 2014, 14:30 to 16:00


  • D-405 (D-Block Seminar Room)


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.