Exact Algorithms for Identifying Structure in Sums and Graphs

Many fascinating problems in theoretical computer science have the following form: 

• "Given as input a large data object (such as a graph or a set of numbers) can we find a large, mathematically structured sub-object hidden within?"

(Famous problems such as the Traveling Salesman Problem, Subset Sum, Graph Coloring, Clique and others fall into this category.) Exact algorithms for these problems are approaches that solve even the hardest problem instances without making compromises such as searching for tractable special cases, approximating optimal solutions, or resorting to heuristics. Although often too slow to be used in practice, exact algorithms illuminate the mathematical structure of hard problems, clarify the complexity-theoretic relationships between them, and often involve fresh applications for techniques from pure mathematics in theoretical computer science.

This is a collaborative research project in which students will work closely with each other and a faculty member (Prof. Tim) on problems at the intersection of computer science and mathematics. We will begin by reviewing the best known exact algorithms for several existing problems, familiarizing ourselves with the mathematical concepts required and with previous algorithmic approaches (existing research). We will then refine our focus to a single problem and work to identify tractable settings in which we can design and formally analyze improvements to existing algorithms. 

Students will reach a point where they can fluently discuss their problem, existing algorithms, promising approaches and remaining obstacles with mathematical maturity and present work via poster. Progress substantial enough for a conference publication is possible but unlikely and not expected during the summer term.

If you're interested in joining the project, please summarize your curricular experience in computer science and mathematics and let me know why you're interested in pursuing research in algorithms. I hope to see you in the summer!

This project is affiliated with Harvey Mudd's REU "Exploring the Limits of Intelligent Systems". If you're a US Citizen or permanent resident, you can apply for this position as an REU student through ETAP at the following link: https://etap.nsf.gov/award/1783/opportunity/10312. (If you're not a US Citizen or permanent resident, you can still apply through URO.)