BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Two Facets of Complexity Theory
DTSTART:20220510T140000
DTEND:20220510T160000
DTSTAMP:20260407T111322Z
UID:1b5508c9550f072002c324ffa1cc246fed7139dea7753dc11561dd87
CATEGORIES:Conferences - Seminars
DESCRIPTION:Ziyi Guan\nEDIC candidacy exam\nExam president: Prof. Ola Sven
 sson\nThesis advisor: Prof. Mika Göös\nThesis co-advisor: Prof. Alessand
 ro Chiesa\nCo-examiner: Prof. Michael Kapralov\n\nAbstract\nProbabilistic 
 proofs and communication complexity are two important subfields in computa
 tional complexity. This writeup contains the summaries of three papers tha
 t 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 sys
 tems construction. The second one gives an information-theoretic method to
  prove lower bounds in communication complexity\, while the last one assoc
 iates communication complexity with Lov\\'{a}sz's fractional covers. Moreo
 ver\, 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 a
 re discussed in the end of this writeup.\n\nBackground papers\n1. Algebrai
 c methods for interactive proof systems: https://dl.acm.org/doi/10.1145/1
 46585.146605\n2. An information statistics approach to data stream and com
 munication complexity: http://people.seas.harvard.edu/~madhusudan/courses
 /Spring2016/papers/BJKS.pdf\n3. Fractional covers and communication comple
 xity https://epubs.siam.org/doi/10.1137/S0895480192238482\n 
LOCATION:BC 02 https://plan.epfl.ch/?room==BC%2002
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR