Harriet Ortiz
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
STOC, 1990.

@proceedings{STOC-1990,
	address       = "Baltimore, Maryland, USA",
	editor        = "Harriet Ortiz",
	isbn          = "0-89791-361-2",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 22nd Annual ACM Symposium on Theory of Computing}",
	year          = 1990,
}

Contents (59 items)

9 ×#algorithm
7 ×#bound
7 ×#on the
6 ×#complexity
6 ×#performance
5 ×#online
5 ×#problem
3 ×#approximate
3 ×#graph
3 ×#network

STOC-1990-FredmanW

BLASTING through the Information Theoretic Barrier with FUSION TREES (MLF, DEW), pp. 1–7.

STOC-1990-Cole #on the

On the Dynamic Finger Conjecture for Splay Trees (RC0), pp. 8–17.

STOC-1990-SundarT #sequence #set

Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences (RS, RET), pp. 18–25.

STOC-1990-Frederickson #bound

The Information Theory Bound Is Tight for Selection in a Heap (GNF), pp. 26–33.

STOC-1990-Poutre #bound #pointer #problem

Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines (JALP), pp. 34–44.

STOC-1990-GoddardKS #algorithm #random #sorting

Optimal Randomized Algorithms for Local Sorting and Set-Maxima (WG, VK, LJS), pp. 45–53.

STOC-1990-BoardP #algorithm #on the

On the Necessity of Occam Algorithms (RAB, LP), pp. 54–63.

STOC-1990-Blum #infinity #learning

Learning Boolean Functions in an Infinite Atribute Space (AB), pp. 64–72.

STOC-1990-BlumLR #problem #self

Self-Testing/Correcting with Applications to Numerical Problems (MB, ML, RR), pp. 73–83.

STOC-1990-Yao

Coherent Functions and Program Checkers (ACCY), pp. 84–94.

STOC-1990-EvenR #distributed #network #using

The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (SE, SR), pp. 95–105.

STOC-1990-FischerMRT #problem

The Wakeup Problem (MJF, SM, SR, GT), pp. 106–116.

STOC-1990-DietzfelbingerH #how #network #taxonomy

How to Distribute a Dictionary in a Complete Network (MD, FMadH), pp. 117–127.

STOC-1990-FeigePRU

Computing with Unreliable Information (UF, DP, PR, EU), pp. 128–137.

STOC-1990-KedemPS #parallel #performance #robust

Efficient Robust Parallel Computations (ZMK, KVP, PGS), pp. 138–148.

STOC-1990-AroraLM #algorithm #network #online

On-line Algorithms for Path Selection in a Nonblocking Network (SA, FTL, BMM), pp. 149–158.

STOC-1990-VitterS #parallel

Optimal Disk I/O with Parallel Block Transfer (JSV, EAMS), pp. 159–169.

STOC-1990-Vishkin #pattern matching #performance

Deterministic Sampling-A New Technique for Fast Pattern Matching (UV), pp. 170–180.

STOC-1990-KaoK #algorithm #graph #parallel #performance #towards #transitive

Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs (MYK, PNK), pp. 181–192.

STOC-1990-CypherP #sorting

Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers (RC, CGP), pp. 193–203.

STOC-1990-Nisan #bound #generative

Psuedorandom Generators for Space-Bounded Computation (NN), pp. 204–212.

STOC-1990-NaorN #performance #probability

Small-bias Probability Spaces: Efficient Constructions and Applications (JN, MN), pp. 213–223.

STOC-1990-SchmidtS #analysis

The Analysis of Closed Hashing under Limited Randomness (JPS, AS), pp. 224–234.

STOC-1990-MansourNT #complexity

The Computational Complexity of Universal Hashing (YM, NN, PT), pp. 235–243.

STOC-1990-GilHW #constant

Not All Keys Can Be Hashed in Constant Time (JYG, FMadH, AW), pp. 244–253.

STOC-1990-Zuckerman #bound

A Technique for Lower Bounding the Cover Time (DZ), pp. 254–259.

STOC-1990-LinialN #approximate

Approximate Inclusion-Exclusion (NL, NN), pp. 260–270.

STOC-1990-Cleve #bound #simulation #source code #towards

Towards Optimal Simulations of Formulas by Bounded-Width Programs (RC), pp. 271–277.

STOC-1990-Szegedy #bound #communication #complexity #symmetry

Functions with Bounded Symmetric Communication Complexity and Circuits with mod m Gates (MS), pp. 278–286.

STOC-1990-RazW #linear

Monotone Circuits for Matching Require Linear Depth (RR, AW), pp. 287–292.

STOC-1990-AlonST #graph #theorem

A Separator Theorem for Graphs with an Excluded Minor and its Applications (NA, PDS, RT), pp. 293–299.

STOC-1990-MillerT

Separators in Two and Three Dimensions (GLM, WPT), pp. 300–309.

STOC-1990-KleinST #algorithm #approximate #concurrent #performance

Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities (PNK, CS, ÉT), pp. 310–321.

STOC-1990-Mulmuley #diagrams #order

Output Sensitive Construction of Levels and Voronoi Diagrams in R^d of Order 1 to k (KM), pp. 322–330.

STOC-1990-AggarwalHL #diagrams #problem

Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (AA, MH, FTL), pp. 331–340.

STOC-1990-KirkpatrickMY #multi #theorem

Quantitative Steinitz’s Theorems with Applications to Multifingered Grasping (DGK, BM, CKY), pp. 341–351.

STOC-1990-KarpVV #algorithm #online

An Optimal Algorithm for On-line Bipartite Matching (RMK, UVV, VVV), pp. 352–358.

STOC-1990-BernGRS #algorithm #online

Online Algorithms for Locating Checkpoints (MWB, DHG, AR, MS), pp. 359–368.

STOC-1990-CoppersmithDRS #algorithm #graph #online #random

Random Walks on Weighted Graphs, and Applications to On-line Algorithms (DC, PD, PR, MS), pp. 369–378.

STOC-1990-Ben-DavidBKTW #algorithm #on the #online #power of

On the Power of Randomization in Online Algorithms (SBD, AB, RMK, GT, AW), pp. 379–386.

STOC-1990-Rompel

One-Way Functions are Necessary and Sufficient for Secure Signatures (JR), pp. 387–394.

STOC-1990-Hastad #generative #pseudo

Pseudo-Random Generators under Uniform Assumptions (JH), pp. 395–404.

STOC-1990-SchriftS

The Discrete Log is Very Discreet (AWS, AS), pp. 405–415.

STOC-1990-FeigeS #protocol

Witness Indistinguishable and Witness Hiding Protocols (UF, AS), pp. 416–426.

STOC-1990-NaorY

Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks (MN, MY), pp. 427–437.

STOC-1990-PapadimitriouSY #complexity #on the

On the Complexity of Local Search (CHP, AAS, MY), pp. 438–445.

STOC-1990-PanconesiR #approximate #quantifier

Quantifiers and Approximation (AP, DR), pp. 446–456.

STOC-1990-OgiwaraW #bound #on the #polynomial #set

On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (MO, OW), pp. 457–467.

STOC-1990-KfouryTU #problem

The Undecidability of the Semi-Unification Problem (AJK, JT, PU), pp. 468–476.

STOC-1990-HarjuK #automaton #decidability #equivalence #finite #multi

Decidability of the Multiplicity Equivalence of Multitape Finite Automata (TH, JK), pp. 477–481.

STOC-1990-BellareMO #constant

Perfect Zero-Knowledge in Constant Rounds (MB, SM, RO), pp. 482–493.

STOC-1990-BellareMO90a #complexity #statistics

The (True) Complexity of Statistical Zero Knowledge (MB, SM, RO), pp. 494–502.

STOC-1990-BeaverMR #complexity #protocol

The Round Complexity of Secure Protocols (DB, SM, PR), pp. 503–513.

STOC-1990-Ostrovsky #performance

Efficient Computation on Oblivious RAMs (RO), pp. 514–523.

STOC-1990-KantorL

Computing in Quotient Groups (WMK, EML), pp. 524–534.

STOC-1990-BorodinT #decidability #on the #polynomial

On the Decidability of Sparse Univariate Polynomial Interpolation (AB, PT), pp. 535–545.

STOC-1990-Shoup #finite

Searching for Primitive Roots in Finite Fields (VS), pp. 546–554.

STOC-1990-Lakshman #complexity #on the

On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal (YNL), pp. 555–563.

STOC-1990-LenstraLMP

The Number Field Sieve (AKL, HWLJ, MSM, JMP), pp. 564–572.