Computational Complexity

Thumbnail

Event details

Date 11.07.2023
Hour 14:0016: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

Practical information

  • General public
  • Free

Tags

EDIC candidacy exam

Share