Noah G. Singer

activity

20212026

most citedStreaming complexity of CSPs with randomly ordered constraints

7 citations · 17 across the 12 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021★ 1 cited

On sketching approximations for symmetric Boolean CSPs

Joanna Boyland, Michael Hwang, Tarun Prasad +2

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 o…

cs.DS2021★ 1 cited

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 $F$ of predicates mapping permutations on ${1, \dots, k}$ to ${0, 1}$ . An instance of Max-OCSP…

math.CO2021★ 5 cited

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 $R^{d}$ that is cov…