Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOM ORDERING OF CONSTRAINTS:
Reports tagged with random ordering of constraints:
TR22-100 | 14th July 2022
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

#### Streaming complexity of CSPs with randomly ordered constraints

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of DICUT requires $\Omega(\sqrt{n})$ space with ... more >>>

ISSN 1433-8092 | Imprint