Mathematics Colloquium: Untangling ad hoc File Formats using the Dowker complex

Speaker:  Michael Robinson, American University

Title:  Untangling ad hoc File Formats using the Dowker complex

Abstract :  File format specifications are dynamic entities that are often ambiguous. A given clause in a specification may have several distinct but self-consistent interpretations, and these interpretations may impact the interpretations of other, related clauses. As a result, files from different dialects of a format tend to exhibit divergent behavior at multiple, independent points within a parser's code base.

If one determines which files can be successfully read by which computer programs, one obtains a binary relation.  That is, multiple files can be read by a given program, and conversely a given file may be read by many different programs.  If one considers a set of files that are supposed to comply with a particular format, this imposes considerable structure on the file-program relations that can arise.

The famous Dowker complex is the applied combinatorial topologist's go-to tool for studying relational data, but on its own it is rather limited.  This talk will outline additional structure built upon the Dowker complex that enables rigorous statistical tests to be applied.  These tests can be interpreted back into the context of the original application, giving new ways to identify what it means for files to comply with (or violate) a particular format.

Time:  Friday, October 13, 3:30pm – 4:20pm

Place:  Exploratory Hall, room 4106

Zoom and In-person