Five papers by CSE researchers presented at STOC 2023

A total of five papers by CSE faculty have been accepted for presentation at the 55th annual ACM Symposium on Theory of Computing (STOC), taking place June 20-23 in Orlando, FL. STOC is the flagship conference of SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory, featuring the latest, most innovative research in theoretical computing.

The papers authored by CSE researchers appearing at STOC 2023 cover a variety of topics spanning routing schemes for network optimization, vertex connectivity problems, matching algorithms, and more. These papers are as follows (CSE researchers in bold):

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Nikhil Bansal, Haotian Jiang, Raghu Meka

Abstract: We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d × d matrices A1,…,An each with ||Ai||op ≤ 1 and rank at most n/log3 n, one can efficiently find ± 1 signs x1,…,xn such that their signed sum has spectral norm ||∑i=1n xi Ai||op = O(√n). This result also implies a logn − Ω( loglogn) qubit lower bound for quantum random access codes encoding n classical bits with advantage ≫ 1/√n.

Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2021] for random matrices with correlated Gaussian entries.

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast

Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak

Abstract: Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives—such as maximal and maximum length-constrained disjoint paths—are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives.

In this work, we give the first efficient algorithms for computing (1 − є)-approximate h-length flows that are nearly “as integral as possible.” We give deterministic algorithms that take Õ(poly(h, 1/є)) parallel time and Õ(poly(h, 1/є) · 2O(√logn)) distributed CONGEST time. We also give a CONGEST algorithm that succeeds with high probability and only takes Õ(poly(h, 1/є)) time.

Using our h-length flow algorithms, we give the first efficient deterministic CONGEST algorithms for the maximal disjoint paths problem with length constraints—settling an open question of Chang and Saranurak (FOCS 2020)—as well as essentially-optimal parallel and distributed approximation algorithms for maximum length-constrained disjoint paths. The former greatly simplifies deterministic CONGEST algorithms for computing expander decompositions. We also use our techniques to give the first efficient and deterministic (1−є)-approximation algorithms for bipartite b-matching in CONGEST. Lastly, using our flow algorithms, we give the first algorithms to efficiently compute h-length cutmatches, an object at the heart of recent advances in length-constrained expander decompositions.

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro

Abstract: We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that SVP in the ℓp norm is W[1]-hard to approximate within any constant factor for any fixed p >1 and W[1]-hard to approximate within a factor approaching 2 for p=1. (We show hardness under randomized reductions in each case.)

These results answer the main questions left open (and explicitly posed) by Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. For MDP, they established similar hardness for binary linear codes and left the case of general fields open. For SVP in ℓp norms with p > 1, they showed inapproximability within some constant factor (depending on p) and left open showing such hardness for arbitrary constant factors. They also left open showing W[1]-hardness even of exact SVP in the ℓ1 norm.

Tight Conditional Lower Bounds for Vertex Connectivity Problems

Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang

Abstract: We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.

We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes:

(1) all-pairs and Steiner vertex connectivity have complexity Θ(n4),

(2) single-source vertex connectivity has complexity Θ(n3), and

(3) single-source-single-sink and global vertex connectivity have complexity Θ(n2).

For graphs with general density, we obtain tight bounds of Θ(m2), Θ(m1.5), Θ(m), respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.

Sublinear Algorithms for (1.5+ϵ)-Approximate Matching

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

Abstract: We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad ‍[FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. ‍[SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time.

We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.