Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Madhu Sudan:

TR10-199 | 14th December 2010
Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Symmetric LDPC codes are not necessarily locally testable

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check" (LDPC) code for it to be locally testable, but few LDPC ... more >>>

TR10-156 | 24th October 2010
Victor Chen, Madhu Sudan, Ning Xie

Property Testing via Set-Theoretic Operations

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference
of these two properties also testable?
We initiate a systematic study of these basic set-theoretic operations in the context of property
testing. As an application, we give a conceptually different proof that linearity is ... more >>>

TR10-155 | 14th October 2010
Brendan Juba, Madhu Sudan

Efficient Semantic Communication via Compatible Beliefs

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

ISSN 1433-8092 | Imprint