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
Publications
Nearest Neighbor Complexity and Boolean Circuits
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
The Karp Dataset
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
The Learning and Communication Complexity of Subsequence Containment
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