Seminars & Colloquia Calendar
Locality preserving hash functions, a partial order and tiles in binary space
Victor S. Miller -- IDA Center for Communications Research, Princeton
Location: zoom
Date & time: Thursday, 29 April 2021 at 5:00PM - 6:00PM
Abstract: 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]
password: 6564120420
