WPI - Computer Science Department, PhD Dissertation Defense , Mason DiCicco " Computational Complexity Across Models: Communication, Circuits, and Learning"
12:00 p.m. to 1:00 p.m.
Computational Complexity Across Models: Communication, Circuits, and Learning
Mason DiCicco
PhD Candidate
WPI – Computer Science Department
Wednesday, August 6, 2025
Time: 12:00 PM – 1:00 PM
Location: Unity Hall 320
Zoom Link (Hybrid):
https://wpi.zoom.us/j/93930488773
Committee members :
Advisor: Professor Daniel Reichman, Computer Science, WPI
(Internal) Comittee Member: Professor Gabor Sarkozy, Computer Science, WPI
(Internal) Comittee Member: Professor Hanmeng Zhan, Computer Science, WPI
(External) Comittee Member: Professor William Martin, Mathematics, WPI
Abstract:
We are interested in the complexity of computing and representing Boolean functions. Our objective is to provide both upper and lower bounds on the expressiveness of various models of computation, emphasizing connections between circuits, communication, and learning.
We establish tight bounds on the communication complexity of deciding whether one string contains another as a subsequence, yielding lower bounds on the sample complexity of an analogous learning problem. We also provide lower bounds for circuits computing the subsequence containment.
We study the capacity of the well-known nearest neighbor classification scheme to represent Boolean functions. We show that nearest neighbor representations are closely related to circuits, and that strong lower bounds against this model would constitute a breakthrough in circuit complexity.
We also contribute a new dataset of NP-hardness reductions, which we call the Karp dataset. This dataset is designed to be used in conjunction with machine learning techniques to study reasoning capacity of modern artificial intelligence systems, and potentially to discover new NP-hardness reductions.