BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Communication Lower Bounds from Query Complexity
DTSTART:20190313T101500
DTEND:20190313T111500
DTSTAMP:20260407T105743Z
UID:a9e9b26e89f1184c7f355ee09ec7ea88416b0fdb217fab3760683403
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Mika Göös - IAS School of Mathematics\nIC Faculty candid
 ate\n\nAbstract:\nIn the basic model of communication complexity (Yao\, 19
 79)\, Alice holds x\, Bob holds y\, and their goal is to compute a given f
 unction F(x\,y) by communicating as few bits as possible. What elevates th
 is model beyond its immediate appearances (communication networks\, distri
 buted systems) are several surprising connections to other seemingly unrel
 ated areas of theoretical computer science and mathematics. I will discuss
  my PhD work in this area\, with applications to circuit complexity\, proo
 f complexity\, combinatorial optimisation (size of linear programming form
 ulations)\, and graph theory (Alon-Saks-Seymour conjecture). A central the
 me in my research has been the introduction and application of several new
  Big Hammers\, so-called "query-to-communication lifting" theorems. These 
 new techniques have allowed me and my coauthors to resolve several fundame
 ntal open problems in communication complexity\, some dating back to Yao
 ’s original 1979 paper that started the field.\n\nBio:\nMika Goos is a p
 ostdoctoral member at IAS. Prior to IAS he was the Michael O. Rabin postdo
 ctoral fellow at Harvard. He obtained his PhD from the University of Toron
 to (2016) under the supervision of Toniann Pitassi. He also holds an MSc f
 rom the University of Oxford (2011) and a BSc from Aalto University (2010)
 . His research interests revolve around computational complexity theory.\n
 \nMore information
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR