Monday April 12 4:00 - 4:50 PM Kelley 1001
Jérémy Barbay Assistant Professor Universidad de Chile >From Output Sensitivity to Instance Optimality >From sorting to many NP-hard problems, the pessimism of worst case analysis is >progressively replaced with finer approaches, such as output sensitivity, >adaptive analysis, parameterized complexity, competitive analysis, smooth >analysis, instance optimality. In the same way that compression schemes take >advantage of the specificities of data (e.g. image, music, video) in order to >compress it better, practical algorithms take advantage of the specificities >of an instance to solve it faster (than the worst case over instances of >comparable size). Using this concept to revisit previously known algorithms, >one sometimes discovers that they perform better than was previously thought. >In this talk I will describe the basis of this approach, and as an >illustration, a sequence of results on the computation of the planar convex >hull from the first approach to the latest, instance optimal results, some of >which were presented at the FOCS 2009 conference. This work is the result of a >collaboration with Peyman Afshani during (and after) his visit to Santiago in >December 2008, and with Timothy Chan during (and after) my visit to Waterloo >in February 2009. Biography Jérémy received a BSc in Mathematics in 1997 in Rouen, a Master in 1998 and a PhD in 2002, both in CS in Orsay. He was a posdoctoral fellow at the university of British Columbia from 2002 to 2004 and an assistant professor at the university of Waterloo from 2004 to 2008. He is now an assistant professor at the university of Chile. Jérémy's research spans several domains, and can be divided into two main topics and a few alternate ones. The two main interests concern the adaptive analysis of the complexity of algorithms, and the design of succinct data structures. His other interests concern application of those results to information retrieval, mathematical models for the theory of evolution, electronic tools for teaching and e-teaching, and publication protocols for digital documents. _______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
