Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Santhoshini Velusamy:

TR21-011 | 13th February 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Classification of the streaming approximability of Boolean CSPs

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint