7 citations · 17 across the 12 of their papers we have counts for
13 papers
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…
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
For an arbitrary family of predicates and any , we prove a single-pass, linear-space streaming lower bound against the gap promise pro…
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…
Oblivious algorithms for the Max-AND Problem
Noah G. Singer
Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-AND problem. This generaliz…
On streaming approximation algorithms for constraint satisfaction problems
Noah G. Singer
In this thesis, we explore streaming algorithms for approximating constraint satisfaction problems (CSPs). The setup is roughly the following: A computer has limited memory space,…
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We give an -space single-pass -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on …
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 $\…
On sketching approximations for symmetric Boolean CSPs
Joanna Boyland, Michael Hwang, Tarun Prasad +2
A Boolean maximum constraint satisfaction problem, Max-CSP(), is specified by a predicate . An -variable instance of Max-CSP() consists of a list o…
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…
Point-hyperplane incidence geometry and the log-rank conjecture
Noah Singer, Madhu Sudan
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in that is cov…