Speaker: |
Siddharth Bhandari |

Date: |
Friday, 12 Feb 2021, 17:15 to 18:15 |

Venue: |

(Scan to add to calendar)

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