Algorithms and Complexity group news

Bruno Loff defends thesis on computational complexity

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.

Jop Briët awarded Andreas Bonn medal

Jop Briët, former researcher at the Centrum Wiskunde & Informatica (CWI) in Amsterdam, was awarded the Andreas Bonn medal for his thesis `Grothendieck Inequalities, nonlocal games and optimization’.

Giannicola Scarpa defends thesis on quantum entanglement

Quantum entanglement, a strong correlation between particles that can exist even over long distances, has far-reaching consequences. Researcher Giannicola Scarpa of Centrum Wiskunde & Informatica (CWI) has studied several of these consequences for information processing and communication.

Decades-old P=NP 'proof' finally refuted

The traveling salesman problem is still unresolved. A 26 year old claim for a solution is finally fully refuted by researchers of Centrum Wiskunde & Informatica (CWI) in Amsterdam, Université libre de Bruxelles and Friedrich-Alexander Universität Erlangen-Nürnberg.

Early genetic code very resistant to mutation

Researchers of Centrum Wiskunde & Informatica (CWI) in Amsterdam show that the genetic code is remarkably resistant to DNA replication errors. This might explain the success of the common ancestor of all life, who 3,5 billion years ago developed the genetic code that resides in every organism.

Grothendieck applied to entanglement and optimization

Jop Briët, researcher at the Centrum Wiskunde & Informatica (CWI) in Amsterdam, introduces in his thesis new variations of Grothendieck’s inequality. He applied them to entanglement, an aspect of quantum mechanics, and optimization. On 27 October 2011 Briët defends his dissertation at the University of Amsterdam.

Cryptography in a quantum world

Cryptography is the art of secrecy. Nearly as old as the art of writing itself, it concerns itself with one of the most fundamental problems faced by any society whose success crucially depends on knowledge and information.

Gödel Prize winner Saxena appointed at CWI

Computer scientist Nitin Saxena will start as a postdoc researcher at CWI on 1 September 2006. Saxena is well known as co-author of the article 'PRIMES is in P', which received a lot of media attention the last few years. Together with Manindra Agrawal and Neeraj Kayal he won the 2006 Gödel Prize for this 'outstanding journal article in theoretical computer science' in April and, by that, is the youngest Gödel Prize winner ever. He also won the 2006 Fulkerson Prize.

Program recognizes patterns without prior knowledge

Identifying unknown composers, automatically recognizing languages, finding the origin of new strains of viruses. These are just a few examples of the many possibilities of the CompLearn Toolkit, a compression based pattern recognition program made by CWI researcher Rudi Cilibrasi, available since October.

Ronald de Wolf first Dutch winner Cor Baayen Award

Ronald de Wolf first Dutch winner Cor Baayen AwardCWI-researcher Ronald de Wolf has won the 2003 Cor Baayen Award. He is the first Dutch scientist to win this ERCIM award for the most promising European researcher in computer science or applied mathematics. The award ceremony took place on November 5, 2003 during the ERCIM Meeting in Luxemburg. The prize, EUR 5000, was introduced in 1995. It is named after former CWI-director Cor Baayen who was the first ERCIM president.

New Scientist: Software to unzip identity of unknown composers

New Scientist wrote the following text about recent research of Paul Vitányi and fellow researchers at CWI: "A standard PC file-compression program can tell the difference between classical music, jazz ad rock, all without playing a single note. This new-found ability could help scholars identify the composers of music that until now has remained anonymous."