Jeffrey Scott Vitter
Proceedings of the 30th Annual ACM Symposium on Theory of Computing
STOC, 1998.

@proceedings{STOC-1998,
	address       = "Dallas, Texas, USA",
	editor        = "Jeffrey Scott Vitter",
	isbn          = "0-89791-962-9",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 30th Annual ACM Symposium on Theory of Computing}",
	year          = 1998,
}

Contents (76 items)

12 ×#algorithm
11 ×#approximate
9 ×#problem
7 ×#graph
7 ×#on the
6 ×#bound
6 ×#random
4 ×#complexity
4 ×#multi
4 ×#performance

STOC-1998-GoldreichG #on the #problem

On the Limits of Non-Approximability of Lattice Problems (OG, SG), pp. 1–9.

STOC-1998-Ajtai #np-hard #problem #random #reduction

The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (MA), pp. 10–19.

STOC-1998-AharonovKN #quantum

Quantum Circuits with Mixed States (DA, AK, NN), pp. 20–30.

STOC-1998-Huber #approximate

Exact Sampling and Approximate Counting Techniques (MH), pp. 31–40.

STOC-1998-NatanzonSS #algorithm #approximate #polynomial #problem

A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (AN, RS, RS), pp. 41–47.

STOC-1998-CalinescuKR #algorithm #approximate #multi

An Improved Approximation Algorithm for Multiway Cut (GC, HJK, YR), pp. 48–52.

STOC-1998-Grover #algorithm #framework #performance #quantum

A Framework for Fast Quantum Mechanical Algorithms (LKG), pp. 53–62.

STOC-1998-BuhrmanCW #communication #quantum

Quantum vs. Classical Communication and Computation (HB, RC, AW), pp. 63–68.

STOC-1998-KargerL #graph

Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (DRK, MSL), pp. 69–78.

STOC-1998-HolmLT #algorithm

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity (JH, KdL, MT), pp. 79–89.

STOC-1998-Feige #approximate

Approximating the Bandwidth via Volume Respecting Embeddings (UF), pp. 90–99.

STOC-1998-BlumKRV #problem

Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems (AB, GK, RR, SV), pp. 100–105.

STOC-1998-AroraRR #approximate #problem

Approximation Schemes for Euclidean k-Medians and Related Problems (SA, PR, SR), pp. 106–113.

STOC-1998-CharikarCGG #algorithm #approximate

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median (MC, CC, AG, SG), pp. 114–123.

STOC-1998-BeigelH

One Help Bit Doesn’t Help (RB, TH), pp. 124–130.

STOC-1998-CanettiMR #probability

Perfectly One-Way Probabilistic Hash Functions (RC, DM, OR), pp. 131–140.

STOC-1998-CrescenzoIO

Non-Interactive and Non-Malleable Commitment (GDC, YI, RO), pp. 141–150.

STOC-1998-GertnerIKM #information retrieval #privacy

Protecting Data Privacy in Private Information Retrieval Schemes (YG, YI, EK, TM), pp. 151–160.

STOC-1998-Bartal #approximate #metric #on the

On Approximating Arbitrary Metrices by Tree Metrics (YB), pp. 161–168.

STOC-1998-LinialMS #metric

Trees and Euclidean Metrics (NL, AM, MES), pp. 169–175.

STOC-1998-PeinadoL #embedded #generative #graph #random

Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (MP, TL), pp. 176–185.

STOC-1998-LevcopoulosNS #algorithm #fault tolerance #geometry #performance

Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners (CL, GN, MHMS), pp. 186–195.

STOC-1998-Ta-Shma

Almost Optimal Dispersers (ATS), pp. 196–202.

STOC-1998-BeigelBF #detection

NP Might Not Be As Easy As Detecting Unique Solutions (RB, HB, LF), pp. 203–208.

STOC-1998-CanettiGH #random #revisited

The Random Oracle Methodology, Revisited (RC, OG, SH), pp. 209–218.

STOC-1998-Grigoriev #bound #complexity #random

Randomized Complexity Lower Bounds (DG), pp. 219–223.

STOC-1998-KupfermanV #automaton

Weak Alternating Automata and Tree Automata Emptiness (OK, MYV), pp. 224–233.

STOC-1998-TherienW #quantifier #word

Over Words, Two Variables Are as Powerful as One Quantifier Alternation (DT, TW), pp. 234–240.

STOC-1998-ShokrollahiW #algebra #bound #geometry

Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound (MAS, HW), pp. 241–248.

STOC-1998-LubyMSS #analysis #design #graph #using

Analysis of Low Density Codes and Improved Designs Using Irregular Graphs (ML, MM, MAS, DAS), pp. 249–258.

STOC-1998-ErgunKKRV

Spot-Checkers (FE, SK, RK, RR, MV), pp. 259–268.

STOC-1998-BenderFRSV #graph #power of

The Power of a Pebble: Exploring and Mapping Directed Graphs (MAB, AF, DR, AS, SPV), pp. 269–278.

STOC-1998-BuchsbaumKRW #algorithm #linear #verification

Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators (ALB, HK, AR, JW), pp. 279–288.

STOC-1998-GoldreichR #graph #sublinear

A Sublinear Bipartiteness Tester for Bunded Degree Graphs (OG, DR), pp. 289–298.

STOC-1998-Trevisan #query #testing

Recycling Queries in PCPs and in Linearity Tests (LT), pp. 299–308.

STOC-1998-AjtaiFS #monad

The Closure of Monadic NP (MA, RF, LJS), pp. 309–318.

STOC-1998-Fredman

Information Theoretic Implications for Pairing Heaps (MLF), pp. 319–326.

STOC-1998-BroderCFM #independence #permutation

Min-Wise Independent Permutations (AZB, MC, AMF, MM), pp. 327–336.

STOC-1998-Arora #np-hard #problem

The Approximability of NP-hard Problems (SA), pp. 337–348.

STOC-1998-CharikarKR #algorithm

Algorithms for Capacitated Vehicle Routing (MC, SK, BR), pp. 349–358.

STOC-1998-AielloKOR #adaptation

Adaptive Packet Routing for Bursty Adversarial Traffic (WA, EK, RO, AR), pp. 359–368.

STOC-1998-AndrewsZ #network

Stability Results for Networks with Input and Output Blocking (MA, LZ), pp. 369–377.

STOC-1998-ColeMHMRSSV #multi #network #protocol #random

Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks (RC, BMM, FMadH, MM, AWR, KS, RKS, BV), pp. 378–388.

STOC-1998-DoolyGS #theory and practice

TCP Dynamic Acknowledgment Delay: Theory and Practice (DRD, SAG, SDS), pp. 389–398.

STOC-1998-GoldreichSV #statistics

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge (OG, AS, SPV), pp. 399–408.

STOC-1998-DworkNS #concurrent

Concurrent Zero-Knowledge (CD, MN, AS), pp. 409–418.

STOC-1998-BellareCK #analysis #approach #authentication #composition #design #protocol

A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (MB, RC, HK), pp. 419–428.

STOC-1998-Gal #bound #source code

A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs (AG), pp. 429–437.

STOC-1998-LewinV #polynomial #question #towards

Checking Polynomial Identities over any Field: Towards a Derandomization? (DL, SPV), pp. 438–447.

STOC-1998-Bar-NoyGNS #multi #network

Multicasting in Heterogeneous Networks (ABN, SG, JN, BS), pp. 448–453.

STOC-1998-AlbersGL #parallel

Minimizing Stall Time in Single and Parallel Disk Systems (SA, NG, SL), pp. 454–462.

STOC-1998-KhannaZ #on the

On Indexed Data Broadcast (SK, SZ), pp. 463–472.

STOC-1998-KleinbergPR #problem #segmentation

Segmentation Problems (JMK, CHP, PR), pp. 473–482.

STOC-1998-Vorobjov #algebra #set

Computing Local Dimension of a Semialgebraic Set (NV), pp. 483–487.

STOC-1998-MourrainP #equation #multi #polynomial

Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (BM, VYP), pp. 488–496.

STOC-1998-HuangR #algebra #approach #black box #composition #problem #set

A Black Box Approach to the Algebraic Set Decomposition Problem (MDAH, AJR), pp. 497–506.

STOC-1998-FournierK #bound #question

Are Lower Bounds Easier over the Reals? (HF, PK), pp. 507–513.

STOC-1998-ChenGP #graph

Planar Map Graphs (ZZC, MG, CHP), pp. 514–523.

STOC-1998-MolloyR #algorithm #aspect-oriented

Further Algorithmic Aspects of the Local Lemma (MM, BAR), pp. 524–529.

STOC-1998-Kleinberg #algorithm #problem

Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem (JMK), pp. 530–539.

STOC-1998-RaoS #approximate #geometry #graph

Approximating Geometrical Graphs via “Spanners” and “Banyans” (SR, WDS), pp. 540–550.

STOC-1998-Zwick

Finding Almost-Satisfying Assignments (UZ), pp. 551–560.

STOC-1998-BeameKPS #complexity #on the #proving #random #satisfiability

On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas (PB, RMK, TP, MES), pp. 561–571.

STOC-1998-Freedman #satisfiability

K-sat on Groups and Undecidability (MHF), pp. 572–576.

STOC-1998-GrigorievK #bound #exponential

An Exponential Lower Bound for Depth 3 Arithmetic Circuits (DG, MK), pp. 577–582.

STOC-1998-Bshouty #algorithm #composition #learning #theorem

A New Composition Theorem for Learning Algorithms (NHB), pp. 583–589.

STOC-1998-Damaschke #adaptation #learning

Adaptive versus Nonadaptive Attribute-Efficient Learning (PD), pp. 590–596.

STOC-1998-CrescenziGPPY #complexity #on the

On the Complexity of Protein Folding (PC, DG, CHP, AP, MY), pp. 597–603.

STOC-1998-IndykM #approximate #nearest neighbour #towards

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality (PI, RM), pp. 604–613.

STOC-1998-KushilevitzOR #approximate #nearest neighbour #performance

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces (EK, RO, YR), pp. 614–623.

STOC-1998-FeigeS #bound #scheduling

Improved Bounds for Acyclic Job Shop Scheduling (UF, CS), pp. 624–633.

STOC-1998-KhannaL #on the

On Broadcast Disk Paging (SK, VL), pp. 634–643.

STOC-1998-LinialSW #algorithm #approximate #matrix #polynomial #scalability

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.

STOC-1998-Thathachar #branch #on the

On Separating the Read-k-Times Branching Program Hierarchy (JST), pp. 653–662.

STOC-1998-FrankelMY #distributed #generative #performance #robust

Robust Efficient Distributed RSA-Key Generation (YF, PDM, MY), pp. 663–672.

STOC-1998-BabaiHK #communication #complexity #cost analysis

The Cost of the Missing Bit: Communication Complexity with Help (LB, TPH, PGK), pp. 673–682.