Whether they are analyzing the stock market, genes or search data, computer programs often need to process large amounts of data. Sometimes there isn't even have enough time to process all the data that is relevant to the calculation. If it were possible to obtain approximate solutions to computational problems without looking at all the data, it would save valuable calculation time. CWI computer scientist David García Soriano developed methods that do just that: they quickly distinguish objects with desired properties from those which are far from it. García Soriano defends his thesis titled ‘Query-Efficient Computation in Property Testing and Learning Theory’ on 25 April at the University of Amsterdam.
Hair colour
‘Let’s for instance suppose that hair color is determined by a small number of genes’, García Soriano says. ‘As long as you don’t know which genes, it may seem that every single gene in the genome still needs to be thoroughly analyzed to determine its influence on hair colour. Suppose that not too many genes are involved in determining hair colour. Then the property testing method that I devised would quickly determine precisely in which way the unknown set of genes determines hair color, even when we cannot afford the time to find out which genes are actually involved. This can obviously save a lot of time in certain situations.’
Understanding of the resources required to solve certain tasks is one of the central goals in theoretical computer science, and contributes to a more efficient use of computing power.
More information:
- Website David García Soriano
The PhD ceremony takes place on 25 April 2012 in the Agnietenkapel, Oudezijds Voorburgwal 231, Amsterdam.
Supervisor: prof. dr. H.M. Buhrman. Committee members: prof. dr. A. Schrijver, prof. dr. R.M. de Wolf, dr. A. Matsliah, prof. dr. E. Fischer.
