Seminar Details
Locality Preserving Hash Functions, a Partial Order and Tiles in Binary Space
- Start Date: April 29, 2021
- Event Start Time: 5:00 PM
- Event End Time: 6:00 PM
- Seminar Series: Experimental Math Seminar
- Presenter(s): Victor Miller - Anduril Industries
- Event Location: Online Event
- Event Additional Info: <p>Presented via Zoom: <a href="https://rutgers.zoom.us/j/94346444480">https://rutgers.zoom.us/j/94346444480</a> </p> <p> </p> <p>Password: 6564120420</p> <p> </p>
- Presentation Type: Stand Alone Presentation
- 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]