30. STOC 1998: Dallas, Texas, USA

Jeffrey Scott Vitter (Ed.): Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998. ACM 1998, ISBN 0-89791-962-9

Session 1A

Oded Goldreich, Shafi Goldwasser:
On the Limits of Non-Approximability of Lattice Problems. 1-9
Miklós Ajtai:
The Shortest Vector Problem in L₂ is NP-hard for Randomized Reductions (Extended Abstract). 10-19
Dorit Aharonov, Alexei Kitaev, Noam Nisan:
Quantum Circuits with Mixed States. 20-30

Session 1B

Mark Huber:
Exact Sampling and Approximate Counting Techniques. 31-40
Assaf Natanzon, Ron Shamir, Roded Sharan:
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. 41-47
Gruia Calinescu, Howard J. Karloff, Yuval Rabani:
An Improved Approximation Algorithm for Multiway Cut. 48-52

Session 2A

Lov K. Grover:
A Framework for Fast Quantum Mechanical Algorithms. 53-62
Harry Buhrman, Richard Cleve, Avi Wigderson:
Quantum vs. Classical Communication and Computation. 63-68

Session 2B

David R. Karger, Matthew S. Levine:
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching. 69-78
Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup:
Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. 79-89

Invited Session I

Session 3A

Uriel Feige:
Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). 90-99
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala:
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. 100-105
Sanjeev Arora, Prabhakar Raghavan, Satish Rao:
Approximation Schemes for Euclidean k-Medians and Related Problems. 106-113
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha:
Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. 114-123

Session 3B

Richard Beigel, Tirza Hirst:
One Help Bit Doesn't Help. 124-130
Ran Canetti, Daniele Micciancio, Omer Reingold:
Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). 131-140
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky:
Non-Interactive and Non-Malleable Commitment. 141-150
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin:
Protecting Data Privacy in Private Information Retrieval Schemes. 151-160

Session 4A

Yair Bartal:
On Approximating Arbitrary Metrices by Tree Metrics. 161-168
Nathan Linial, Avner Magen, Michael E. Saks:
Trees and Euclidean Metrics. 169-175
Marcus Peinado, Thomas Lengauer:
Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract). 176-185
Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid:
Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. 186-195
Amnon Ta-Shma:
Almost Optimal Dispersers. 196-202

Session 4B

Richard Beigel, Harry Buhrman, Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions. 203-208
Ran Canetti, Oded Goldreich, Shai Halevi:
The Random Oracle Methodology, Revisited (Preliminary Version). 209-218
Dima Grigoriev:
Randomized Complexity Lower Bounds. 219-223
Orna Kupferman, Moshe Y. Vardi:
Weak Alternating Automata and Tree Automata Emptiness. 224-233
Denis Thérien, Thomas Wilke:
Over Words, Two Variables Are as Powerful as One Quantifier Alternation. 234-240

Session 5A

Mohammad Amin Shokrollahi, Hal Wasserman:
Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. 241-248
Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman:
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs. 249-258
Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan:
Spot-Checkers. 259-268

Session 5B

Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan:
The Power of a Pebble: Exploring and Mapping Directed Graphs. 269-278
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery Westbrook:
Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators. 279-288
Oded Goldreich, Dana Ron:
A Sublinear Bipartiteness Tester for Bunded Degree Graphs. 289-298

Session 6A

Luca Trevisan:
Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). 299-308
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer:
The Closure of Monadic NP (Extended Abstract). 309-318

Session 6B

Michael L. Fredman:
Information Theoretic Implications for Pairing Heaps. 319-326
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher:
Min-Wise Independent Permutations (Extended Abstract). 327-336

Invited Session II

Sanjeev Arora:
The Approximability of NP-hard Problems. 337-348

Session 7A

Moses Charikar, Samir Khuller, Balaji Raghavachari:
Algorithms for Capacitated Vehicle Routing. 349-358
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén:
Adaptive Packet Routing for Bursty Adversarial Traffic. 359-368
Matthew Andrews, Lisa Zhang:
Stability Results for Networks with Input and Output Blocking. 369-377
Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, Ramesh K. Sitaraman, Berthold Vöcking:
Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks. 378-388
Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott:
TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract). 389-398

Session 7B

Oded Goldreich, Amit Sahai, Salil P. Vadhan:
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. 399-408
Cynthia Dwork, Moni Naor, Amit Sahai:
Concurrent Zero-Knowledge. 409-418
Mihir Bellare, Ran Canetti, Hugo Krawczyk:
A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract). 419-428
Anna Gál:
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs. 429-437
Daniel Lewin, Salil P. Vadhan:
Checking Polynomial Identities over any Field: Towards a Derandomization? 438-447

Session 8A

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Multicasting in Heterogeneous Networks. 448-453
Susanne Albers, Naveen Garg, Stefano Leonardi:
Minimizing Stall Time in Single and Parallel Disk Systems. 454-462
Sanjeev Khanna, Shiyu Zhou:
On Indexed Data Broadcast. 463-472
Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Segmentation Problems. 473-482

Session 8B

Nicolai Vorobjov:
Computing Local Dimension of a Semialgebraic Set. 483-487
Bernard Mourrain, Victor Y. Pan:
Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations. 488-496
Ming-Deh A. Huang, Ashwin J. Rao:
A Black Box Approach to the Algebraic Set Decomposition Problem. 497-506
Hervé Fournier, Pascal Koiran:
Are Lower Bounds Easier over the Reals? 507-513

Session 9A

Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
Planar Map Graphs. 514-523
Michael Molloy, Bruce A. Reed:
Further Algorithmic Aspects of the Local Lemma. 524-529
Jon M. Kleinberg:
Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem. 530-539
Satish Rao, Warren D. Smith:
Approximating Geometrical Graphs via "Spanners" and "Banyans". 540-550

Session 9B

Uri Zwick:
Finding Almost-Satisfying Assignments. 551-560
Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. 561-571
Michael H. Freedman:
K-sat on Groups and Undecidability. 572-576
Dima Grigoriev, Marek Karpinski:
An Exponential Lower Bound for Depth 3 Arithmetic Circuits. 577-582

Session 10A

Nader H. Bshouty:
A New Composition Theorem for Learning Algorithms. 583-589
Peter Damaschke:
Adaptive versus Nonadaptive Attribute-Efficient Learning. 590-596
Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis:
On the Complexity of Protein Folding (Extended Abstract). 597-603

Session 10B

Piotr Indyk, Rajeev Motwani:
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. 604-613
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani:
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. 614-623
Uriel Feige, Christian Scheideler:
Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). 624-633

Session 11A

Sanjeev Khanna, Vincenzo Liberatore:
On Broadcast Disk Paging. 634-643
Nathan Linial, Alex Samorodnitsky, Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. 644-652

Session 11B

Jayram S. Thathachar:
On Separating the Read-k-Times Branching Program Hierarchy. 653-662
Yair Frankel, Philip D. MacKenzie, Moti Yung:
Robust Efficient Distributed RSA-Key Generation. 663-672
László Babai, Thomas P. Hayes, Peter G. Kimmel:
The Cost of the Missing Bit: Communication Complexity with Help. 673-682

Last update Sun May 19 23:37:44 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page