Table of Contents

• Over Words, Two Variables Are as Powerful as One Quantifier Alternation [doi]
• On the Limits of Non-Approximability of Lattice ProblemsOded Goldreich, Shafi Goldwasser. 1-9 [doi]
• The Shortest Vector Problem in ::::L::2:::::: is ::::NP::::-hard for Randomized Reductions (Extended Abstract)Miklós Ajtai. 10-19 [doi]
• Quantum Circuits with Mixed StatesDorit Aharonov, Alexei Kitaev, Noam Nisan. 20-30 [doi]
• Exact Sampling and Approximate Counting TechniquesMark Huber. 31-40 [doi]
• A Polynomial Approximation Algorithm for the Minimum Fill-In ProblemAssaf Natanzon, Ron Shamir, Roded Sharan. 41-47 [doi]
• An Improved Approximation Algorithm for Multiway CutGruia Calinescu, Howard J. Karloff, Yuval Rabani. 48-52 [doi]
• A Framework for Fast Quantum Mechanical AlgorithmsLov K. Grover. 53-62 [doi]
• Quantum vs. Classical Communication and ComputationHarry Buhrman, Richard Cleve, Avi Wigderson. 63-68 [doi]
• Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite MatchingDavid R. Karger, Matthew S. Levine. 69-78 [doi]
• Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and BiconnectivityJacob Holm, Kristian de Lichtenberg, Mikkel Thorup. 79-89 [doi]
• Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract)Uriel Feige. 90-99 [doi]
• Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering ProblemsAvrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala. 100-105 [doi]
• Approximation Schemes for Euclidean ::::k::::-Medians and Related ProblemsSanjeev Arora, Prabhakar Raghavan, Satish Rao. 106-113 [doi]
• Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and ::::k::::-MedianMoses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha. 114-123 [doi]
• One Help Bit Doesn t HelpRichard Beigel, Tirza Hirst. 124-130 [doi]
• Non-Interactive and Non-Malleable CommitmentGiovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky. 141-150 [doi]
• Protecting Data Privacy in Private Information Retrieval SchemesYael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin. 151-160 [doi]
• On Approximating Arbitrary Metrices by Tree MetricsYair Bartal. 161-168 [doi]
• Trees and Euclidean MetricsNathan Linial, Avner Magen, Michael E. Saks. 169-175 [doi]
• Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract)Marcus Peinado, Thomas Lengauer. 176-185 [doi]
• Almost Optimal DispersersAmnon Ta-Shma. 196-202 [doi]
• NP Might Not Be As Easy As Detecting Unique SolutionsRichard Beigel, Harry Buhrman, Lance Fortnow. 203-208 [doi]
• The Random Oracle Methodology, Revisited (Preliminary Version)Ran Canetti, Oded Goldreich, Shai Halevi. 209-218 [doi]
• Randomized Complexity Lower BoundsDima Grigoriev. 219-223 [doi]
• Weak Alternating Automata and Tree Automata EmptinessOrna Kupferman, Moshe Y. Vardi. 224-233 [doi]
• Over Words, Two Variables Are as Powerful as One Quantifier AlternationDenis Thérien, Thomas Wilke. 234-240 [doi]
• Analysis of Low Density Codes and Improved Designs Using Irregular GraphsMichael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman. 249-258 [doi]
• Spot-CheckersFunda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan. 259-268 [doi]
• The Power of a Pebble: Exploring and Mapping Directed GraphsMichael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan. 269-278 [doi]
• Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and DominatorsAdam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery Westbrook. 279-288 [doi]
• Recycling Queries in PCPs and in Linearity Tests (Extended Abstract)Luca Trevisan. 299-308 [doi]
• The Closure of Monadic NP (Extended Abstract)Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer. 309-318 [doi]
• Information Theoretic Implications for Pairing HeapsMichael L. Fredman. 319-326 [doi]
• Min-Wise Independent Permutations (Extended Abstract)Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher. 327-336 [doi]
• The Approximability of NP-hard ProblemsSanjeev Arora. 337-348 [doi]
• Algorithms for Capacitated Vehicle RoutingMoses Charikar, Samir Khuller, Balaji Raghavachari. 349-358 [doi]
• Adaptive Packet Routing for Bursty Adversarial TrafficWilliam Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén. 359-368 [doi]
• Stability Results for Networks with Input and Output BlockingMatthew Andrews, Lisa Zhang. 369-377 [doi]
• Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection NetworksRichard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, Ramesh K. Sitaraman, Berthold Vöcking. 378-388 [doi]
• TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract)Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott. 389-398 [doi]
• Concurrent Zero-KnowledgeCynthia Dwork, Moni Naor, Amit Sahai. 409-418 [doi]
• A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract)Mihir Bellare, Ran Canetti, Hugo Krawczyk. 419-428 [doi]
• A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span ProgramsAnna Gál. 429-437 [doi]
• Checking Polynomial Identities over any Field: Towards a Derandomization?Daniel Lewin, Salil P. Vadhan. 438-447 [doi]
• Multicasting in Heterogeneous NetworksAmotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber. 448-453 [doi]
• Minimizing Stall Time in Single and Parallel Disk SystemsSusanne Albers, Naveen Garg, Stefano Leonardi. 454-462 [doi]
• On Indexed Data BroadcastSanjeev Khanna, Shiyu Zhou. 463-472 [doi]
• Segmentation ProblemsJon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan. 473-482 [doi]
• Asymptotic Acceleration of Solving Multivariate Polynomial Systems of EquationsBernard Mourrain, Victor Y. Pan. 488-496 [doi]
• A Black Box Approach to the Algebraic Set Decomposition ProblemMing-Deh A. Huang, Ashwin J. Rao. 497-506 [doi]
• Are Lower Bounds Easier over the Reals?Hervé Fournier, Pascal Koiran. 507-513 [doi]
• Planar Map GraphsZhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. 514-523 [doi]
• Further Algorithmic Aspects of the Local LemmaMichael Molloy, Bruce A. Reed. 524-529 [doi]
• Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths ProblemJon M. Kleinberg. 530-539 [doi]
• Approximating Geometrical Graphs via Spanners and Banyans Satish Rao, Warren D. Smith. 540-550 [doi]
• Finding Almost-Satisfying AssignmentsUri Zwick. 551-560 [doi]
• On the Complexity of Unsatisfiability Proofs for Random ::::k::::-CNF FormulasPaul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks. 561-571 [doi]
• An Exponential Lower Bound for Depth 3 Arithmetic CircuitsDima Grigoriev, Marek Karpinski. 577-582 [doi]
• A New Composition Theorem for Learning AlgorithmsNader H. Bshouty. 583-589 [doi]
• Adaptive versus Nonadaptive Attribute-Efficient LearningPeter Damaschke. 590-596 [doi]
• On the Complexity of Protein Folding (Extended Abstract)Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. 597-603 [doi]
• Approximate Nearest Neighbors: Towards Removing the Curse of DimensionalityPiotr Indyk, Rajeev Motwani. 604-613 [doi]
• Efficient Search for Approximate Nearest Neighbor in High Dimensional SpacesEyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani. 614-623 [doi]
• Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract)Uriel Feige, Christian Scheideler. 624-633 [doi]
• On Broadcast Disk PagingSanjeev Khanna, Vincenzo Liberatore. 634-643 [doi]
• A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate PermanentsNathan Linial, Alex Samorodnitsky, Avi Wigderson. 644-652 [doi]
• On Separating the Read-k-Times Branching Program HierarchyJayram S. Thathachar. 653-662 [doi]
• Robust Efficient Distributed RSA-Key GenerationYair Frankel, Philip D. MacKenzie, Moti Yung. 663-672 [doi]
• The Cost of the Missing Bit: Communication Complexity with HelpLászló Babai, Thomas P. Hayes, Peter G. Kimmel. 673-682 [doi]