BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium :  "On the communication complexity of sparse set di
 sjointness and exists-equal problems"
DTSTART:20131014T161500
DTEND:20131014T173000
DTSTAMP:20260510T135113Z
UID:48dd4c91b524d703b7a7c562d63e2b9fefd56d852655e0ada285f564
CATEGORIES:Conferences - Seminars
DESCRIPTION:Gabor Tardos \nAbstract:\nIn communication complexity one conc
 entrates on a single aspect of computation and asks how long messages need
  to be exchanged and in how many rounds between two parties (traditionally
  Alice and Bob) if they want to evaluate a function that depends on both o
 f their inputs. This lead to a very clean model and allowed us to better u
 nderstand certain aspects of complexity\, including proving meaningful low
 er bounds for certain problems that are famously lacking for more standard
  computational models. Among the many applications are those for streaming
  algorithms\, a widely studied topic in complexity.\nProbably the two most
  studied problem in communication complexity are the equality and set disj
 ointness problems. In the former problem Alice and Bob have to decide if t
 heir inputs are equal\, in the latter they receive subsets of a common gro
 und set and they have to decide if their subsets are disjoint. The complex
 ity of these problems are well established and (in the randomized model) v
 ery different.\nIn this talk I concentrate on variants of these problems: 
 The sparse set disjointness problem Alice and Bob receive SMALL subsets of
  a large ground set and they still have to figure out if their sets are di
 sjoint. For this problem\, we give a protocol that communicates a total of
  O(k log(r) k) bits over r\nrounds and errs with very small probability. H
 ere k is the size of the input sets and log(r) is the r-times-iterated-log
  function. This is optimal for any value of r. We can take r = log∗ k to
  obtain a O(k) total communication log∗ k-round protocol with exponentia
 lly small error probability\, improving on the O(k)-bits O(log k)-round co
 nstant error probability protocol of Hastad and Wigderson from 1997. A sma
 ll variation of our protocol even finds the intersection of the input sets
 .\nThe exist-equal problem is the OR of several independent equality probl
 ems. Our lower bound on the constant round protocols for exists-equal show
  that\nsolving the OR of n instances of the equality problem requires stri
 ctly more than n times the cost of a single instance. To our knowledge thi
 s is the first example of such a super-linear increase in complexity.\nThe
  results are joint with Mert Sağlam and will appear in the coming FOCS.Bi
 ography:\nGábor Tardos is a Hungarian mathematician\, currently a profess
 or and Canada Research Chair at Simon Fraser University. He works mainly i
 n combinatorics and computer science with beautiful results on fingerprint
  codes\, constructive lovasz local lemma\, communication complexity\, and 
 online algorithms. He received the European Mathematical Society prize for
  young researchers at the European Congress of Mathematics in 1992 and the
  Erdős Prize from the Hungarian Academy of Sciences in 2000. He received 
 a Lendület Grant from the Hungarian Academy of Sciences (2009) specifical
 ly devised to keep outstanding researchers in Hungary.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR