“Tractable Problems at the Intersection of Constraint Optimization and Query Optimization”

Many fundamental data management problems involve solving a constraint optimization problem over the results of a query answer. For example, given a query answer – how to best explain / debug / refine / represent / justify it? Each of these questions is a seminal data management problem that has been studied for decades, with countless variants for each question as well. However, since all such problems have been typically studied in isolation – prior solutions do not generalize. In addition, tractability boundaries remain completely open, even for very specific problems and variants.

In this talk, we will discuss a recent unified paradigm to solve constraint optimization problems over query answers – instead of creating specialized algorithms for each unique case. We find that such a paradigm also helps us find and solve tractable sub-classes of hard problems automatically. We will also discuss connections of this problem to other fundamental problems in data management, and how the tools and algorithms developed for this problem (such as automatic proof generation) can be used to solve other problems in data management and beyond.

Neha Makhija is an Assistant Professor at the Manning College of Information and Computer Sciences (CICS) at the University of Massachusetts, Amherst. Her core research goal is to design unified algorithms that automatically work as efficiently as the theoretical best-case for the given input problem instance (i.e., have instance-optimality), thus achieving the best of both theory and practice. She studies this question in the domain of explainable data management, provenance, and knowledge representation. Neha earned her PhD in Computer Science from Northeastern University in 2025, where her dissertation was awarded the Khoury Research Award.