Alladi Ramakrishnan Hall

Algorithms for NP-hard Problems in the Sublinear Space Regime

Arindam Biswas

TU IImenuau, Germany

This willbe a virtual event. Please use the following to join virtually.
zoom.us/j/96655727773
Passcode: 749114
Abstract: Alongside the usual line of enquiry into NP-hard problems where one tries to identify scenarios (approximation or fixed-parameter tractability) in which solutions can be computed in close to polynomial time, it is interesting to study the question of whether such solutions can be computed efficiently when space constraints are imposed.
In this thesis, we devise sublinear-space approximation and fixed-parameter algorithms for a number of optimization problems. In devising our results, we focus on the sublinear-space regime, where an algorithm: (a) has random access to the input; (b) cannot not modify the input; (c) cannot read the output; and (d) can only use a small amount of additional memory, constrained to be sublinear in the input size.
While our goal is to compute solutions using as little space as possible, it seems unlikely that one should be able do this for NP-hard problems in close to logarithmic space. In their standard implementations, most approximation or parameterized algorithms for NP-hard problems use space at least linear in the input size. Owing to this, we allow ourselves a more generous sublinear space constraint. Even so, under this constraint, it is not clear that one can carry out basic algorithmic primitives such as computing BFS trees or maximal independent sets.
The overall objective of this thesis is to identify NP-hard problems that admit sublinear-space approximation or fixed-parameter algorithms. Up to this point, such algorithmic results have been few and far between. We hope that our results serve as proof of the existence of non-trivial results on NP-hard problems in the sublinear-space regime, paving the way for further work in this area.