Seminars

View all Seminars  |  Download ICal for this event

Robust Recovery and Optimization Beyond the Worst Case

Series: Ph.D. Colloquium

Speaker: Rameesh Paul, Ph.D student, Dept. of CSA, IISc.,

Date/Time: Jul 24 10:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Anand Louis

Abstract:
The classical worst-case algorithm design paradigm, while foundational to theoretical computer science, can be prohibitively pessimistic. Many fundamental problems are not only NP-hard but extremely difficult to approximate: for instance, the Maximum Independent Set problem cannot be approximated better than a factor of $n^{1-epsilon}$ for any $epsilon>0$ unless P=NP. The modern approach for coping with such intractability is beyond worst-case analysis, in which one develops refined input models that capture meaningful structure in typical instances of a problem. This thesis makes progress in this direction by designing provably robust and efficient algorithms for a broad class of combinatorial optimization problems, across a variety of beyond worst-case settings.

The central part of the thesis develops a theory for recovering planted subgraphs in random, semirandom, and smoothed models. The canonical example is the planted independent set problem. Here, starting from a set V of n vertices, a hidden set $S subset V$ of size k is chosen as the planted independent set. For every pair of vertices in V x (VS), an edge is added independently at random with probability p. The goal is to recover a set $hat{S}$ of vertices that closely approximates the planted set S. In a seminal work, Alon, Krivelevich, and Sudakov gave an efficient algorithm for the problem when $k=Omega(sqrt{n})$. The problem is more widely known as the Planted Clique problem, a central problem in average-case complexity with deep connections throughout theoretical computer science and mathematics. We ask a broader question: for what other families of planted structures can we obtain similar recovery guarantees? We answer this question affirmatively for a large class of subgraph families including noisy independent sets, bipartite subgraphs, r-colorable subgraphs, and more generally subgraph families characterized by near-satisfiable Constraint Satisfaction Problems (CSPs). Our results build on the popular Lovasz-Theta function certificates (Lovasz 79, Feige-Krauthgamer 00), and recent biclique certificates (Buhai-Kothari-Steurer 23).

An important theme in beyond worst-case analysis is to design robust algorithms whose guarantees continue to hold over as large class of instances as possible -- thereby moving closer to worst-case guarantees. Smoothed analysis of algorithms which originated in the work of Spielman and Teng for explaining the empirical success of the simplex algorithm for linear programming, has emerged as a hallmark of such robustness. In this framework, one starts with an arbitrary (adversarial) instance and applies a small random perturbation to it; the goal is to design an algorithm that works with high probability on the resulting instance. We prove our results in smoothed models, this was previously unknown, even for the planted independent set problem.

We also extend our results to s-uniform hypergraphs; here the key problem is to design a refutation certificate that proves upper bounds on independence number of a sparse random hypergraph. Our work gives improved bounds via Sum-of-Squares certificates, by leveraging recent progress on matrix-concentration inequalities, Bandeira et al. 25. We complement our results with a low-degree polynomial lower bound showing that our bounds are nearly tight. Proving such low-degree polynomial lower bounds was previously not even known for sparse graphs, and was posed as an open problem in Jones et al. 21.

A complementary approach to beyond worst-case analysis considered in this thesis is to study optimization problems on structured instances of graphs and hypergraphs, including instances characterized by low threshold rank, expansion, and high triangle density. We design algorithms showing that such structural promises can be leveraged into improvements over worst-case guarantees. We further study learning-augmented online algorithms, in which, an online algorithm is given access to (possibly imperfect) predictions about the input. We develop online algorithms for a broad class of covering and network design problems that compete with the best prediction in hindsight.

Across these settings, a common theme is the use of continuous methods in robust algorithm design, including linear programs, spectral methods, semidefinite programs, sum-of-squares method, low-degree polynomials, and multiplicative-weight framework.