WPI - Computer Science Department, PhD Proposal Defense , Mason DiCicco " Studies in Complexity: Learning, Representation, and Computation"

Mason DiCicco

PhD Candidate

WPI – Computer Science Department 

Friday, July 26, 2024

Time: 10:00 a.m. – 11:00 a.m.

Location: FL Beckett Conference room

Zoom link: https://wpi.zoom.us/j/96116813777

Committee Members: 

Advisor: Prof. Daniel Reichman , WPI – Computer Science

Hanmeng Zhan, WPI – Computer Science Department 
Gabor Sarkozy , WPI – Computer Science Department 

 William Martin, WPI – Mathematical Sciences 

Abstract: 

A pillar of theoretical computer science is the study of complexity. The essential questions in this domain are to determine the resources required to solve particular problems. This proposal is for a thesis of collected analyses of several problems under several different notions of complexity. 

First, we establish tight hardness results regarding the communication complexity of subsequence containment. This has relevance in many settings involving computation of non-contiguous features

 within sequential data. Here, the "resource" in question is the number of bits communicated in distributed computation. Both model and problem are central ideas in computer science with direct applications as well as theoretical implications -- in particular, the results in this section also establish the hardness of learning a sequence given its subsequences.

Second, we analyze the representational complexity of the nearest-neighbor classification rule. Nearest neighbors is a canonical learning paradigm with countless practical uses, and hence its efficiency is of significant interest. Here, we consider the number of prototypes, or anchors, required to exactly represent Boolean functions via the nearest-neighbor rule. We prove several upper and lower bounds on the nearest-neighbor complexity of particular functions, establish connections to other models of computation such as decision trees, and answer several open questions about this model.