Event time:
Friday, April 30, 2021 - 5:00pm
Event description:
yums seminar series
On the Trifference Problem
Gibbs Assistant Professor Cosmin Pohoata
Zoom Link
https://yale.zoom.us/j/93022685686
Abstract
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.