4 papers
Nine lower bound conjectures on streaming approximation algorithms for CSPs
Noah G. Singer
In this column, we overview recent progress by many authors on understanding the approximability of constraint satisfaction problems (CSPs) in low-space streaming models. Inspired…
Sketching approximations and LP approximations for finite CSPs are related
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
We identify a connection between the approximability of CSPs in two models: (i) sublinear space streaming algorithms, and (ii) the basic LP relaxation. We show that whenever the ba…
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…