BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/712
DTSTAMP:20230914T125935Z
SUMMARY:Complexity of Elimination
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nOne of the basic q
 uestions in complexity theory is how the complexity of computing $k$ insta
 nces of a function relates to the complexity of computing a single instanc
 e. More precisely\, we want to know whether we can save any computation by
  solving $k$ instances together instead of solving each instance individua
 lly. In literature jargon\, this question has a name: the direct-sum probl
 em.\n\nWe will consider an easier version of this problem\, called the eli
 mination problem\, in communication setting. Consider a bipartite boolean 
 function: $f: \\mathcal{X} \\times \\mathcal{Y} \\rightarrow \\mathcal{R}$
  where Alice gets $X \\in \\mathcal{X}$ and Bob gets $Y \\in \\mathcal{Y}$
  and jointly they compute the function $f(X\,Y)$ by communicating with eac
 h other. In the elimination problem\, Alice gets $X_1. \\dots\, X_k \\in \
 \mathcal{X}^k$ and Bob gets $Y_1\, \\dots\, Y_k \\in \\mathcal{Y}^k$ and t
 heir goal is to output a string $\\sigma_1\, \\dots\, \\sigma_k$ such that
  $f(X_i\, Y_i) \\neq \\sigma_i$ for at least one $i \\in [k]$. Clearly thi
 s is an easier scenario than the &#39\;direct-sum&#39\; problem:\n\nConsid
 er the case where $f$ is the EQUALITY function\, $X_1 = \\dots = X_k$ and 
 $Y_1 = \\dots = Y_k$. To solve direct-sum one needs to solve at least one 
 instance of $f$ whereas for elimination\, no communication is necessary un
 der the said promise.\n\nWe will prove an upper and a lower bound of the r
 andomized communication complexity of the elimination problem.\n\nRef:  B
 eimel\, Amos and Daniel\, Sebastian Ben and Kushilevitz\, Eyal and Weinreb
 \, Enav:\nChoosing\, Agreeing\, and Eliminating in Communication Complexit
 y.\n \n
URL:https://www.tcs.tifr.res.in/web/events/712
DTSTART;TZID=Asia/Kolkata:20160916T160000
DTEND;TZID=Asia/Kolkata:20160916T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR