| Preface |
| Committees |
| Ron Book Prize for Best Student Paper |
| 2002 Best Paper Award |
| Joint Session with STOC 2002 / Session 1： |
| Resolution Lower Bounds for the Weak Pigeonhole Principle / R. Raz |
| Hard Examples for Bounded Depth Frege / E. Ben-Sasson |
| Relations between Average Case Complexity and Approximation Complexity / U. Feige |
| Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2-[epsilon] / J. Holmerin |
| Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection / D. MicciancioSession 2： |
| Algorithmic Derandomization via Complexity Theory / D. Sivakumar |
| Pseudo-random Generators for All Hardnesses / C. Umans |
| Randomness Conductors and Constant-Degree Lossless Expanders / M. Capalbo ; O. Reingold ; S. Vadhan ; A. WigdersonSession 3： |
| Expanders from Symmetric Codes / R. Meshulam |
| The Complexity of Approximating the Entropy / T. Batu ; S. Dasgupta ; R. Kumar ; R. Rubinfeld |
| Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems / P. Beame ; E. Vee |
| On Communication over an Entanglement-Assisted Quantum Channel / A. Nayak ; J. Salzman |
| Hardness Amplification within NP / R. O'DonnellSession 4： |
| 3-Manifold Knot Genus Is NP-Complete / I. Agol ; J. Hass ; W. Thurston |
| On the Power of Unique 2-Prover 1-Round Games / S. Khot |
| Learnability beyond AC[superscript 0] / J. Jackson ; A. Klivans ; R. Servedio |
| Resolution Lower Bounds for Perfect Matching Principles / A. RazborovSession 5： |
| Resolution Width-Size Trade-Offs for the Pigeon-Hole Principle / S. Dantchev |
| The Inapproximability of Lattice and Coding Problems with Preprocessing |
| Sampling Short Lattice Vectors and the Closest Lattice Vector Problem / M. Ajtai |
| Invited Address 1 |
| The History of Complexity / Lance Fortnow |
| The Correlation between Parity and Quadratic Polynomials Mod 3 / F. GreenSession 6： |
| Functions That Have Read-Twice Constant Width Branching Programs Are Not Necessarily Testable / E. Fischer ; I. Newman |
| On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism / P. Woelfel |
| Information Theory Methods in Communication Complexity / Z. Bar-Yossef ; T. JayramSession 7： |
| Extracting Quantum Entanglement (General Entanglement Purification Protocols) / A. Ambainis ; A. Smith ; K. Yang |
| Algebras of Minimal Rank over Perfect Fields / M. Blaser |
| Invited Address 2 |
| Rapid Mixing / Peter Winkler |
| Pseudorandomness and Average-Case Complexity via Uniform Reductions / L. TrevisanSession 8： |
| Pseudo-random Generators and Structure of Complete Degrees / M. Agrawal |
| Decoding Concatenated Codes Using Soft Information / V. Guruswami ; M. Sudan |
| Survey Talk 1 |
| Arthur and Merlin in a Quantum World / John Watrous |
| Streaming Computation of Combinatorial Objects / R. ShaltielSession 9： |
| Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval / O. Goldreich ; H. Karloff ; L. Schulman |
| Better Lower Bounds for Locally Decodable Codes / A. Deshpande ; R. Jain ; T. Kavitha ; S. Lokam ; J. Radhakrishnan |
| Universal Arguments and Their Applications / B. Barak |
| Author Index |
| Preface |
| Committees |
| Ron Book Prize for Best Student Paper |
| 2002 Best Paper Award |
| Joint Session with STOC 2002 / Session 1： |
| Resolution Lower Bounds for the Weak Pigeonhole Principle / R. Raz |
