Online computation has proven itself a very useful paradigm for the design and analysis of algorithms for problems of incomplete information. An emerging, and fast-growing trend is to study online computation in a setting in which the algorithm has certain additional information, such as some machine-learned advice or prediction, which may however be imprecise. The central question then is: how can one design online algorithms that leverage such predictions about the input, and which perform well if the prediction is imprecise, or even entirely erroneous? We propose a thesis topic that is in the intersection of machine learning and theoretical computer science, and addresses some new directions in this nascent field.
Keywords : Online computation, competitive analysis, advice, machine learning with predictions
This PhD research project has been submitted for a funding request to “Sorbonne Center for Artificial Intelligence (SCAI)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.