Making a Trifference

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. Ref: Siddharth Bhandari, Abhishek Khetan, Improved Upper Bound for the Size of a Trifferent Code. [arXiv:2402.02390]. In the proceedings of the IEEE International Symposium on Information Theory (ISIT) 2024.

Venue: A3 117

Speaker Bio

Siddharth Bhandari completed his Ph.D. from the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, and followed that up with a Simons-Berkeley postdoctoral fellowship from the Simons Institute for the Theory of Computing in Berkeley. He is a recipient of the Jack Keil Wolf Student Paper Award at ISIT-2018, the Danny Lewin Best Student Paper Award at STOC-2020, and the ACM India 2022 Doctoral Dissertation Award. He is currently a Research Assistant Professor at the Toyota Technological Institute in Chicago.