« Locality Preserving Hash Functions, a Partial Order and Tiles in Binary Space
Locality Preserving Hash Functions, a Partial Order and Tiles in Binary Space
April 29, 2021, 5:00 PM - 6:00 PM
Location:
Online Event
Victor Miller, Center for Communications Research, Princeton
A "tile" in the space B^n of bit vectors of length n, is a subset S of B^n, such that there is another subset A of B^n so that every element of B^n can be written uniquely in the form a + s, where a in A and s in S. A particular class of tiles are the subsets of minimum weight elements in the cosets of a linear code over GF(2). In systematically investigating locality preserving hash functions, we generated the list of all possible tiles of cardinality <=64 satisfying a certain optimality condition. All but 6 of them turned out to be the sets of minimum weight elements described above. Attempts to prove the same for the remaining 6 remained elusive. Instead we found two computational criteria -- one using linear programming, and the other using combinatorial bin packing, which showed that the remaining 6 could not be tiles.
[Joint with Don Coppersmith, Dan Gordon and Peter Ostapenko]