Making a Trifference

Speaker:

Siddharth Bhandari

Organiser:

Raghuvansh Saxena

Date:

Monday, 26 Aug 2024, 10:00 to 11:00

Venue:

A-201 (STCS Seminar Room)

Category:

STCS Seminar

event.ics Print

Abstract

A subset C⊆{0,1,2}^n is said to be a trifferent code (of block length n) if for every three distinct codewords x,y,z∈C, there is a coordinate i∈{1,2,...,n} where they all differ, that is, {x(i),y(i),z(i)} is same as {0,1,2}. Let T(n) denote the size of the largest trifferent code of block length n. Understanding the asymptotic behavior of T(n) is closely related to determining the zero-error capacity of the (3/2)-channel defined by Elias'58, and is a long-standing open problem in the area. Elias had shown that T(n)≤2×(3/2)^n and prior to our work the best upper bound was T(n)≤0.6937×(3/2)^n due to Kurz'23 obtained via a computer search.

In this talk we will see an improved bound of T(n)≤c×n^(−0.4)×(3/2)^n where c is an absolute constant. First, we will go over some history of the problem and explore its connections to zero-error information theory, perfect hashing and graph covering. Then, we will go over the main ideas of the proof and several interesting open questions.

Short Bio:

Siddharth Bhandari is currently serving as a Research Assistant Professor at the Toyota Technological Institute in Chicago. Prior to this, he was a Simons-Berkeley Fellow at the Simons Institute for the Theory of Computing. Siddharth completed his Ph.D. at the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai. His research interests lie in exploring interdisciplinary directions with a focus on developing techniques from computer science. He has worked and continues to work in the areas of coding/information theory, MCMC sampling algorithms, and causal inference. Siddharth's work has been recognized with several awards. His dissertation work was awarded the ACM India Dissertation Award. His paper "Improved Bounds for Perfect Sampling of k-Colorings in Graphs" won the Danny Lewin Best Student Paper Award at STOC 2020. He also won the Jack Keil Wolf Student Paper Award at ISIT 2018 for his work "Bounds on the Zero-Error List-Decoding Capacity of the q/(q−1) Channel.