default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID30th STOC 1998: Dallas, Texas, USA
- Jeffrey Scott Vitter:
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 L2 is NP-hard for Randomized Reductions (Extended Abstract). 10-19 - Dorit Aharonov, Alexei Y. 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 S. 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 R. 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 N. Vorobjov Jr.:
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-08 00:56 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
