2002-2003 papers

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