Inoculation strategies for bounded degree graphs
Published in Theoretical Computer Science, Volume 1035, 2025
We devise asymptotically tight bounds for the price of anarchy for several graph families in a model of epidemic containment.
Download here
Published in Theoretical Computer Science, Volume 1035, 2025
We devise asymptotically tight bounds for the price of anarchy for several graph families in a model of epidemic containment.
Download here
Published in ITCS, 2025
We initiate the systematic study of the representational power of nearest and k-nearest neighbors through Boolean circuit complexity.
Download here
Published in The 4th Workshop on Mathematical Reasoning and AI at NeurIPS, 2024
We introduce the Karp dataset: The first dataset composed of detailed proofs of NP-completeness reductions.
Download here
Published in ISIT, 2023
We devise asymptotically tight bounds for the communication complexity of subsequence detections and the sample complexity (VC dimension) of a corresponding classifier.
Download here