4 papers · 1 filter
Streaming Complexity Separations for Dense and Sparse Graphs
Yang P. Liu, Hoai-An Nguyen, Noah G. Singer +1
We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dens…
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al…
Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
Samuel Hwang, Noah G. Singer, Santhoshini Velusamy
In the maximum directed cut problem, the input is a directed graph , and the goal is to pick a partition of the vertices such that as many edg…
Streaming approximation resistance of every ordering CSP
Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
An ordering constraint satisfaction problem (OCSP) is defined by a family of predicates mapping permutations on to . An instance of Max-OCSP…