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 2021 · cs.DSShow all

2 papers · 2 filters

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…