Modern Computer Science has benefited tremendously from progress in algorithmic foundations. New developments on the algorithmic front have had a significant impact on practice. In fact, establishing new algorithms has gone hand in hand with innovations in computer systems. Nowadays, customized hardware (such as TPU’s) is being produced specifically with the goal of running specific underlying algorithms; similarly, performing computation on massive data sets poses major challenges due to the size of the input.

In this context, it is of critical importance to go beyond the traditional setting where the algorithm has full access to the entire input, and design algorithms that can efficiently work under the specific constraints of the actual setting where they are deployed. We therefore propose in the present project a systematic study of algorithms which obey the limitations of the actual setting for which they are designed, specifically obeying the limitation of the input-access model, and yet exploiting the advantages of said model.

Our main research objective is to significantly improve the theoretical foundations of efficient algorithms that address contemporary challenges, where access to the input is constrained. Specifically, we will focus on online algorithms, which operate under uncertainty regarding the future inputs or requests; streaming algorithms, which must work under stringent memory constraints; and algorithms with oracle access, which can only access their input through some restricted set of “allowed” queries.

Our project involves student and faculty exchanges between the two countries, to provide students from both countries access to an international experience and expand existing collaborations.

We anticipate providing results that go beyond the standard “worst-case analysis” more accurately match the difficulties faced nowadays by real life systems, as well as developing a principled approach to exploiting the new advantages offered by modern prediction systems, and in particular machine learning-based predictions. This will translate both into publications in flagship conferences and top venues, as well as principled algorithms ready to be implemented and deployed.

UMR8243 Institut de Recherche en Informatique Fondamentale, CNRS/Université Paris Cité

School of Computer Science, Faculty of Engineering, University of Sydney