School of Technology and Computer Science Seminars

Some Basic Linear Algebraic Techniques for Proving Lower Bounds

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

Friday, August 8, 2014 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
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.