<< Back to search results

Smoothed analysis: predicting the likelyhood of an algorithm’s worst‐case behavior.

University College Cork

Brief of Description of Project

Smoothed analysis gives a more realistic evaluation of an algorithm’s running time, than worst-case or average-case scenarios. The simplex algorithm runs in exponential-time in the worst-case and yet in practice it is a very efficient algorithm. Providing a model to explain this behavior was a main motivation for developing smoothed analysis. Smoothed analysis is a hybrid of worst-case and average-case analyses that inherits advantages of both, by measuring the expected performance of algorithms under slight random perturbations of worst-case inputs. If the smoothed complexity of an algorithm is low, then it is unlikely that the algorithm will take long time to solve practical instances whose data are subject to slight noises and imprecisions. The model was developed by Spielman and Teng. Smoothed complexity is mathematically challenging to determine in practice and does not lend itself to (semi)automation. The PhD topic focuses on exploring new approaches to modeling smoothed complexity, aimed at facilitating the analysis. Students with a solid background in Computer Science and Mathematics are encouraged to apply. 

Description of facilities and research environment

The Computer Science Department at University College Cork has 28 research active academic staff working in areas of Artificial Intelligence, Distributed Computing, Foundations of Computing, Multimedia, Networking & Systems and Secure, Reliable and Scalable Computing.  In the past five years, in excess of 660 peer reviewed publications have been published in journals. 

Our Department has a very strong track record in commercialisation and has 7 recent patent applications and has spun out three companies; Kleever, Thinksmart and Clinical Support Information Systems.   

To support our dynamic research staff we have top class facilities including a Virtual Reality Laboratory, Audio Visual Studio, Wireless Network Test Beds and a range of High Performance Computing Facilities.   

Integrated in the Department of Computer Science are a number of vibrant research Centres/groups; The Cork Constraint Computation Centre (4C), CEOL The Centre for Efficiency‐Oriented Languages, The Irish Cloud Computing Centre, The Boole Centre for Research Informatics and the Mobile & Internet Systems Laboratory.  These groups generate additional income, for example, in 2011 4C won new grant awards of more than €5m and CEOL has attraced €2.5m in funding.  

In addition to our academic staff, we have 20 post‐doctoral researchers and 27 postgraduate doctoral students.   http://www.ucc.ie/en/compsci/ 


Priority Areas

Principal Investigators

Research Groups