IMSc Webinar

Sub-linear Space Algorithms for NP-hard Problems (Synopsis Seminar)

Arindam Biswas

IMSc

Alongside the usual line of enquiry into NP-hard problems where one tries to identify scenarios (fixed-parameter tractability or approximation) in which solutions can be computed in polynomial time, it is also interesting to study the question of whether such solutions can be computed under space constraints.

In this work, we identify a number of optimization problems that admit sublinear-space approximation or fixed-parameter algorithms. Our model allows for random access to memory, but the amount of memory available is constrained to be sublinear in the problem size. Examples of problems we study are Hitting Set, Max SAT, Subgraph Detection and Feedback Vertex Set.

Earlier results in this model have mostly dealt with problems concerning reachability, graph recognition and sorting. With this work, we show that the model even allows one to compute solutions for many NP-hard optimization problems.


Join at:
zoom.us/j/99018916192?pwd=Vnd3YW1RbisxNlVhZGN5RXYvMVZ5Zz09
Meeting ID: 990 1891 6192
Passcode: 422343