Description of field of research:

Establishing that an algorithmic problem B is NP-complete requires transforming another problem A to B. These transformations or reductions between problems define a graph where each algorithmic problem is a vertex. Understanding the properties of this graph of problems and finding shorter paths between problems can be very beneficial to Theoretical Computer Science, as well as to Artificial Intelligence, and Algorithms design. Unfortunately, navigating this graph today remains a manual task with little computer help, essentially reading definitions and proofs in research papers and online blogs.

School

Computer Science and Engineering

Research areas

Algorithms, Artificial Intelligence, Theory

The objective of this project is to start remediating this issue by designing a digital format for this graph (and the meta-data useful to researchers and programmers), starting to populate it, and implementing some related graph exploration algorithms.

Background knowledge and skills useful for this project (at least one is desirable but not all required because the topic will evolve to suit the strengths of the intern).

  • Algorithms (e.g. COMP3121/COMP3821)
  • Artificial Intelligence / Logic (e.g., COMP3411)
  • Web development
  • Pierluigi Crescenzi and Viggo Kann. "How to find the best approximation results". In: ACM SIGACT News 29.4 (1998), pp. 90-97
  • Michael R Garey and David S Johnson. Computers and intractability. Vol. 174. freeman San Francisco, 1979