Computational Complexity
Event details
| Date | 11.07.2023 |
| Hour | 14:00 › 16:00 |
| Speaker | Anastasiia Sofronova |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
Communication complexity and proof complexity are both important parts of computational complexity theory. Often, the lower bounds in these areas translate to, for example, circuit complexity or back, and the methods and techniques find their use in the adjacent areas.
In this write-up, we discuss several techniques and approaches to proving the lower bounds in both communication complexity and proof complexity.
Based on the existing works, we explore several matrix measures and how they imply lower and upper bounds in communication complexity. We discuss also how these methods relate with the new rapidly developing area of constant cost communication complexity, which has strong connection with a number of algebraic and geometric problems. The papers that we discuss use discrete analysis methods (for example, Fourier analysis) for establishing lower and upper bounds.
Proof complexity studies the length of shortest proofs of unsatisfiable formulas. Our main interest here are lower bounds that do not reduce to the use of random restriction technique. We discuss one of the existing lower bounds that falls under this category. It uses probabilistic method in combinatorics as well as some algebraic methods.
We give a research proposal with the open problems related to those works.
Background papers
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
Communication complexity and proof complexity are both important parts of computational complexity theory. Often, the lower bounds in these areas translate to, for example, circuit complexity or back, and the methods and techniques find their use in the adjacent areas.
In this write-up, we discuss several techniques and approaches to proving the lower bounds in both communication complexity and proof complexity.
Based on the existing works, we explore several matrix measures and how they imply lower and upper bounds in communication complexity. We discuss also how these methods relate with the new rapidly developing area of constant cost communication complexity, which has strong connection with a number of algebraic and geometric problems. The papers that we discuss use discrete analysis methods (for example, Fourier analysis) for establishing lower and upper bounds.
Proof complexity studies the length of shortest proofs of unsatisfiable formulas. Our main interest here are lower bounds that do not reduce to the use of random restriction technique. We discuss one of the existing lower bounds that falls under this category. It uses probabilistic method in combinatorics as well as some algebraic methods.
We give a research proposal with the open problems related to those works.
Background papers
- Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitation (https://drops.dagstuhl.de/opus/volltexte/2022/17144/pdf/LIPIcs-APPROX22.pdf)
- Kaave Hosseini, Hamed Hatami, and Shachar Lovett. Sign-rank vs. discrepancy (https://drops.dagstuhl.de/opus/volltexte/2020/12570/pdf/LIPIcs-CCC-2020-18.pdf)
- Alexander A. Razborov. Resolution lower bounds for the weak functional pigeonhole principle (https://eccc.weizmann.ac.il/report/2001/075/)
Practical information
- General public
- Free