[Colloq] PHD Thesis Defense - Ahmed Abdelmeged - Friday May 23, 3pm, 366 WVH - Organizing Open Online Computational Problem Solving Competitions

[Jessica Biron]

PhD Thesis Defense, College of Computer and Information Science, Northeastern University 

Who: Ahmed Abdelmeged 

When: Friday May 23, 2014, 3pm , 366 WVH 

Title: Organizing Open Online Computational Problem Solving Competitions 

Abstract: 

Competitions have been successfully used to build and organize communities aiming to solve complex computational problems. Recently, the winner of an open online competition to solve a complex immunogenomics problem has produced an algorithm that has a higher accuracy and is 1,000 times faster than the corresponding algorithm developed by the US National Institutes of Health. 

We developed a novel sports-like approach for organizing open online computational problem solving competitions where participants assist in the evaluation of their opponents. Therefore, we reduce the competition administration overhead. We tackled several challenges that can render the results of this kind of competition meaningless. The most prominent challenges are the potential of incorrect peer evaluation of participants as well as collusion potential. 

We addressed the potential of incorrect peer evaluation of participants by using generalized semantic games of interpreted predicate logic sentences specifying computational problems. 

We addressed the collusion potential by using collusion-resistant ranking functions. We developed a first of its kind, formal characterization of collusion-resistant ranking functions for generalized semantic game tournaments. We also developed a representation theorem for collusion-resistant ranking functions as well as other basic correctness properties. In essence, we show that under basic correctness properties of ranking functions, the collusion-resistant property is logically equivalent to using a ranking function that is based on a generalized form of fault counting. 

In addition to competition organization, the system and its theoretical foundation is also useful for pushing the state-of-the-art in formal science education. Indeed, the system was developed in the context of education (Algorithms and Software Development Courses) to facilitate fair peer grading and focused debates among students. 

Committee: 

Karl Lieberherr (advisor) 

Ravi Sundaram 

Thomas Wahl 

Nicole Immorlica (Microsoft Research)