BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1117
DTSTAMP:20230914T125951Z
SUMMARY:Element distinctness using arbitrary binary gates
DESCRIPTION:Speaker: Siddharth Bhandari\n\nAbstract: \nWe will study the De
 cision-Tree complexity of element distinctness using arbitrary binary gate
 s (an instance of which is comparison gates). Concretely\, let $m$ and $n$
  be natural numbers with $m>n$. Suppose\, we are given an array $A[1]\,A[2
 ]\,\\ldots\,A[n]$ where each $A[i]\\in [m]$. At each step we are allowed t
 o pick two indices $i$ and $j$ in $[n]$ and an arbitrary function $f:\\N \
 \times \\N \\to \\{0\,1\\}$\, and ask for the value of $f(A[i]\,A[j])$. At
  the end of the procedure we must be able to tell whether all the entries 
 of $A$ were distinct or not. Define by $S(m\,n)$ the minimum number of ste
 ps needed in such a procedure. We are interested in understanding the asym
 ptotics of $S(m\,n)$.\nIn the specific case when we are restricted to use 
 only comparison gates\, i.e.\, $f(a\,b)=[a>b]$ we will see that $S(m\,n)=\
 \Theta(n \\log n)$ for all $m\\geq n$.\nIn the more general setting where 
 we are allowed to use arbitrary gates\, we will see that when $m>>n$ then 
 $S(m\,n)=\\Theta(n \\log n)$. However\, when $m=n$ our understanding is in
 complete: $S(m\,n)=\\Omega(n \\sqrt(\\log n))$. (This is a result of Ravi 
 Boppana https://www.sciencedirect.com/science/article/pii/0020019094001545
 ?via%3Dihub). If time permits we might discuss a few ideas to bridge this 
 gap.\nZoom link:\nhttps://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0
 ZHcEt0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1117
DTSTART;TZID=Asia/Kolkata:20210212T171500
DTEND;TZID=Asia/Kolkata:20210212T181500
END:VEVENT
END:VCALENDAR