ECCC-Report TR11-005https://eccc.weizmann.ac.il/report/2011/005Comments and Revisions published for TR11-005en-usFri, 21 Jan 2011 19:40:02 +0200
Revision 1
| Testing Linear Properties: Some general themes |
Madhu Sudan
https://eccc.weizmann.ac.il/report/2011/005#revision1The 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.Fri, 21 Jan 2011 19:40:02 +0200https://eccc.weizmann.ac.il/report/2011/005#revision1
Paper TR11-005
| Testing Linear Properties: Some general themes |
Madhu Sudan
https://eccc.weizmann.ac.il/report/2011/005The 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.Thu, 20 Jan 2011 23:42:39 +0200https://eccc.weizmann.ac.il/report/2011/005