Contact Us

Give us a call or drop by anytime, we endeavor to answer all inquiries within 24 hours.


Find us

PO Box 16122 Collins Street West Victoria, Australia

Email us /

Phone support

Phone: + (066) 0760 0260 / + (057) 0760 0560

Loading Events

« All Events

  • This event has passed.

Toniann Pitassi: A Survey of Recent Progress in Lower Bounds

January 1, 1970 @ 12:00 am

Abstract: Ever since Yao introduced the communication model in 1979, it has played a pivotal role in our understanding of lower bounds for a wide variety of problems in Computer Science. In this talk, I will present the lifting method, whereby communication lower bounds are obtained by “lifting” much simpler lower bounds. I will present several lifting theorems that we have obtained and explain what makes the exciting/useful but also difficult to prove. Finally I will highlight how they have been used to solve several open problems in circuit complexity, proof complexity, optimization, cryptography, game theory and privacy.Short Bio: Toniann Pitassi is a professor and Bell Canada Chair in Information Systems at the University of Toronto. She also holds a five-year visiting professorship at the Institute for Advanced Study. She earned her bachelor’s and master’s degrees from Penn State and her PhD from the University of Toronto. She has held previous positions at UC San Diego, University of Pittsburgh, and University of Arizona. Pitassi was an invited speaker at the International Congress of Mathematicians and was recently elected as an ACM fellow. Her primary research is in computational complexity, proof complexity, privacy and fairness.


January 1, 1970
12:00 am