NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing

Serge Gaspers, Tao Zixu He, Simon Mackenzie

We prove that computing the deterministic communication complexity D(f) of a Boolean function is NP-hard in the standard protocol-tree model, answering, independently and concurrently with Hirahara-Llango-Loff (arXiv:2507.10426), a question first posed by Yao (1979). Our reduction builds and expands on a suite of structural "interlacing" lemmas introduced by Mackenzie and Saffidine (arXiv:2411.19003); these lemmas can be reused as black boxes in future lower-bound constructions. The instances produced by our reduction admit optimal protocols for self-similar constructions with strong structural properties, giving a flexible framework for the design of reductions showing NP-hardness of deciding the communication complexity of a Boolean matrix. This complements the work by Hirahara, Ilango, and Loff, which establishes NP-hardness in the same model via a different route; our analysis additionally yields reusable structural guarantees and underpins further consequences concerning inapproximability. Because the gadgets in our construction are self-similar, they can be recursively embedded. We sketch how this yields, under the Exponential-Time Hypothesis, an additive inapproximability gap that grows without bound. Furthermore we outline a route toward NP-hardness of approximating D(f) within a fixed constant additive error. Full details of the ETH-based inapproximability results will appear in a future version. Beyond settling the complexity of deterministic communication complexity itself, the modular framework we develop opens the door to a wider class of reductions and, we believe, will prove useful in tackling other long-standing questions in communication complexity.

[arXiv]

Fair Allocation of Divisible Goods under Non-Linear Valuations

Haris Aziz, Zixu He, Xinhang Lu, Kaiyang Zhou

AAMAS 2025 Spotlight

This paper addresses the division of homogeneous divisible goods among agents with non-linear valuations. We propose an algorithm that guarantees a \(\frac{1}{2n-1}\)-MMS allocation for \(n\) agents with arbitrary non-decreasing valuations and establish the impossibility of exceeding a \(1/n\)-MMS approximation, even with one-breakpoint piecewise-constant valuations. For \(n \leq 3\), the \(1/n\) ratio is proven tight. On envy-freeness, we show that verifying the existence of an EF and Pareto optimal (PO) allocation is NP-hard for \(n\) agents and at least three goods, even with one-breakpoint piecewise-constant valuations. We complement this with a polynomial-time algorithm for checking EF and PO allocations for a single divisible good with piecewise-linear valuations.

[PDF]

A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from \(O(1.7272^n)\) to \(O(1.7207^n)\) and from \(O(1.6262^n)\) to \(O(1.6225^n)\) respectively.

[arXiv] [Code]

A Faster Algorithm for Vertex Cover: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Tao Zixu He, Simon Mackenzie, Tiankuang Zhang

This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method for automatically generating branching rules through a systematic case analysis of local structures. Second, we develop a new technique for analyzing randomized branching algorithms using the \MCfull method, offering greater flexibility in formulating branching rules. By combining these innovations with additional techniques, we obtain the fastest known randomized algorithms in different parameters for the Vertex Cover problem on graphs with bounded degree (up to 6) and on general graphs. For example, our algorithm solves Vertex Cover on subcubic graphs in \(O(1.07625^n)\) time and \(O(1.13132^k)\) time, respectively. For graphs with maximum degree 4, we achieve running times of \(O(1.13735^n)\) and \(O(1.21103^k)\), while for general graphs we achieve \(O(1.25281^k)\).