Data Management Seminar: Neha Makhija, Designing Data to Shape Outcomes: Where Theory Guides Practice
Content
Speaker
Abstract
While traditional data management typically answers questions like, “What were the expenses of my company this quarter?”, the underlying data can be used to answer more powerful questions like: “What expenses should my company have this quarter (given the business requirements)?” These questions can generally be modeled as “Reverse” Data Management (RDM) problems that ask: “What optimal interventions on data produce a desired property in the output?” Several problems from this family have been studied and used to solve problems in domains as diverse as query explainability, data debugging, knowledge representation, and effective SQL pedagogy. However, these variants, their complexity, and practical algorithms had always been studied in isolation—hence prior solutions do not generalize to slightly different problems and settings, and many questions in this space remain unsolved.
My work introduces a novel paradigm to solve such RDM problems: instead of creating dedicated algorithms for easy (PTIME) and hard cases (NP-complete), we devise unified algorithms that can solve all problem instances and are guaranteed to terminate in PTIME for easy cases. This approach allows us to separate the task of designing efficient algorithms from proving tractability, allowing us to solve problems in a “coarse-grained instance optimal” manner. Our approach leads us to both practical benefits in terms of automatic time guarantees and ease of implementation as well as new theoretical complexity results. A complementary contribution of my work is an Automatic Hardness Gadget finder—which leverages a semantic specification of NP-Hardness to computationally resolve open theoretical complexity questions.
Bio
Neha Makhija is a CS PhD student at the DataLab@Northeastern University where she is advised by Wolfgang Gatterbauer. Her research focuses on bridging the theoretical and practical aspects of data management, specifically in the context of explainable data management and knowledge representation.
Related work
- Neha Makhija and Wolfgang Gatterbauer. A Unified and Practical Approach for Generalized Deletion Propagation. Under Submission: arXiv 2024 (https://arxiv.org/abs/2411.17603)
- Neha Makhija and Wolfgang Gatterbauer. A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations. SIGMOD 2024 (https://doi.org/10.1145/3626715)
- Neha Makhija and Wolfgang Gatterbauer. Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries. PODS 2024 (https://doi.org/10.1145/3651605)
Host