23 citations · 148 across the 41 of their papers we have counts for
54 papers
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
Kuan Cheng, Elena Grigorescu, Xin Li +2
The goal of the trace reconstruction problem is to recover a string given many independent {\em traces} of , where a trace is a subsequence obtained from deletin…
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…
Is this correct? Let's check!
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel +1
Societal accumulation of knowledge is a complex process. The correctness of new units of knowledge depends not only on the correctness of new reasoning, but also on the correctness…
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We give an -space single-pass -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on …
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan +1
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 $\…
Streaming and Sketching Complexity of CSPs: A survey
Madhu Sudan
In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and…