14 citations · 27 across the 20 of their papers we have counts for
6 papers · 1 filter
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…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
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…
Sketching approximability of all finite CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
A constraint satisfaction problem (CSP), , is specified by a finite set of constraints for positive int…
Approximability of all Boolean CSPs with linear sketches
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
In this work we consider the approximability of in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Sp…
Elementary analysis of isolated zeroes of a polynomial system
Mitali Bafna, Madhu Sudan, Santhoshini Velusamy +1
Wooley ({\em J. Number Theory}, 1996) gave an elementary proof of a Bezout like theorem allowing one to count the number of isolated integer roots of a system of polynomial equatio…