All reports by Author Noah Singer:

__
TR22-144
| 7th November 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming beyond sketching for Maximum Directed Cut

__
TR22-066
| 4th May 2022
__

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy#### On sketching approximations for symmetric Boolean CSPs

__
TR21-064
| 5th May 2021
__

Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming approximation resistance of every ordering CSP

Revisions: 3

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms.

... more >>>Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

A Boolean maximum constraint satisfaction problem, Max-CSP\((f)\), is specified by a predicate \(f:\{-1,1\}^k\to\{0,1\}\). An \(n\)-variable instance of Max-CSP\((f)\) consists of a list of constraints, each of which applies \(f\) to \(k\) distinct literals drawn from the \(n\) variables. For \(k=2\), Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>

Noah Singer, Madhu Sudan, Santhoshini Velusamy

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>