*This page contains links to some papers produced during the academic year of 2002-2003.*

## Complexity

- D. Aharonov, O. Regev, A Lattice Problem in Quantum NP, Proceedings of the
*44th Annual IEEE Symposium on Foundations of Computer Science, 2003*, pages 210-219 - B. Barak, R. Shaltiel, A. Wigderson, Computational Analogues of Entropy, Proceedings of the
*11th International Conference on Random Structures and Algorithms, 2003*, pages 200-215 - E. Ben-Sasson, M. Sudan, S. Vadhan, A. Wigderson, Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets, Proceedings of the
*35th Annual ACM Symposium on Theory of Computing, 2003*, pages 612-621 - H. Buhrman, H. Klauck, N. Vereshchagin, P. Vitanyi, Individual Communication Complexity,
*Journal of Computer and System Sciences*, 73(6): 973-985, 2007 - A. Chakrabarti, S. Khot, X. Sun, Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness, Proceedings of the
*18th IEEE Conference on Computational Complexity, 2003*, pages 107-117 - A. Chakrabarti, O. Regev, An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching, Proceedings of the
*45th Annual IEEE Symposium on Foundations of Computer Science, 2004*, pages 473-482 - I. Dinur, V. Guruswami, S. Khot, O. Regev, A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover,
*SIAM Journal on Computing*, 34(5): 1129-1146, 2005 - D. Harnik, M. Naor, O. Reingold, A. Rosen, Completeness in Two-Party Secure Computation - A Computational View,
*Journal of Cryptology*, 19(4): 521-552, 2006 - J. Kempe, O. Regev, 3-Local Hamiltonian is QMA-complete,
*Quantum Information and Computation*, 3(3): 258-264, 2003 - S. Khot, O. Regev, Vertex Cover might be Hard to Approximate to within 2-\epsilon, Proceedings of the
*18th IEEE Conference on Computational Complexity, 2003*, pages 379-386 - H. Klauck, Quantum time-space tradeoffs for sorting. Proceedings of the
*35th Annual ACM Symposium on Theory of Computing, 2003*, pages 69-76 - H. Klauck, Rectangle Size Bounds and Threshold Covers in Communication Complexity. Proceedings of the
*18th IEEE Conference on Computational Complexity, 2003*, pages 118-134 - C-J Lu, O. Reingold, S. Vadhan, A. Wigderson, Extractors: Optimal up to Constant Factors, Proceedings of the
*35th Annual ACM Symposium on Theory of Computing, 2003*, pages 602-611 - R. Raz, A. Shpilka, On the power of Quantum Proofs, Proceedings of the
*19th IEEE Conference on Computational Complexity, 2004*, pages 260-274 - A. Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution
- O. Regev, Improved Inapproximability of Lattice and Coding Problems with Preprocessing,
*IEEE Transactions on Information Theory*, 50(9): 2031-2037, 2004

## Algorithms

- S. Arora, K. L. Chang, Approximations Schemes for Degree-Restricted MST and Red-Blue Separation Problem,
*Algorithmica*, 40(3): 189-210, 2004 - S. Arora, S. Rao, U. Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings, Proceedings of the
*36th Annual ACM Symposium on Theory of Computing, 2004*, pages 222-231 - J. Balogh, O. Regev, C. Smyth, W. Steiger, M. Szegedy, Long Monotone Paths in Line Arrangements,
*Discrete and Computational Geometry*, 32(2): 167-176, 2004 - B. Bollobas, D. Coppersmith, M. Elkin, Sparse Distance Preservers and Additive Spanners,
*SIAM Journal on Discrete Mathematics*, 19(4): 1029-1055, 2005 - M. Elkin, A Faster Distributed Protocol for Constructing the Minimum Spanning Tree,
*Journal of Computer and System Sciences*, 72(8): 1282-1308, 2006 - M. Elkin, Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem,
*SIAM Journal on Computing*, 36(2): 433-456, 2006 - M. Elkin, G. Kortsarz, Sublogarithmic Approximation for Telephone Multicast,
*Journal of Computer and System Sciences*, 72(4): 648-659, 2006 - M. Elkin, G. Kortsarz, Approximation Algorithm for Directed Telephone Multicast Problem,
*Algorithmica*, 45(4): 569-583, 2006 - M. Elkin, G. Kortsarz, Logarithmic Inapproximability of the Radio Broadcast Problem,
*Journal of Algorithms*, 52(1): 8-25, 2004 - R. Raz, A. Shpilka, Deterministic Polynomial Identity Testing in Non-Commutative Models,
*Journal of Computational Complexity*, 14(1): 1-19, 2005 - O. Regev, New Lattice Based Cryptographic Constructions,
*Journal of the ACM*, 51(6): 899-942, 2004

## Combinatorics

- N. Alon, I. Dinur, E. Friedgut, B. Sudakov, Graph products, fourier analysis and spectral techniques,
*Geometric and Functional Analysis*, 14: 913-940, 2004 - Z. Furedi, B. Sudakov, Extremal set-systems with restricted k-wise intersections,
*J. Combinatorial Theory Ser. A*, 105: 143-159, 2004 - P. Keevash, M. Saks, B. Sudakov, J. Verstraete, Multicolour Turan problems,
*Advances in Applied Mathematics*, 33: 238-262, 2004 - J.H. Kim, B. Sudakov, V. Vu, Small subgraphs of random regular graphs,
*Discrete Mathematics*, 307(15): 1961-1967, 2007 - M. Krivelevich, B. Sudakov, V. Vu, Covering codes with improved density,
*IEEE Transactions on Information Theory*, 49: 1812-1815, 2003

## Miscellanea

- S. Arora, Advanced Topics in Computer Science: A Theorist's Toolkit (course given at the Princeton University)
- A. Wigderson, On the Work of Madhu Sudan,
*Notices of the AMS*, 50(1): 45-50, 2003