Algorithms for Restricted Data Models

2023 – 2024

Contact: Adrian Vladu

Australian partner: Prof. William Seeun



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.

Main objectives of research

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.

Network activities and expected results

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.


Institutions and laboratories involved


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


School of Computing and Information Systems, University of Melbourne

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

Scientist, guided towards the optimal solution by a computer or AI system