Tata Institute of Fundamental Research
Element distinctness using arbitrary binary gates
STCS Student Seminar
Speaker:
Siddharth Bhandari
Date:
Friday, 12 Feb 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
We will study the Decision-Tree complexity of element distinctness using arbitrary binary gates (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 to 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 steps needed in such a procedure. We are interested in understanding the asymptotics of $S(m,n)$.
In 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$.
In 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 incomplete: $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.
Zoom link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Siddharth Bhandari |
| Date: | Friday, 12 Feb 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
We will study the Decision-Tree complexity of element distinctness using arbitrary binary gates (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 to 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 steps needed in such a procedure. We are interested in understanding the asymptotics of $S(m,n)$.
In 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$.
In 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 incomplete: $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.
Zoom link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
In 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$.
In 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 incomplete: $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.
Zoom link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09