Mason DiCicco

Mason DiCicco

Publications

Inoculation strategies for bounded degree graphs

Authors: Mason DiCicco, Henry Poskanzer and Daniel Reichman

Published in: Theoretical Computer Science, Volume 1035

We devise asymptotically tight bounds for the price of anarchy for several graph families in a model of epidemic containment.

Nearest Neighbor Complexity and Boolean Circuits

Authors: Mason DiCicco, Vladimir Podolskii and Daniel Reichman

Published in: The 16th Innovations in Theoretical Computer Science (ITCS)

We initiate the systematic study of the representational power of nearest and k-nearest neighbors through Boolean circuit complexity.

The Karp Dataset

Authors: Mason DiCicco, Eamon Worden, Conner Olsen, Nikhil Gangaram, Daniel Reichman, and Neil Heffernan

Published in: The 4th Workshop on Mathematical Reasoning and AI at NeurIPS

We introduce the Karp dataset: The first dataset composed of detailed proofs of NP-completeness reductions.

The Learning and Communication Complexity of Subsequence Containment

Authors: Mason DiCicco and Daniel Reichman

Published in: The 2023 IEEE International Symposium on Information Theory (ISIT)

We devise asymptotically tight bounds for the communication complexity of subsequence detections and the sample complexity (VC dimension) of a corresponding classifier.