Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR21-011 | 14th March 2022 20:35

Approximability of all Boolean CSPs with linear sketches

RSS-Feed




Revision #4
Authors: Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Accepted on: 14th March 2022 20:35
Downloads: 166
Keywords: 


Abstract:

A Boolean constraint satisfaction problem (CSP), Max-CSP($f$), is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal is to compute the maximum number of constraints that can be satisfied by a Boolean assignment to the $n$~variables. In the $(\gamma,\beta)$-approximation version of the problem for parameters $\gamma \geq \beta \in [0,1]$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied.

In this work, we consider the approximability of Max-CSP($f$) in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given $f$, $\gamma$, and $\beta$ we show that either (1) the $(\gamma,\beta)$-approximation version of Max-CSP($f$) has a linear sketching algorithm using $O(\log n)$ space, or (2) for every $\epsilon > 0$ the $(\gamma-\epsilon,\beta+\epsilon)$-approximation version of Max-CSP($f$) requires $\Omega(\sqrt{n})$ space for any sketching algorithm. We also prove lower bounds against streaming algorithms for several CSPs. In particular, we recover the streaming dichotomy of [Chou-Golovnev-Velusamy FOCS'20] for $k=2$ and show streaming approximation resistance of all CSPs for which $f^{-1}(1)$ supports a distribution with uniform marginals.

Our positive results show wider applicability of bias-based algorithms used previously by [Guruswami-Velingker-Velusamy APPROX'17] and [Chou-Golovnev-Velusamy FOCS'20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [Kapralov-Khanna-Sudan SODA'15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.



Changes to previous version:

The previous version claimed Theorem 1.1 (the dichotomy theorem) in the dynamic streaming setting. The new version replaces it with a dichotomy theorem for approximability of CSPs with sketching algorithms.


Revision #3 to TR21-011 | 14th July 2021 21:01

Approximability of all Boolean CSPs in the dynamic streaming setting





Revision #3
Authors: Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Accepted on: 14th July 2021 21:01
Downloads: 286
Keywords: 


Abstract:

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal is to compute the maximum number of constraints that can be satisfied by a Boolean assignment to the $n$~variables. In the $(\gamma,\beta)$-approximation version of the problem for parameters $\gamma \geq \beta \in [0,1]$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied.

In this work we consider the approximability of Max-CSP$(f)$ in the (dynamic) streaming setting, where constraints are inserted (and may also be deleted in the dynamic setting) one at a time. We completely characterize the approximability of all Boolean CSPs in the dynamic streaming setting. Specifically, given $f$, $\gamma$ and $\beta$ we show that either (1) the $(\gamma,\beta)$-approximation version of Max-CSP$(f)$ has a probabilistic dynamic streaming algorithm using $O(\log n)$ space, or (2) for every $\varepsilon > 0$ the $(\gamma-\varepsilon,\beta+\varepsilon)$-approximation version of Max-CSP$(f)$ requires $\Omega(\sqrt{n})$ space for probabilistic dynamic streaming algorithms. We also extend previously known results in the insertion-only setting to a wide variety of cases, and in particular the case of $k=2$ where we get a dichotomy and the case when the satisfying assignments of $f$ support a distribution on $\{-1,1\}^k$ with uniform marginals.

Our positive results show wider applicability of bias-based algorithms used previously by [Guruswami-Velingker-Velusamy APPROX'17] and
[Chou-Golovnev-Velusamy FOCS'20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [Kapralov-Khanna-Sudan SODA'15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.


Revision #2 to TR21-011 | 14th April 2021 18:50

Approximability of all Boolean CSPs in the dynamic streaming setting





Revision #2
Authors: Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Accepted on: 14th April 2021 18:50
Downloads: 421
Keywords: 


Abstract:

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal is to compute the maximum number of constraints that can be satisfied by a Boolean assignment to the $n$~variables. In the $(\gamma,\beta)$-approximation version of the problem for parameters $\gamma \geq \beta \in [0,1]$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied.

In this work we consider the approximability of Max-CSP$(f)$ in the (dynamic) streaming setting, where constraints are inserted (and may also be deleted in the dynamic setting) one at a time. We completely characterize the approximability of all Boolean CSPs in the dynamic streaming setting. Specifically, given $f$, $\gamma$ and $\beta$ we show that either (1) the $(\gamma,\beta)$-approximation version of Max-CSP$(f)$ has a probabilistic dynamic streaming algorithm using $O(\log n)$ space, or (2) for every $\varepsilon > 0$ the $(\gamma-\varepsilon,\beta+\varepsilon)$-approximation version of Max-CSP$(f)$ requires $\Omega(\sqrt{n})$ space for probabilistic dynamic streaming algorithms. We also extend previously known results in the insertion-only setting to a wide variety of cases, and in particular the case of $k=2$ where we get a dichotomy and the case when the satisfying assignments of $f$ support a distribution on $\{-1,1\}^k$ with uniform marginals.

Our positive results show wider applicability of bias-based algorithms used previously by [Guruswami-Velingker-Velusamy APPROX'17] and [Chou-Golovnev-Velusamy FOCS'20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [Kapralov-Khanna-Sudan SODA'15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.



Changes to previous version:

This version of the paper replaces the previous version (now withdrawn). The previous version claimed Theorem 1.1 in the insertion-only streaming setting, the new version proves Theorem 1.1 in the dynamic streaming setting (and also extends previously known results in the insertion-only setting to a wide variety of cases). The status of Theorem 1.1 in the previous version is currently open.


Revision #1 to TR21-011 | 24th February 2021 16:36

Classification of the streaming approximability of Boolean CSPs





Revision #1
Authors: Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Accepted on: 24th February 2021 16:36
Downloads: 391
Keywords: 


Abstract:

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal is to compute the maximum number of constraints that can be satisfied by a Boolean assignment to the $n$ variables. In the $(\gamma,\beta)$-approximation version of the problem for parameters $\gamma \geq \beta \in [0,1]$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied.

In this work we completely characterize the approximability of all Boolean CSPs in the streaming model. Specifically, given $f$, $\gamma$ and $\beta$ we show that either (1) the $(\gamma,\beta)$-approximation version of Max-CSP$(f)$ has a probabilistic streaming algorithm using $O(\log n)$ space, or (2) for every $\epsilon > 0$ the $(\gamma-\epsilon,\beta+\epsilon)$-approximation version of Max-CSP$(f)$ requires $\Omega(\sqrt{n})$ space for probabilistic streaming algorithms. Previously such a separation was known only for $k=2$. We stress that for $k=2$, there are only finitely many distinct problems to consider.

Our positive results show wider applicability of bias-based algorithms used previously by [Guruswami-Velingker-Velusamy APPROX'17], [Chou-Golovnev-Velusamy FOCS'20] by giving a systematic way to explore biases. Our negative results combine the Fourier analytic methods of [Kapralov-Khanna-Sudan SODA'15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.



Changes to previous version:

Improved the presentation.


Paper:

TR21-011 | 13th February 2021 20:01

Classification of the streaming approximability of Boolean CSPs


Abstract:

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal is to compute the maximum number of constraints that can be satisfied by a Boolean assignment to the $n$ variables. In the $(\gamma,\beta)$-approximation version of the problem for parameters $\gamma \geq \beta \in [0,1]$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied.

In this work we completely characterize the approximability of all Boolean CSPs in the streaming model. Specifically, given $f$, $\gamma$ and $\beta$ we show that either (1) the $(\gamma,\beta)$-approximation version of Max-CSP$(f)$ has a probabilistic streaming algorithm using $O(\log n)$ space, or (2) for every $\epsilon > 0$ the $(\gamma-\epsilon,\beta+\epsilon)$-approximation version of Max-CSP$(f)$ requires $\Omega(\sqrt{n})$ space for probabilistic streaming algorithms. Previously such a separation was known only for $k=2$. We stress that for $k=2$, there are only finitely many distinct problems to consider.

Our positive results show wider applicability of bias-based algorithms used previously by [Guruswami-Velingker-Velusamy APPROX'17], [Chou-Golovnev-Velusamy FOCS'20] by giving a systematic way to explore biases. Our negative results combine the Fourier analytic methods of [Kapralov-Khanna-Sudan SODA'15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.


Comment(s):

Comment #1 to TR21-011 | 20th March 2021 22:22

Errata for Classification of the streaming approximability of Boolean CSPs ContactAdd CommentRSS-Feed

Authors: Chi-Ning Chou, Alexander Golovnev, Madhu Sudan
Accepted on: 20th March 2021 22:22
Keywords: 


Comment:

We regret that due to a fatal error in this paper, we are retracting the results of this paper. We are grateful to Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, and Huacheng Yu, for pointing out the error (in the proof of Claim 5.6). While some of the results (including the algorithmic result (Theorem 4.1) and the lower bound on the communication complexity of the RMD problem (Theorem 5.3)) continue to hold, the dichotomy claim (Theorem 1.1) is now open. We will post an updated version of this paper shortly.




ISSN 1433-8092 | Imprint