Progress in Lifting and Applications in Lower Bounds (Invited Talk)

Pitassi, Toniann

doi:10.4230/LIPIcs.FSTTCS.2019.4

Document

Progress in Lifting and Applications in Lower Bounds (Invited Talk)

Author Toniann Pitassi

Part of: Volume: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2019-12-04

PDF

File

PDF

LIPIcs.FSTTCS.2019.4.pdf

Filesize: 156 kB
1 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2019.4
URN: urn:nbn:de:0030-drops-115664

Subject Classification

ACM Subject Classification

Theory of computation → Communication complexity

Keywords

complexity theory
lower bounds
communication complexity

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

Ever since Yao introduced the communication complexity model in 1979, it has played a pivotal role in our understanding of limitations 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 show how lifting theorems have been used to solve many open problems in a variety of areas of computer science, including: circuit complexity, proof complexity, combinatorial optimization (size of linear programming formulations), cryptography (linear secret sharing schemes), game theory and privacy.
At the end of the talk, I will sketch the proof of a unified lifting theorem for deterministic and randomized communication (joint with Arkadev Chattopadyhay, Yuval Filmus, Sajin Koroth, and Or Meir.)

Cite As Get BibTex

Toniann Pitassi. Progress in Lifting and Applications in Lower Bounds (Invited Talk). In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.4

Author Details

Toniann Pitassi

University of Toronto, Canada
Institute for Advanced Study, Princeton, NJ, USA

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail