I am working on computational complexity (mostly within the class NP), constraint satisfaction problems (CSPs), their approximation and optimisation, and underlying mathematics.
The Constraint Satisfaction Problem is the problem of deciding whether a list of constraints over variables with (usually finite) domain can be satisfied simultaneously. This is a wide class of problems which includes, the Boolean SAT problem, linear programming, solving systems of equations, and many other problems. Some of these are NP-complete, and some are solvable efficiently in polynomial time.
You may also check my research at my home page, and my github page.
Some ideas for projects follow. In general, I would be happy to supervise projects that are theoretical and/or mathematical in nature, contributions to open-source projects, in particular, those implemented in Python (as that is my language of choice these days), and tools for improving your personal work-flow.
Puzzle games from NP-complete problems
NP-complete problems are great as a basis for puzzle design. The key idea comes from the fact that the complexity class of NP is essentially defined as those problems for which it is hard to find a solution, but easy to check that a solution is correct. A particular example of such a problem is Sudoku.
- The project can choose an NP-complete problem and design a casual puzzle game based on this problem. This could be a phone app, or a web application.
Graph algorithms
There are many theoretical graph algorithms that are not implemented in practical tools.
- Implement Weisfeiler-Leman colour refinement algorithm for graph isomorphism. For initial exploration, see the Wikipedia page. Surprisingly, some establish Python libraries for graphs, e.g., NetworkX, do not contain implementation of this test. The project could fill this gap, or explore other implementations, variants of the algorithm, etc.
SAT and CSP solvers
CSP solver is an algorithm that computes a solution to a given CSP instance. We are often interested in finding a relatively efficient algorithm which solves an NP-complete problem, so it may be applied in the general case. These solvers are usually based on a combination of some kind of heuristic and backtracking.
A particular case of a CSP solver is a SAT solver, which solves the SAT problem. There are many SAT solvers, and SAT solving competitions. Surprisingly the same cannot be said about general CSP solvers.
The project ideas below require different amount of coding, mathematical understanding, and creativity.
Build a SAT solver based on a theoretical algorithm, and benchmark it against state-of-the-art SAT-solvers.
Build an reasonably efficient CSP solver.
Apply linear programming as a heuristic for a SAT/CSP solver, and compare to SAT-solvers based on different methods.
Use a SAT solver to solve a practical NP-problem. You would need to come with a problem of your own where a SAT solved could be hooked to.