Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Noah Singer:

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