Geometry Seminar
Geometric Methods for Combinatorial Optimization Using Comparison Oracles
Speaker: Madhusudhan Pittu, NYU Courant Institute
Location: Warren Weaver Hall 1314 and on Zoom
Date: Tuesday, March 10, 2026, 6 p.m.
Synopsis:
In linear combinatorial optimization, we aim to find the optimal set \(S\) among a collection \(\mathcal{F}\subseteq 2^U \) of feasible sets over a ground set \(U\) of \(n\) elements. Traditionally, the objective function \(w\) is known explicitly or accessible via a value oracle. We study the weaker comparison oracle, which for any \(S, T \in \mathcal{F}\) reveals only which set has smaller total weight (or if they are equal). We investigate the query complexity and computational efficiency of optimizing in this model.
Approaching this problem from a geometric perspective, we characterize query complexity through the "conic dimension" of the set of points that are indicator vectors of sets in \(\mathcal{F}\)—the maximum size of a sequence where each point lies outside the conical hull of its predecessors (a modified special case of the previously known inference dimension). This shows that \(O(n^2 \log^3 n)\) comparisons suffice for any boolean optimization problem—even NP-hard ones—revealing a fundamental separation between information and computational complexity.
Having resolved the query complexity, we ask for efficient algorithms for set systems that are optimizable in the value oracle case. First, we observe that this is fundamentally a point location problem in the dual space. Every comparison acts as a query against a hyperplane arrangement, reducing the optimization to locating the hidden weight vector within a specific full-dimensional cell. The certification problem is to provide a small certificate proving that the optimal weight vector is in a particular region of this arrangement. To navigate this, we introduce the Dual Ellipsoid Method. This framework efficiently reduces optimization to certification by maintaining a region of plausible weight vectors and using invalid certificates to generate separating hyperplanes.
We conclude by briefly highlighting how these geometric foundations yield the first polynomial-time, low-query algorithms for classic combinatorial applications.
Joint work with Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Jon Schneider, and David P. Woodruff. The paper will appear at STOC 2026 and is available on arXiv at https://arxiv.org/abs/2511.15142.
Notes:
In person and on Zoom. Plz contact Boris Aronov if you are not NYU-affiliated and want to attend in person and/or to be put on the mailing list and get the Zoom information.