Noah G. Singer

activity

20212026

most citedStreaming complexity of CSPs with randomly ordered constraints

7 citations · 17 across the 12 of their papers we have counts for

collaborators

Showing 2022Show all

2 papers · 1 filter

cs.DS2022

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1

We give an $O (n)$ -space single-pass $0.483$ -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ …

cs.DS2022★ 7 cited

Streaming complexity of CSPs with randomly ordered constraints

Raghuvansh R. Saxena, Noah Singer, Madhu Sudan +1

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 $\…