Proceedings of the 30th Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

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

TCS
DBLP
Scholar
Full names Links ISxN
@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)

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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.