CWI researcher Bruno Loff has developed new techniques for determining the complexity of problems that can be solved by a computer. Studying computational complexity provides insight in the inherent difficulty of different types of problems, and the amount of computing power necessary to solve them. Loff will defend his thesis ‘A Medley for Computational Complexity’ on Tuesday 21 January 2014 at the University of Amsterdam.
The complexity of computational problems is a fundamental problem in theoretical computer science. It asks whether there is a practical limit to what computers can and cannot compute efficiently, and how this can be determined. The P versus NP problem, the formal version of this question, is one of the famous seven Millennium Prize Problems, for which the Clay Mathematics Institute has offered $1 million for a satisfying solution.
In his thesis, Loff investigated the complexity of four different types of algorithms. By applying tools from various fields of computer science, he was able to advance the characterization of randomized algorithms, prove bounds for the size of certain kinds of digital logic circuits and the so-called knapsack problem and prove new theorems for communication complexity. This research was funded by the Portuguese Science Foundation FCT and CWI.
Thesis: A Medley for Computational Complexity
By: Bruno Loff (CWI Algorithms and Complexity-group)
Promoter: Prof. dr. Harry Buhrman (CWI and UvA)
Date: 21 January 2014, 10.00h
Place: Agnietenkapel, Oudezijds Voorburgwal 231, Amsterdam
