English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the approximability of constraint satisfaction problems in thestreaming setting. For every constraint satisfaction problem (CSP) on $n$variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over thetrivial approximability by a factor of $q$ requires $\Omega(n)$ space even oninstances with $O(n)$ constraints. We also identify a broad subclass ofproblems for which any improvement over the trivial approximability requires$\Omega(n)$ space. The key technical core is an optimal,$q^{-(k-1)}$-inapproximability for the \textsf{Max $k$-LIN}-$\bmod\; q$problem, which is the Max CSP problem where every constraint is given by asystem of $k-1$ linear equations $\bmod\; q$ over $k$ variables. Our workbuilds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC2019) who showed a linear lower bound on any non-trivial approximation of theMaxCut problem in graphs. MaxCut corresponds roughly to the case of \textsf{Max$k$-LIN}-$\bmod\; q$ with ${k=q=2}$. For general CSPs in the streaming setting,prior results only yielded $\Omega(\sqrt{n})$ space bounds. In particular nolinear space lower bound was known for an approximation factor less than $1/2$for {\em any} CSP. Extending the work of Kapralov and Krachun to \textsf{Max$k$-LIN}-$\bmod\; q$ to $k>2$ and $q>2$ (while getting optimal hardnessresults) is the main technical contribution of this work. Each one of theseextensions provides non-trivial technical challenges that we overcome in thiswork.

Linear Space Streaming Lower Bounds for Approximating CSPs