2 papers
cs.CC2026
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…
cs.CC2024
Low-Degree Testing Over Grids
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
We study the question of local testability of low (constant) degree functions from a product domain to a field , where ${S_i} \subseteq…