Madhu Sudan | DeepAI

DeepAI AI Chat

Featured Co-authors

Venkatesan Guruswami
52 publications
Elchanan Mossel
46 publications
MohammadTaghi Hajiaghayi
42 publications
Bernhard Haeupler
36 publications
David Gamarnik
34 publications
Himanshu Tyagi
31 publications
Noah Golowich
27 publications
Soheil Behnezhad
25 publications
Mrinal Kumar
24 publications
Preetum Nakkiran
24 publications
Omri Ben-Eliezer
22 publications

∙ 11/08/2022

Streaming beyond sketching for Maximum Directed Cut

We give an O(√(n))-space single-pass 0.483-approximation streaming algor...

0 Raghuvansh R. Saxena, et al. ∙

∙ 07/14/2022

Streaming complexity of CSPs with randomly ordered constraints

We initiate a study of the streaming complexity of constraint satisfacti...

0 Raghuvansh R. Saxena, et al. ∙

∙ 05/05/2022

Streaming and Sketching Complexity of CSPs: A survey

In this survey we describe progress over the last decade or so in unders...

0 Madhu Sudan, et al. ∙

∙ 05/04/2022

Sketching Approximability of (Weak) Monarchy Predicates

We analyze the sketching approximability of constraint satisfaction prob...

0 Chi-Ning Chou, et al. ∙

∙ 07/13/2021

Information Spread with Error Correction

We study the process of information dispersal in a network with communic...

0 Omri Ben-Eliezer, et al. ∙

∙ 06/24/2021

Linear Space Streaming Lower Bounds for Approximating CSPs

We consider the approximability of constraint satisfaction problems in t...

0 Chi-Ning Chou, et al. ∙

∙ 05/04/2021

Streaming approximation resistance of every ordering CSP

An ordering constraint satisfaction problem (OCSP) is given by a positiv...

0 Noah Singer, et al. ∙

∙ 05/03/2021

Approximability of all finite CSPs in the dynamic streaming setting

A constraint satisfaction problem (CSP), Max-CSP( F), is specified by a ...

0 Chi-Ning Chou, et al. ∙

∙ 03/14/2021

Ideal-theoretic Explanation of Capacity-achieving Decoding

In this work, we present an abstract framework for some algebraic error-...

0 Siddharth Bhandari, et al. ∙

∙ 02/24/2021

Approximability of all Boolean CSPs in the dynamic streaming setting

A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...

0 Chi-Ning Chou, et al. ∙

∙ 01/23/2021

Point-hyperplane incidence geometry and the log-rank conjecture

We study the log-rank conjecture from the perspective of incidence geome...

0 Noah Singer, et al. ∙

∙ 12/02/2020

Decoding Multivariate Multiplicity Codes on Product Sets

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of ...

0 Siddharth Bhandari, et al. ∙

∙ 11/27/2020

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance

Trace reconstruction considers the task of recovering an unknown string ...

0 Elena Grigorescu, et al. ∙

∙ 10/02/2019

A Self-contained Analysis of the Lempel-Ziv Compression Algorithm

This article gives a self-contained analysis of the performance of the L...

0 Madhu Sudan, et al. ∙

∙ 09/08/2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

We present the first algorithm for maintaining a maximal independent set...

0 Soheil Behnezhad, et al. ∙

∙ 09/01/2019

Round Complexity of Common Randomness Generation: The Amortized Setting

We study the effect of rounds of interaction on the common randomness ge...

0 Noah Golowich, et al. ∙

∙ 04/21/2019

Communication for Generating Correlation: A Survey

The task of manipulating correlated random variables in a distributed se...

0 Madhu Sudan, et al. ∙

∙ 10/09/2018

Polar Codes with exponentially small error at finite block length

We show that the entire class of polar codes (up to a natural necessary ...

0 Jarosław Błasiok, et al. ∙

∙ 10/03/2018

Algorithmic Polarization for Hidden Markov Models

Using a mild variant of polar codes we design linear compression schemes...

0 Venkatesan Guruswami, et al. ∙

∙ 08/27/2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CR...

0 Mitali Bafna, et al. ∙

∙ 02/23/2018

Synchronization Strings: List Decoding for Insertions and Deletions

We study codes that are list-decodable under insertions and deletions. S...

0 Bernhard Haeupler, et al. ∙

∙ 02/08/2018

General Strong Polarization

Arı kan's exciting discovery of polar codes has provided an altogether n...

0 Jarosław Błasiok, et al. ∙

∙ 09/18/2017

Local decoding and testing of polynomials over grids

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that n-variate ...

0 Srikanth Srinivasan, et al. ∙

∙ 02/01/2014

Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem

We show that the Survey Propagation-guided decimation algorithm fails to...

0 David Gamarnik, et al. ∙