School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
- 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.