The Leeds Institute for Data Analytics is pleased to present the next seminar in our series showcasing data analytics.
This seminar will be held in 9.59, Worsley building.
In classical complexity theory, PTIME / NP marks the dividing line between tractability and intractability. Nowadays, even reading the whole input just once may be infeasible, due to the sheer size of the data sets we are dealing with. Hence we need algorithms even faster than linear time. Still, we would like to give running time and accuracy guarantees. In a recent paper we provide such algorithms for a large class of problems on sparse graphs and databases. We do this by a novel combination of methods from Property Testing (with roots in Programme Checking and related to the PAC model from Machine Learning) with Logic and Graph Theory. Property testing algorithms are highly efficient algorithms that only access a small number of local parts of the input, and determine global (structural) properties based on what they discover locally. Nevertheless, they come with performance guarantees. This talk introduces the topic and our results from an elementary perspective and highlights connections to other fields, including computational biology, social networks, AI, and data analysis in general.
Before joining the University of Leeds in 2016, Dr Isolde Adler was a Junior Professor at Goethe University Frankfurt (2009-2016), a postdoctoral researcher at the University of Bergen in Norway (2008/09) and at Humboldt University of Berlin (2006-2008), and a visiting professor at Humboldt University of Berlin (2008). She obtained her PhD from Albert Ludwig University of Freiburg in 2006.
Both Graph Theory and Logic in Computer Science form the basis of her research interests. She is fascinated by the interplay between the combinatorial structure of graphs and discrete models on the one hand, and their algorithmic properties on the other hand. Furthermore, she likes the challenge of problems that are computationally hard but nevertheless have to be solved in practice. While based in Theory, she also enjoys bridging the gap to practical applications in different fields.
15.30: Quick and accurate: Prototypes for extremely efficient data exploration with guarantees- Polly Fahey
16.00: Explore locally – understand globally: Sublinear time algorithms for problems on large sparse data sets- Dr Isolde Adler
17.00: Networking reception with drinks and nibbles hosted in the LIDA staff kitchen.
To book please email Hayley Irving with your name, occupation and faculty/organisation.