Single-Pass Streaming CSPs via Two-Tier Sampling
arXiv:2604.01575v1 Announce Type: new Abstract: We study the maximum constraint satisfaction problem, Max-CSP, in the streaming setting. Given $n$ variables, the constraints arrive sequentially in an arbitrary order, with each constraint involving only a small subset of the variables. The objective is to approximate the maximum fraction of constraints that can be satisfied by an optimal assignment in a single pass. The problem admits a trivial near-optimal solution with $O(n)$ space, so the major open problem in the literature has been the best approximation achievable when limiting the space to $o(n)$. The answer to the question above depends heavily on the CSP instance at hand. The integrality gap $\alpha$ of an LP relaxation, known as the BasicLP, plays a central role. In particular, a
View PDF
Abstract:We study the maximum constraint satisfaction problem, Max-CSP, in the streaming setting. Given $n$ variables, the constraints arrive sequentially in an arbitrary order, with each constraint involving only a small subset of the variables. The objective is to approximate the maximum fraction of constraints that can be satisfied by an optimal assignment in a single pass. The problem admits a trivial near-optimal solution with $O(n)$ space, so the major open problem in the literature has been the best approximation achievable when limiting the space to $o(n)$. The answer to the question above depends heavily on the CSP instance at hand. The integrality gap $\alpha$ of an LP relaxation, known as the BasicLP, plays a central role. In particular, a major conjecture of the area is that in the single-pass streaming setting, for any fixed $\varepsilon > 0$, (i) an $(\alpha-\varepsilon)$-approximation can be achieved with $o(n)$ space, and (ii) any $(\alpha+\varepsilon)$-approximation requires $\Omega(n)$ space. In this work, we fully resolve the first side of the conjecture by proving that an $(\alpha - \varepsilon)$-approximation of Max-CSP can indeed be achieved using $n^{1-\Omega_\varepsilon(1)}$ space and in a single pass. Given that Max-DiCut is a special case of Max-CSP, our algorithm fully recovers the recent result of [ABFS26, STOC'26] via a completely different algorithm and proof. On a technical level, our algorithm simulates a suitable local algorithm on a reduced graph using a technique that we call two-tier sampling: the algorithm combines both edge sampling and vertex sampling to handle high- and low-degree vertices at the same time.
Subjects:
Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2604.01575 [cs.DS]
(or arXiv:2604.01575v1 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2604.01575
arXiv-issued DOI via DataCite (pending registration)
Submission history
From: Amir Azarmehr [view email] [v1] Thu, 2 Apr 2026 03:42:01 UTC (40 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
More about
announcestudyarxiv
Simple parallel estimation of the partition ratio for Gibbs distributions
arXiv:2505.18324v2 Announce Type: replace-cross Abstract: We consider the problem of estimating the partition function $Z(\beta)=\sum_x \exp(\beta(H(x))$ of a Gibbs distribution with the Hamiltonian $H:\Omega\rightarrow\{0\}\cup[1,n]$. As shown in [Harris & Kolmogorov 2024], the log-ratio $q=\ln (Z(\beta_{\max})/Z(\beta_{\min}))$ can be estimated with accuracy $\epsilon$ using $O(\frac{q \log n}{\epsilon^2})$ calls to an oracle that produces a sample from the Gibbs distribution for parameter $\beta\in[\beta_{\min},\beta_{\max}]$. That algorithm is inherently sequential, or {\em adaptive}: the queried values of $\beta$ depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs $O( q (\log^2 n) (\log q + \log \log n + \epsilon^{-2}) )$ samples.
Online Graph Coloring for $k$-Colorable Graphs
arXiv:2511.16100v2 Announce Type: replace Abstract: We study the problem of online graph coloring for $k$-colorable graphs. The best previously known deterministic algorithm uses $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors for general $k$ and $\widetilde{O}(n^{5/6})$ colors for $k = 4$, both given by Kierstead in 1998. In this paper, we finally break this barrier, achieving the first major improvement in nearly three decades. Our results are summarized as follows: (1) $k \geq 5$ case. We provide a deterministic online algorithm to color $k$-colorable graphs with $\widetilde{O}(n^{1-\frac{1}{k(k-1)/2}})$ colors, significantly improving the current upper bound of $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors. Our algorithm also matches the best-known bound for $k = 4$ ($\widetilde{O}(n^{5/6})$ c
Zero-Freeness of the Hard-Core Model with Bounded Connective Constant
arXiv:2604.02746v1 Announce Type: cross Abstract: We study the zero-free regions of the partition function of the hard-core model on finite graphs and their implications for the analyticity of the free energy on infinite lattices. Classically, zero-freeness results have been established up to the tree uniqueness threshold $\lambda_c(\Delta-1)$ determined by the maximum degree $\Delta$. However, for many graph classes, such as regular lattices, the connective constant $\sigma$ provides a more precise measure of structural complexity than the maximum degree. While recent approximation algorithms based on correlation decay and Markov chain Monte Carlo have successfully exploited the connective constant to improve the threshold to $\lambda_c(\sigma)$, analogous results for complex zero-freenes
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
More in Research Papers
Online Graph Coloring for $k$-Colorable Graphs
arXiv:2511.16100v2 Announce Type: replace Abstract: We study the problem of online graph coloring for $k$-colorable graphs. The best previously known deterministic algorithm uses $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors for general $k$ and $\widetilde{O}(n^{5/6})$ colors for $k = 4$, both given by Kierstead in 1998. In this paper, we finally break this barrier, achieving the first major improvement in nearly three decades. Our results are summarized as follows: (1) $k \geq 5$ case. We provide a deterministic online algorithm to color $k$-colorable graphs with $\widetilde{O}(n^{1-\frac{1}{k(k-1)/2}})$ colors, significantly improving the current upper bound of $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors. Our algorithm also matches the best-known bound for $k = 4$ ($\widetilde{O}(n^{5/6})$ c
Zero-Freeness of the Hard-Core Model with Bounded Connective Constant
arXiv:2604.02746v1 Announce Type: cross Abstract: We study the zero-free regions of the partition function of the hard-core model on finite graphs and their implications for the analyticity of the free energy on infinite lattices. Classically, zero-freeness results have been established up to the tree uniqueness threshold $\lambda_c(\Delta-1)$ determined by the maximum degree $\Delta$. However, for many graph classes, such as regular lattices, the connective constant $\sigma$ provides a more precise measure of structural complexity than the maximum degree. While recent approximation algorithms based on correlation decay and Markov chain Monte Carlo have successfully exploited the connective constant to improve the threshold to $\lambda_c(\sigma)$, analogous results for complex zero-freenes
Stochastic Function Certification with Correlations
arXiv:2604.02611v1 Announce Type: new Abstract: We study the Stochastic Boolean Function Certification (SBFC) problem, where we are given $n$ Bernoulli random variables $\{X_e: e \in U\}$ on a ground set $U$ of $n$ elements with joint distribution $p$, a Boolean function $f: 2^U \to \{0, 1\}$, and an (unknown) scenario $S = \{e \in U: X_e = 1\}$ of active elements sampled from $p$. We seek to probe the elements one-at-a-time to reveal if they are active until we can certify $f(S) = 1$, while minimizing the expected number of probes. Unlike most previous results that assume independence, we study correlated distributions $p$ and give approximation algorithms for several classes of functions $f$. When $f(S)$ is the indicator function for whether $S$ is the spanning set of a given matroid, ou
Non-Signaling Locality Lower Bounds for Dominating Set
arXiv:2604.02582v1 Announce Type: new Abstract: Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps between known algorithms and lower bounds. Chang and Li prove an $\Omega(\log n)$-locality lower bound for a constant factor approximation, while Kuhn--Moscibroda--Wattenhofer gave an algorithm beating this bound beyond $\log \Delta$-approximation, along with a weaker lower bound for this degree-dependent setting scaling roughly with $\min\{\log \Delta/\log\log \Delta,\sqrt{\log n/\log\log n}\}$. Unfortunately, this latter bound is weak for small $\Delta$, and never recovers the Chang--Li bound, leaving central questions: does $O(\log \Delta)$-approximation require
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!