Two Facets of Complexity Theory
Event details
| Date | 10.05.2022 |
| Hour | 14:00 › 16:00 |
| Speaker | Ziyi Guan |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Thesis co-advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Michael Kapralov
Abstract
Probabilistic proofs and communication complexity are two important subfields in computational complexity. This writeup contains the summaries of three papers that are considered fundamental and classical in these two fields. The first paper introduces an interactive proof system for matrix permanent, which sets the foundation of arithmetization techniques widely used in proof systems construction. The second one gives an information-theoretic method to prove lower bounds in communication complexity, while the last one associates communication complexity with Lov\'{a}sz's fractional covers. Moreover, the goal to overcome the barrier in field size, which is introduced by the use of Schwartz-Zippel lemma in soundness error calculation, and to use techniques in communication complexity in other complexity models are discussed in the end of this writeup.
Background papers
1. Algebraic methods for interactive proof systems: https://dl.acm.org/doi/10.1145/146585.146605
2. An information statistics approach to data stream and communication complexity: http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf
3. Fractional covers and communication complexity https://epubs.siam.org/doi/10.1137/S0895480192238482
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Thesis co-advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Michael Kapralov
Abstract
Probabilistic proofs and communication complexity are two important subfields in computational complexity. This writeup contains the summaries of three papers that are considered fundamental and classical in these two fields. The first paper introduces an interactive proof system for matrix permanent, which sets the foundation of arithmetization techniques widely used in proof systems construction. The second one gives an information-theoretic method to prove lower bounds in communication complexity, while the last one associates communication complexity with Lov\'{a}sz's fractional covers. Moreover, the goal to overcome the barrier in field size, which is introduced by the use of Schwartz-Zippel lemma in soundness error calculation, and to use techniques in communication complexity in other complexity models are discussed in the end of this writeup.
Background papers
1. Algebraic methods for interactive proof systems: https://dl.acm.org/doi/10.1145/146585.146605
2. An information statistics approach to data stream and communication complexity: http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf
3. Fractional covers and communication complexity https://epubs.siam.org/doi/10.1137/S0895480192238482
Practical information
- General public
- Free