The following papers are roughly organized (reverse) chronologically. You can also find my work on
DBLP and
Google Scholar. My ORCID
is 000000020076521X
.
Research papers

Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy
In submission
Abstract: "Streaming complexity of CSPs with randomly ordered constraints"
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 $\textsf{MaxDiCut}$, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$approximation of $\textsf{DiCut}$ requires $\Omega(\sqrt n)$ space with adversarial ordering, we show that with random ordering of constraints there exists a $0.48$approximation algorithm that only needs $O(\log n)$ space. We also give new algorithms for $\textsf{MaxDiCut}$ in variants of the adversarial ordering setting. Specifically, we give a twopass $O(\log n)$ space $0.48$approximation algorithm for general graphs and a singlepass $\tilde{O}(\sqrt n)$ space $0.48$approximation algorithm for bounded degree graphs.
On the negative side, we prove that CSPs where the satisfying assignments of the constraints support a onewise independent distribution require $\Omega(\sqrt n)$space for any nontrivial approximation, even when the constraints are randomly ordered. This was previously known only for adversarially ordered constraints. Extending the results to randomly ordered constraints requires switching the hard instances from a union of random matchings to simple ErdősRényi random (hyper)graphs and extending tools that can perform Fourier analysis on such instances.
The only CSP to have been considered previously with random ordering is $\textsf{MaxCut}$ where the ordering is not known to change the approximability. Specifically it is known to be as hard to approximate with random ordering as with adversarial ordering, for $o(\sqrt n)$ space algorithms. Our results show a richer variety of possibilities and motivate further study of CSPs with randomly ordered constraints.

On sketching approximations for symmetric Boolean CSPs
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy
APPROX 2022
Abstract: "On sketching approximations for symmetric Boolean CSPs"
A Boolean maximum constraint satisfaction problem, $\textsf{MaxCSP}(f)$, is specified by a predicate $f:{1,1}^k\to{0,1}$. An $n$variable instance of $\textsf{MaxCSP}(f)$ consists of a list ofconstraints, 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 characterizing the $\sqrt n$space streaming approximability of every predicate. For $k \geq 3$, Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general dichotomy theorem for $\sqrt n$space sketching algorithms: For every $f$, there exists $\alpha(f)\in (0,1]$ such that for every $\epsilon>0$, $\textsf{MaxCSP}(f)$ is $(\alpha(f)\epsilon)$approximable by an $O(\log n)$space linear sketching algorithm, but $(\alpha(f)+\epsilon)$approximation sketching algorithms require $\Omega(\sqrt{n})$ space.
In this work, we give closedform expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting $\alpha’_k = 2^{(k1)} (1k^{2})^{(k1)/2}$, we show that for odd $k \geq 3$, $\alpha(k\textsf{AND}) = \alpha’_k$, and for even $k \geq 2$, $\alpha(k\textsf{AND}) = 2\alpha’_{k+1}$. Thus, for every $k$, $k\textsf{AND}$ can be $(2o(1))2^{k}$approximated by $O(\log n)$space sketching algorithms; we contrast this with a lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy [STOC 2022] implying that streaming $(2+\epsilon)\cdot2^{k}$approximations require $\Omega(n)$ space! We also resolve the ratio for the “atleast$(k1)$$1$’s” function for all even $k$; the “exactly$\frac{k+1}2$$1$’s” function for odd $k \in {3,\ldots,51}$; and fifteen other functions. We stress here that for general $f$, the dichotomy theorem in [CGSV21] only implies that $\alpha(f)$ can be computed to arbitrary precision in $\textbf{PSPACE}$, and thus closedform expressions need not have existed a priori. Our analyses involve identifying and exploiting structural “saddlepoint” properties of this dichotomy.
Separately, for all threshold functions, we give optimal “biasbased” approximation algorithms generalizing [CGV20] while simplifying [CGSV21]. Finally, we investigate the $\sqrt n$space streaming lower bounds in [CGSV21], and show that they are incomplete for $\textsf{3AND}$, i.e., they fail to rule out $(\alpha(\textsf{3AND})\epsilon)$approximations in $o(\sqrt n)$ space.

Streaming approximation resistance of every ordering CSP
Noah Singer, Madhu Sudan, and Santhoshini Velusamy
APPROX 2021
Abstract: "Streaming approximation resistance of every ordering CSP"
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 $\textsf{MaxOCSP}(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number of constraints that are satisfied, where a constraint specifies a sequence of $k$ distinct variables and the constraint is satisfied by an ordering on the $n$ variables if the ordering induced on the $k$ variables in the constraint satisfies $\Pi$. Ordering constraint satisfaction problems capture natural problems including “Maximum acyclic subgraph (MAS)” and “Betweenness”.
In this work we consider the task of approximating the maximum number of satisfiable constraints in the (singlepass) streaming setting, where an instance is presented as a stream of constraints. We show that for every $\Pi$, $\textsf{MaxOCSP}(\Pi)$ is approximationresistant to $o(n)$space streaming algorithms, i.e., algorithms using $o(n)$ space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS, our result shows that for every $\epsilon>0$, MAS is not $(1/2+\epsilon)$approximable in $o(n)$ space. The previous best inapproximability result, due to Guruswami and Tao [APPROX 2019], only ruled out a $3/4$approximation in $o(\sqrt n)$ space.
Our results build on recent works of Chou, Golovnev, Sudan, Velingker, and Velusamy who show tight, linearspace inapproximability results for a broad class of (nonordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate CSPs from any given OCSP, and applying their work to this family of CSPs. To convert the resulting hardness results for CSPs back to our OCSP, we show that the hard instances from this earlier work have the following “smallset expansion” property: If the CSP instance is viewed as a hypergraph in the natural way, then for every partition of the hypergraph into small blocks most of the hyperedges are incident on vertices from distinct blocks. By exploiting this combinatorial property, in combination with the hardness results of the resulting families of CSPs, we give optimal inapproximability results for all OCSPs.

Pointhyperplane incidence geometry and the logrank conjecture
Noah Singer and Madhu Sudan
ACM Transactions on Computation Theory
Abstract: "Pointhyperplane incidence geometry and the logrank conjecture"
We study the logrank conjecture from the perspective of pointhyperplane incidence geometry. We formulate the following conjecture: Given a point set in $\mathbb{R}^d$ that is covered by constantsized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., $2^{{\mathrm{polylog}(d)}}$ fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the pointhyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linearalgebraically as follows: Any rank$d$ matrix containing at most $O(1)$ distinct entries in each column contains a submatrix of fractional size $2^{{\mathrm{polylog}(d)}}$, in which each column is constant. We prove that our conjecture is equivalent to the logrank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel $k$partitions to bounds for parallel $(k1)$partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel.
Motivated by the connections above, we revisit wellstudied questions in pointhyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density $\Omega(\epsilon^{2d}/d)$ in any $d$dimensional configuration with incidence density $\epsilon$, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upperbound construction of Apfelbaum and Sharir [J. Discrete Math. 2007], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is $\Omega(1/\sqrt d)$. Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density $\Omega(1)$ and complete bipartite subgraph density $2^{\Omega(\sqrt d)}$, and pose several questions for this special case in the alternative language of extremal set combinatorics.
Our framework and results may help shed light on the difficulty of improving Lovett’s $\tilde{O}(\sqrt{\mathrm{rank}(f)})$ bound [J. ACM. 2014] for the logrank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel $3$partitioned configurations which beat our generic bounds for unstructured configurations.
Other writings

On streaming approximation algorithms for constraint satisfaction problems
Noah Singer
Harvard College Senior Thesis
Hoopes Prize (Harvard College)
Abstract: "On streaming approximation algorithms for constraint satisfaction problems"
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, sees a long “stream” of local constraints on a set of variables, and tries to estimate how many of the constraints may be simultaneously satisfied. The past ten years have seen a number of works in this area, and this thesis includes both expository material and novel contributions. Throughout, we emphasize connections to the broader theories of CSPs, approximability, and streaming models, and highlight interesting open problems.
The first part of our thesis is expository: We present aspects of previous works that completely characterize the approximability of specific CSPs like MaxCut and MaxDicut with $\sqrt{n}$space streaming algorithm (on $n$variable instances), while characterizing the approximability of all CSPs in $\sqrt n$ space in the special case of “composable” (i.e., sketching) algorithms, and of a particular subclass of CSPs with linearspace streaming algorithms.
In the second part of the thesis, we present two of our own joint works. We begin with a work with Madhu Sudan and Santhoshini Velusamy in which we prove linearspace streaming approximationresistance for all ordering CSPs (OCSPs), which are “CSPlike” problems maximizing over sets of permutations. Previous works considered the maximum acyclic subgraph (MAS) problem, the prototypical OCSP; even for MAS, we improve on both the inapproximability factor and the space bound. Next, we present joint work with Joanna Boyland, Michael Hwang, Tarun Prasad, and Santhoshini Velusamy in which we investigate the $\sqrt n$space streaming approximability of symmetric Boolean CSPs with negations. In particular, we give explicit $\sqrt n$space sketching approximability ratios for several families of CSPs, including $\textsf{Max}k\textsf{AND}$ develop simpler optimal sketching approximation algorithms for threshold predicates; and show that previous streaming lower bounds are “incomplete” in that they fail to characterize the $\sqrt n$space streaming approximability of $\textsf{Max3AND}$.

CS 121.5 Notes, Fall 2019
Noah Singer
Notes from advanced section in CS 121: Introduction to Theoretical Computer Science (Fall 2019)