Colloquium Schedule         Guidelines         Directions        

Colloquium
Thursday, March 19, 2015


Quantum Proofs for Classical Theorems

Ronald de Wolf (CWI)


Abstract: Alongside the development of quantum computing, in recent years quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. Just like some results about real functions are most easily proved via complex numbers, and many results in combinatorics are most easily proved using the "probabilistic method", this development uses the mathematical framework provided by quantum information theory to analyze classical questions. Of course, no physical quantum computer need ever be built for this application! In this talk I will survey this use of quantum information techniques as a proof tool, with a focus on two specific applications: lower bounds on certain error-correcting codes, and on the size of linear programs for hard optimization problems such as Traveling Salesman. The talk is partially based on this survey paper by Andrew Drucker and myself: http://theoryofcomputing.org/articles/gs002/gs002.pdf

<<< previous talk
next talk >>>



Location :  Room 611 of the Hans Freudenthal building, formerly known as the Wiskunde/Maths building, (campus De Uithof) Budapestlaan 6, Utrecht.
Date and time : Thursday, March 19, 2015 15:30-16:30. The lecture is preceded by coffee, tea, and cookies from 15.00 to 15.30 hour in the same room.