default search action
30th 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
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
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
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
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
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
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
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
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
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
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 2024-11-26 20:33 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: