[PS] On the Trifference Problem - Cosmin Pohoata

Event time: 
Friday, April 30, 2021 - 5:00pm
Event description: 
yums seminar series

On the Trifference Problem

Gibbs Assistant Professor Cosmin Pohoata

Zoom Link



In theoretical computer science, a perfect 3-hash code C is a set of n-dimensional vectors with coordinates among {0,1,2} and which have the property that for every 3 distinct vectors x,y,z in C there exists at least a coordinate where the entries of the vectors are pairwise distinct (i.e. x,y,z are “trifferent” in this coordinate). Determining how large can such a code be is an important and difficult problem in the field, known as the Trifference Problem. In this talk, we will discuss what is known about it and reflect upon a few intriguing connections with some other difficult problems in extremal combinatorics.