FROM HARDNESS TO STRUCTURE: ALGORITHMIC INSIGHTS FROM SAT, DIVERSITY, AND CONNECTIVITY

Abstract

This thesis investigates the deep interplay between hardness and structure in combinatorial optimization, demonstrating how uncovering and formalizing structural regularities within complex problems enables progress beyond long-standing computational barriers. Spanning three domains—Satisfiability (SAT), Diversity, and Connectivity—the presented works collectively develop a unifying perspective: that algorithmic advancement arises from transforming hardness into exploitable structure. In the SAT domain, the thesis introduces the first general framework for quiet planting of $k$-SAT formulas with multiple planted solutions. Unlike previous models limited to a constant number of solutions, this framework supports an arbitrary number of planted assignments with prescribed pairwise Hamming distances (arbitrary geometry), while ensuring that the resulting formulas remain statistically indistinguishable from uniformly random instances under all Statistical Query algorithms. The construction combines linear-program feasibility conditions with coding-theoretic realizations, uncovering new principles governing distributional hardness and the indistinguishability of structured randomness. In Diversity Maximization, the focus shifts to geometric optimization. The thesis presents deterministic combinatorial algorithms that achieve near-optimal approximation ratios for selecting well-separated subsets in metric spaces, specifically a $(2/\varepsilon)$-approximation for sufficiently large instances, improving upon the best-known randomized bounds and establishing tight lower limits. These results illustrate how geometric separation and combinatorial density arguments can be combined to yield deterministic guarantees for problems closely related to clustering and Max-Cut, without relying on randomization or relaxations. In Connectivity, encompassing the Prize-Collecting Steiner Forest (PCSF) and Steiner Forest (SFP) problems, the thesis develops new algorithmic frameworks grounded in combinatorial structure and local refinement. For PCSF, it presents the first deterministic and purely combinatorial 2-approximation algorithm, matching the optimal factor and surpassing the long-standing 2.54 bound while bypassing LP-based integrality limitations. Building on these ideas, the thesis then introduces a boosted moat-growing and local search framework for SFP, yielding a $(2 - \varepsilon)$-approximation, the first improvement beyond the classical factor 2 in over thirty-five years. This result not only breaks a historic barrier in network design but also provides a structural explanation for the origin of that barrier. Together, these contributions trace a path from hardness to structure, showing that algorithmic progress arises not by avoiding hardness but by uncovering the structure within it.