Keynote Speakers

Susanna F. de Rezende

Department of Computer Science, LTH, Lund University

TITLE: Lower Bounds in Monotone Circuit Complexity

ABSTRACT: Monotone Boolean circuits are circuits that use only AND and OR gates (no NOT gates). In this talk, we will survey both classical results and recent developments in monotone circuit complexity. Our focus will be on so-called query-to-communication lifting theorems, which have been instrumental in addressing many open problems in the area. In particular, we will show how these have led to the strongest known lower bounds for the clique function. Along the way, we will touch on other recent results and discuss some open questions that remain. 

Paolo Ferragina

Sant’Anna School of Advanced Studies

TITLE: Learning for Data Compression and Indexing

ABSTRACT: Key-value stores, vector and graph DBs, as well as search engines are posing a continuously growing need to efficiently store, retrieve and analyze massive datasets under the many and different requirements posed by data types, users, devices, and applications. Such a new level of complexity cannot be properly handled by just known techniques, so that academic and industrial researchers started recently to devise new compression and indexing schemes that integrate classic approaches with various kinds of advanced techniques drawn from computational geometry and machine learning. In this talk, I’ll survey the evolution of these algorithmic solutions, discuss their theoretical and experimental performance, highlight their limits and some recent results that are pointing out new challenges worth of future research.

Sophie Huiberts

Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
Clermont Auvergne University

TITLE: Open problems about the simplex method

ABSTRACT: The simplex method is a very efficient algorithm. In this talk we look at recent attempts to explain this using smoothed analysis. Following that, we discuss to what extent smoothed analysis succeeds at providing a scientific explanation, and discuss what any successor theory much resolve. Along the way I will sprinkle in some historical anecdotes about linear programming and its applications for human rights violations.