BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Computational Complexity
DTSTART:20230711T140000
DTEND:20230711T160000
DTSTAMP:20260410T152244Z
UID:4ff6158a69b4e348ecba4d637955fb32ce4c67937ab1f6ac80ff263a
CATEGORIES:Conferences - Seminars
DESCRIPTION:Anastasiia Sofronova\nEDIC candidacy exam\nExam president: Pro
 f. Ola Svensson\nThesis advisor: Prof. Mika Göös\nCo-examiner: Prof. Mic
 hael Kapralov\n\nAbstract\nCommunication complexity and proof complexity a
 re both important parts of computational complexity theory. Often\, the lo
 wer bounds in these areas translate to\, for example\, circuit complexity 
 or back\, and the methods and techniques find their use in the adjacent ar
 eas.\n\nIn this write-up\, we discuss several techniques and approaches to
  proving the lower bounds in both communication complexity and proof compl
 exity.\n\nBased 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 are
 a of constant cost communication complexity\, which has strong connection 
 with a number of algebraic and geometric problems. The papers that we disc
 uss use discrete analysis methods (for example\, Fourier analysis) for est
 ablishing lower and upper bounds.\n\nProof complexity studies the length o
 f shortest proofs of unsatisfiable formulas. Our main interest here are lo
 wer 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.\n\nWe give a research proposal with the open problems related to 
 those works.\n\nBackground papers\n\n	Hamed Hatami\, Pooya Hatami\, Willia
 m 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)\n	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)\n	Alexander A. Razborov. Resolution lowe
 r bounds for the weak functional pigeonhole principle (https://eccc.weizma
 nn.ac.il/report/2001/075/)\n
LOCATION:BC 129 https://plan.epfl.ch/?room==BC%20129
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR