PhD Project: Doing More with Less: Sparsification and Redundancy in Infinite Structures

Sparsifying neural networks has received attention in the literature but few research has been done to identify redundancy in the training data. For this purpose we have identified the infinite-domain constraint satisfaction problem (CSP) as the ideal candidate. Theoretically, we ask a fundamental question of which mathematical tools developed for finite structures can be brought to infinite structures, and will develop general tools for studying redundancy, sparsifiability, and related questions, with broad practical implications. To this aim, our three principal questions are as follows.

Question 1: What is the precise relationship between sparsification and redundancy over infinite structures? Is coding theory in the infinite setting useful as intermediate problems?

Question 2: For which infinite structures do small sparsifiers exist? And can their size be related to chain-length and VC-dimension?

Question 3: Can we compute or at least approximate such sparsifiers in a reasonable amount of time?