Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-005 | 21st January 2011 19:40

Testing Linear Properties: Some general themes

RSS-Feed




Revision #1
Authors: Madhu Sudan
Accepted on: 21st January 2011 19:40
Downloads: 1038
Keywords: 


Abstract:

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, these developments have contributed to the rich theory of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). In this survey, we focus on some of the general technical themes at work behind the many results in this area.



Changes to previous version:

Minor edits.


Paper:

TR11-005 | 20th January 2011 23:42

Testing Linear Properties: Some general themes





TR11-005
Authors: Madhu Sudan
Publication: 20th January 2011 23:42
Downloads: 1168
Keywords: 


Abstract:

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, these developments have contributed to the rich theory of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). In this survey, we focus on some of the general technical themes at work behind the many results in this area.



ISSN 1433-8092 | Imprint