Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
Hilfe
Suche: Booktitle=Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
On the limits on non-approximability of lattice problems
Oded Goldreich
,
Shafi Goldwasser
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 1-9
The shortest vector problem in
L_2
is
NP
-hard for randomized reductions
Miklós Ajtai
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 10-19
Quantum circuits with mixed states
Dorit Aharonov
,
Alexei Kitaev
,
Noam Nisan
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 20-30
Exact sampling and approximate counting techniques
Mark Huber
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 31-40
A polynomial approximation algorithm for the minimum fill-in problem
Assaf Natanzon
,
Ron Shamir
,
Roded Sharan
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 41-47
An improved approximation algorithm for MULTIWAY CUT
Gruia Călinescu
,
Howard Karloff
,
Yuval Rabani
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 48-52
A framework for fast quantum mechanical algorithms
Lov K. Grover
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 53-62
Quantum vs. classical communication and computation
Harry Buhrmann
,
Richard Cleve
,
Avi Wigderson
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 63-68
Finding maximum flows in undirected graphs seems easier than bipartite matching
David R. Karger
,
Matthew S. Levine
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 69-78
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Jacob Holm
,
Kristian de Lichtenberg
,
Mikkel Thorup
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 79-89
Approximating the bandwidth via volume respecting embeddings
Uriel Feige
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 90-99
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
Avrim Blum
,
Goran Konjevod
,
R. Ravi
,
Santosh Vempala
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 100-105
Approximation schemes for Euclidean
k
-medians and related problems
Sanjeev Arora
,
Prabhakar Raghavan
,
Satish Rao
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 106-113
Rounding via trees: Deterministic approximation algorithms for group Steiner trees and
k
-median
Moses Charikar
,
Chandra Chekuri
,
Ashish Goel
,
Sudipto Guha
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 114-123
One help bit doesn't help
Richard Beigel
,
Tirza Hirst
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 124-130
Perfectly one-way probabilistic hash functions
Ran Canetti
,
Daniele Micciancio
,
Omer Reingold
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 131-140
Non-interactive and non-malleable commitment
Giovanni di Crescenzo
,
Yuval Ishai
,
Rafail Ostrovsky
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 141-150
Protecting data privacy in private information retrieval schemes
Yael Gertner
,
Yuval Ishai
,
Eyal Kushilevitz
,
Tal Malkin
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 151-160
On approximating arbitrary metrics by tree metrics
Yair Bartal
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 161-168
Trees and Euclidean metrics
Nathan Linial
,
Avner Magen
,
Michael E. Saks
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 169-175
Random generation of embedded graphs and an extension to Dobrushin uniqueness
Marcus Peinado
,
Thomas Lengauer
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 176-185
Efficient algorithms for constructing fault-tolerant geometric spanners
Christos Levcopoulos
,
Giri Narasimhan
,
Michiel Smid
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 186-195
Almost optimal dispersers
Amnon Ta-Shma
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 196-202
NP
might not be as easy as detecting unique solutions
Richard Beigel
,
Harry Buhrmann
,
Lance Fortnow
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 203-208
The random oracle methodology, revisited
Ran Canetti
,
Oded Goldreich
,
Shai Halevi
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC'98 (Dallas, Texas, May 23-26, 1998)
, 1998, pp. 209-218
Seiten 1
2
3
4
>