Note: This document will be updated in the next week or so. However, feel free to read through if you want to get a head start (none of the papers mentioned here will be removed later).

Introduction

Listed below are some papers that are suitable for presentations (unless mentioned otherwise) along with some background information. Another good resource for papers is to browse through the bibliography of the papers mentioned below.

Expanders

Undirected Connectivity

Explicit Constructions

Applications of Expanders in Switching Networks

Pseudorandom Objects

Expander Codes

We will talk about the basics of expander codes. However, we will not cover linear-time encoding and decoding algorithms for such codes. These algorithms were first obtained by Dan Spielman in his paper titled Linear-time encodable and decodable error-correcting codes.

Property Testing

Codeword Testing

Codeword testing was the genesis of property testing.

Lower Bounds

Testing Graph Properties

Sublinear Algorithms

Sublinear algorithms are the (functional) version of property testing where one is also interested in keeping in the running time low. Recall that in property testing, we are generally concerned with the query complexity but do not necessarily pay much attention to the running time.

Locally Decodable Codes

These are objects that are related to (and in some sense complementary to) codeword testers.

More options?

Looking for some other paper? Go through the publications pages of the people mentioned above and select one of their property testing papers. (If you do take this route, please check with Hung or Atri to make sure your selection is OK.)