CSE researchers present six papers at STOC 2022

Six papers authored or co-authored by CSE researchers at the University of Michigan were accepted to appear at the 2022 ACM Symposium on Theory of Computing (STOC 2022), the world’s leading general theoretical computing conference. Six U-M researchers proposed new techniques and discoveries in graph theory, distributed algorithms, dynamic algorithms, and discrepancy theory.

Prof. Thatchaphol Saranurak also co-organized a workshop on recent advances in dynamic algorithms at the conference.

Learn more about the projects:

Byzantine Agreement in Polynomial Time with Near-Optimal Resilience

Shang-En Huang (University of Michigan), Seth Pettie (University of Michigan) and Leqi Zhu (University of Michigan)

Abstract: It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault [FLP85], but that it can be solved with probability 1 [Ben83], even against an adversary that controls the scheduling of all messages and corrupts up to f < n/3 players [Bra87]. The main downside of [Ben83, Bra87] is that they terminate in 2^Θ(n) rounds in expectation whenever f = Θ(n).

King and Saia [KS16, KS18(arXiv:1812.10169)] developed a polynomial protocol (polynomial rounds, polynomial computation) that is resilient to f < (1.14×10⁻⁹)n Byzantine faults. The new idea in their protocol is to detect — and blacklist — coalitions of likely-bad players by analyzing the deviations of random variables generated by those players over many rounds.

In this work we design a simple collective coin-flipping protocol such that if any coalition of faulty players repeatedly does not follow protocol, then they will eventually be detected by one of two simple statistical tests. Using this coin-flipping protocol, we solve Byzantine Agreement in a polynomial number of rounds, even in the presence of up to f < n/4 Byzantine faults. This comes close to the f < n/3 upper bound on the maximum number of faults [BT85,FLM86,LSP82].

A Characterization of Approximability for Biased CSPs

Euiwoong Lee (University of Michigan) and Suprovat Ghoshal (Indian Institute of Science, Bangalore)

Abstract: A μ-biased Max-CSP instance with predicate ψ:{0,1}^r→{0,1} is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most μ which satisfies the maximum fraction of constraints. Biased CSPs are versatile and express several well studied problems such as Densest-k-Sub(Hyper)graph and SmallSetExpansion.

In this work, we explore the role played by the bias parameter μ on the approximability of biased CSPs. We show that the approximability of such CSPs can be characterized (up to loss of factors of arity r) using the bias-approximation curve of Densest-k-SubHypergraph (DkSH). In particular, this gives a tight characterization of predicates which admit approximation guarantees that are independent of the bias parameter μ.

Motivated by the above, we give new approximation and hardness results for DkSH. In particular, assuming the Small Set Expansion Hypothesis (SSEH), we show that DkSH with arity r and k=μn is NP-hard to approximate to a factor of Ω(r³μ^r−1 log(1/μ)) for every r≥2 and μ < 2^−r. We also give a O(μ^r−1 log(1/μ))-approximation algorithm for the same setting. Our upper and lower bounds are tight up to constant factors, when the arity r is a constant, and in particular, imply the first tight approximation bounds for the Densest-k-Subgraph problem in the linear bias regime. Furthermore, using the above characterization, our results also imply matching algorithms and hardness for every biased CSP of constant arity.

Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds

Amos Beimel (Ben-Gurion University), Haim Kaplan (Tel Aviv University and Google research), Yishay Mansour (Tel Aviv University and Google research), Kobbi Nissim (Georgetown University), Thatchaphol Saranurak (University of Michigan) and Uri Stemmer (Tel Aviv University and Google research)

Abstract: A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis.

We give a general reduction transforming a dynamic algorithm against an oblivious adversary to a dynamic algorithm robust against an adaptive adversary. This reduction maintains several copies of the oblivious algorithm and uses differential privacy to protect their random bits. Using this reduction we obtain dynamic algorithms against an adaptive adversary with improved update and query times for global minimum cut, all pairs distances, and all pairs effective resistance.

We further improve our update and query times by showing how to maintain a sparsifier over an expander decomposition that can be refreshed fast. This fast refresh enables it to be robust against what we call a blinking adversary that can observe the output of the algorithm only following refreshes. We believe that these techniques will prove useful for additional problems.

On the flip side, we specify dynamic problems that, assuming a random oracle, every dynamic algorithm that solves them against an adaptive adversary must be polynomially slower than a rather straightforward dynamic algorithm that solves them against an oblivious adversary. We first show a separation result for a search problem and then show a separation result for an estimation problem. In the latter case our separation result draws from lower bounds in adaptive data analysis.

Flow Time Scheduling and Prefix Beck-Fiala

Nikhil Bansal (University of Michigan), Lars Rohwedder (EPFL) and Ola Svensson (EPFL)

Abstract: We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded ℓ₁-norm) setting to bounds on the flow time of an optimal schedule.

Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(sqrt(log n)) and O(sqrt(log n) log P) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(log n) and O(log n log P). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {−1,0,1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded ℓ₁-norm.

Optimal Vertex Connectivity Oracles

Seth Pettie (University of Michigan), Thatchaphol Saranurak (University of Michigan) and Longhui Yin (Tsinghua University)

Abstract: A k-vertex connectivity oracle for undirected G is a data structure that, given u,v ∈ V(G), reports min{k,κ(u,v)}, where κ(u,v) is the pairwise vertex connectivity between u,v. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov shows that a data structure of total size Õ(kn) can even be encoded as a Õ(k)-bit labeling scheme so that vertex-connectivity queries can be answered in Õ(k) time. The construction time is polynomial, but unspecified.

In this paper we address the top three complexity measures: Space, Query Time, and Construction Time. We give an Ω(kn)-bit lower bound on any vertex connectivity oracle. We construct an optimal-space connectivity oracle in max-flow time that answers queries in O(log n) time, independent of k.

The Power of Two Choices in Graphical Allocation

Nikhil Bansal (University of Michigan) and Ohad N. Feldheim (Hebrew University in Jerusalem)

Abstract: The graphical balls-into-bins process is a generalization of the classical 2-choice balls-into-bins process, where the bins correspond to vertices of an arbitrary underlying graph G. At each time step an edge of G is chosen uniformly at random, and a ball must be assigned to either of the two endpoints of this edge. The standard 2-choice process corresponds to the case of G = K_n.

For any k(n)-edge-connected, d(n)-regular graph on n vertices, and any number of balls, we give an allocation strategy that, with high probability, ensures a gap of O((d/k)log⁴ n log log n), between the load of any two bins. In particular, this implies polylogarithmic bounds for natural graphs such as cycles and tori, for which the classical greedy allocation strategy is conjectured to have a polynomial gap between the bin loads. For every graph G, we also show an Ω((d/k) + log n) lower bound on the gap achievable by any allocation strategy. This implies that our strategy achieves the optimal gap, up to polylogarithmic factors, for every graph G.

Our allocation algorithm is simple to implement and requires only O(log n ) time per allocation. It can be viewed as a more global version of the greedy strategy that compares average load on certain fixed sets of vertices, rather than on individual vertices. A key idea is to relate the problem of designing a good allocation strategy to that of finding suitable multi-commodity flows. To this end, we consider Räcke’s cut-based decomposition tree and define certain orthogonal flows on it.