PhD Defense: From Hardness to Structure: Algorithmic Insights from SAT, Diversity, and Connectivity

This research explores how structural understanding can turn computational hardness into algorithmic progress, focusing on three NP-hard directions: SAT, Diversity Maximization, and Connectivity.
In SAT, we introduce a new method for generating hard instances with multiple solutions that still appear random, making them indistinguishable to efficient algorithms.
In Diversity Maximization, a problem from the family of Max-Cut, we design deterministic algorithms with improved approximation guarantees, achieving a twofold improvement over previous results and nearly tight bounds across both general and low-dimensional metric spaces. The goal is to find two subsets of a given size that are as far apart as possible, balancing diversity and structure.
For Connectivity, we advance the theory of Steiner Forest problems, improving approximation factors from 2.54 for the prize-collecting version to a natural 2-approximation, and further to a (2−ε) approximation for the classical case. We also construct counterexamples showing that some long-assumed 2-approximation algorithms perform worse than expected.
Together, these results trace a path from hardness to structure, showing how identifying and exploiting hidden regularities can break long-standing computational barriers.