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