Semester/Bachelor/Master projects

 
Advisor(s) Project title
Jana Cslovjecsek
(On request)
Martina Gallato (Project already assigned)
Adam Polak Deterministic 3SUM hardness

The goal of this project is to look for previously known probabilistic fine-grained reductions from the 3SUM problem which could be derandomized, e.g. with the Chan-Hu technique.

Jonas Racine
(Project already assigned)
Moritz Venzin
Approximating Maximum Independent Set of Rectangles

The main goal of this project is to understand the MISR problem and the various techniques used to tackle it.

Projects at DISOPT: Rules of the game

  • Available projects are displayed on this webpage. Students interested in taking a project with DISOPT are invited to contact us. Projects are allotted first-come first-serve.
  • Please note that for third year Bachelor students, a successful completion of the course Optimisation discrète is required (grade 4.5 or better) to do a project.
  • Each project is supervised by an advisor within DISOPT. The student and the advisor meet within 3 days after the project assignation for the kick-off meeting, where the goals and first milestones are discussed on the basis of the project description.
  • There is a seminar dedicated to project talks. Each student has to deliver two 30 min presentations. Each project student is expected to participate at the presentation of the other students. The quality of the presentation and, in particular, the improvement from first to second presentation, is a grading criterion.
  • There are weekly meetings with the advisor. In these meetings the achievement of previously set goals is assesed and after discussion, new tasks are assigned for the following week and, if necessary, the milestones are updated.
  • Typically, the identified tasks are reading and understanding an article from the literature or implementing algorithms or methods used for the project
  • We expect the students to be on time and well prepared for these meetings. If two meetings are missed by the student without an excuse, or if the student is two times unprepared, the student will not pass the project.
  • There is a mutual evaluation form to be filled out by the student and the advisor  at midterm that serves as a base to improve the performance of the project.
  • At the end of the semester the students will hand in their report and, after that, present their project and results in a 30-minutes final presentation.
  • The final presentation shall be exposed in 10 slides, plus a single bonus slide listing the contribution of the student. The contribution might be of the following kinds: understanding and learning state-of-the art methods, modelling real-life scenarios, algorithm implementations, new proofs of existing results, or (restricted) new results.

Grading:

  • DISOPT uses the full grading spectrum 1-6 to assess projects

Grading criteria:

  • Ability to perform independent mathematical research: literature research (branching out), formulation of  alternative and related goals
  • Mastery of the mathematical theory around the project
  • Usability and efficiency of the code and comparison by exhaustive tests with existing methods (applied projects)
  • Achievement of theoretical goals (new theorems proved, old theorems proved in a creative alternative way)
  • Quality of midterm and final project presentation and the report

Requirements:

High motivation, discrete optimization, linear algebra, programming skills