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
- Papers on construction of and routing in switching networks:
- Noga Alon and Michael Capalbo,
Finding disjoint paths in expanders
deterministically and online.
- Paul Feldman, Joel Friedman
and Nichloas Pippenger,
Wide-sense
nonblocking networks.
- Sanjeev Arora,
Tom Leighton and
Bruce Maggs,
On-line algorithms
for path selection in a nonblocking network.
- Fan Chung, On concentrators, superconcentrators, generalizers,
and nonblocking networks.
- Papers on Selection Networks:
- Nicholas Pippenger, Selection networks.
- Shuji Jimbo and
Akira Maruoka,
A Method of Constructing Selection Networks with O(log n) Depth.
- Two classic papers on Sorting Networks:
- Miki Ajtai, Janos Komolos
and Endre Szemeredi, Sorting in c log n parallel steps
- Mike Paterson, Improved sorting networks with O (log N ) depth.
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.)