 |
 |
 | |
What We're Reading Now |
Dixon's Books |
- Aaronson: The Complexity Zoo
- Ajtai, Komlós, Szemerédi 1987: "Deterministic Simulation in LOGSPACE"
- Arora, Lund 1996: "Hardness of Approximations"
- Arora, Rao, Vazirani 2004: "Expander Flows, Geometric Embeddings and Graph Partitioning"
- Boppana, Sipser 1989 survey: "The Complexity of Finite Functions"
- Cohen, Wigderson 1989: "Dispersers, Deterministic Amplification, and Weak Random Sources"
- Dinur 2005: "The PCP Theorem by Gap Amplification "
- Feige 1998: "A threshold of ln n for approximating set cover"
- Goldreich, Impagliazzo, Levin, Venkatesan, Zuckerman 1990: "Security Preserving Amplification of Hardness"
- Goldreich, Nisan, Wigderson 1995: "On Yao's XOR-Lemma"
- Green, Tao 2007: "A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields"
- Hemenway, Ostrovsky 2007: "Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code"
- Impagliazzo 1995: "Hard-core distributions for somewhat hard problems"
- Impagliazzo, Wigderson 1997: "P=BPP unless E has sub-exponential circuits: derandomizing the XOR lemma"
- Impagliazzo, Zuckerman 1989: "How to Recycle Random Bits"
- Kabanets 2002 survey: "Derandomization: A Brief Overview"
- Kannan, Venkateswaran, Vinay, Yao 1993: "A circuit-based proof of Toda's Theorem"
- Katz, Trevisan 2000: "On the efficiency of local decoding procedures for error-correcting codes"
- Linial, London, Rabinovich 1995: "The geometry of graphs and some of its algorithmic applications"
- Linial, Wigderson 2003 lecture notes: "Expander Graphs and their Applications"
- Lund, Yannakakis 1994: "On the hardness of approximating minimization problems"
- Nisan, Wigderson 1994: "Hardness vs. randomness"
- Papadimitriou, Yannakakis 1991: "Optimization, approximation, and complexity classes"
- Raghavendra 2007: "A Note on Yekhanin's Locally Decodable Codes"
- Razborov, Yekhanin 2006: "An &Omega(n1/3) lower bound for bilinear group based private information retrieval"
- Razborov, Rudich 1997: Natural Proofs
- Razborov, Yekhanin 2006: An &Omega(n1/3) lower bound for bilinear group based private information retrieval
- Reingold, Vadhan, Wigderson 2001: "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors"
- Reingold, Vadhan, Wigderson 2002: "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders"
- Reingold 2004: "Undirected ST-Connectivity in Log-Space"
- Samorodnitsky 2006: "Low degree tests at large distances"
- Sudhan 2000 lecture notes: "Probabilistically Checkable Proofs"
- Sudhan, Trevisan, Vadhan 2000: "Pseudorandom generators without the XOR lemma"
- Toda 1993: "PP is as hard as the Polynomial Hierarchy"
- Trevisan 1994 survey: "Some Applications of Coding Theory in Computational Complexity"
- Valiant, Vazirani 1986: "NP is as Easy as Detecting Unique Solutions"
- Viola, Emanuele 2007: "Selected Results in Additive Combinatorics: An Exposition"
- Wigderson, Dinur 2002 survey: "Derandomizing BPP and Pseudorandomness - A Survey"
- Yekhanin 2007: "Towards 3-query locally decodable codes of subexponential length"