Embedded Files
Solver-Assisted Discovery of Computational Complexity Results in Data Management
Solver-Assisted Discovery of Computational Complexity Results in Data Management
The DREAM Lab focuses on building systems for efficiently managing data. We focus on diverse topics, including probabilistic databases, privacy-preserving data analysis, mining and analysis of social networks and graph data, secure database architectures, database auditing, data stream processing, sensor data management, flash-based database management, provenance, causality, reverse data management, diversity and fairness, among others.
Project Description:
Database theory broadly studies: Given a large amount of (structured) data, what types of questions can be answered efficiently? We can show that some questions are “easy” or tractable by finding and proving the correctness of algorithms that can solve them. On the other hand, we can show that questions are “hard” or intractable by showing that the question is as hard as some other hard questions.
Solvers are mathematical software that takes in some input constraints and searches for a solution that satisfies them. Some well-known examples include SAT solvers, and linear programming solvers.
Bringing the two areas together - Can we now formulate the properties we are looking for in an algorithm as input to a solver and use it to discover new algorithms and complexity results?
Learning Objectives:
- Understand mathematical notation and formalisms related to computational complexity and database theory
- Translate problems into constraint optimization problems and satisfiability problems
- Create and run empirical experiments to test hypotheses, and measure performance and outcomes
Skills needed:
- Introductory background/ Strong interest in Mathematical Logic
- Ability of writing code in Python and willingness to learn to learn declarative programming languages
Report abuse