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

• One of the major results in theoretical computer science in this century is the paper titled Undirected Connectivity in Log-space by Omer Reingold. Reingold showed that verifying whether two nodes in an undirected graph with n vertices can be found in O(log n) space. The basic idea in the algorithm is to "turn" it into an expander. The ideas in this paper also inspired Irit Dinur's new proof of the PCP theorem, which we will cover next semester in detail. Reingold's paper won the best paper award at STOC 2005. In an interesting twist, Vladimir Trifinov, then a Ph.D. student at University of Texas at Austin presented an O(log n*loglog n) space algorithms for the same problem also at STOC 2005. His paper won the best student paper award at STOC 05. Here is a SIAM News article by Sara Robinson on this result (along with some background on expanders and undirected connectivity).
• An alternate proof of Reingold's result appears in a paper by Eyal Rozenman and Salil Vadhan titled Derandomized Squaring of Graphs.

Explicit Constructions

• The paper titled An Elementary Construction of Constant-Degree Expanders by Noga Alon, Oded Schwartz and Asaf Shapira.

Applications of Expanders in Switching Networks

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

Pseudorandom Objects

• The survey by Salil Vadhan titled The Unified Theory of Pseudorandomness gives a common "language" to interpret various pseudorandom objects such as Pseudorandom generator, List-decodable codes, Expanders, Extractors, Samplers and "Hardness amplifiers." The survey is definition heavy but light on proofs.

Expander Codes

Property Testing

Codeword Testing

• Testers for Reed-Muller codes were the building blocks of the original PCP constructions. In some sense the most general tester appears in the paper by Tali Kaufman and Dana Ron titled Testing Polynomials over General Fields. You might also be interested in a related paper. Warning: this later paper uses more terminology and ideas from coding theory in its proofs. Both these papers use the same proof framework that was crystallized in the paper by Ronitt Rubinfeld and Madhu Sudan titled Robust Characterizations of Polynomials and their Applications to Program Testing.
• A paper by Tali Kaufman and Simon Litsyn titled Almost Orthogonal Linear Codes are Locally Testable gives codeword testers for a family of codes including the BCH codes. (Warning: again a lot of coding theory stuff is used.) An interesting aspect of the proof is that the technique is totally different from the Rubinfeld-Sudan framework.
• This paper talks about "tolerant" codeword testing. The paper also gives a survey of some of the known techniques to construct "locally testable codes." If you present the paper, you'll also have to present one of these techniques. (Talk to Atri or Hung once you have chosen the technique.)

Lower Bounds

• The paper by Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova titled Some 3CNF properties are hard to test presents some natural classes of properties which cannot be tested with few queries. The proofs in the paper are very nice and elegant.
• The paper by Eli Ben-Sasson, Oded Goldreich and Madhu Sudan titled Bounds on 2-query codeword testing.

Testing Graph Properties

• The classic: Property Testing and its Connection to Learning and Approximation (long version) by Oded Goldreich and Shafi Goldwasser. This paper defined the notion of property testing.
• The paper by Noga Alon, Eldar Fischer, Ilan Newman and Asaf Shapira titled A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. (The name is pretty descriptive.)

Sublinear Algorithms

• The paper by Bernard Chazelle, Ronitt Rubinfeld and Luca Trevisan titled Approximating the Minimum Spanning Tree Weight in Sublinear Time. (This is suitable for a single speaker presentation.)

Locally Decodable Codes

• The breakthrough work by Sergey Yekhanin titled Towards 3-query locally decodable codes of subexponential length. Uber-cool stuff with Mersenne primes thrown in for good measure. This paper won the both the best paper and best student paper award at STOC 2007. Yekhanin's thesis won the ACM Doctoral Dissertation Award in 2007.
• An earlier paper by Sergey Yekhanin and David Woodruff titled A geometric approach to information theoretic private information retrieval gave a nice common theme behind almost all the previous locally decodable codes (before Yekhanin's breakthrough work above).

More options?