Cris Koutsougeras, Jeffrey Scott Vitter
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing
STOC, 1991.

@proceedings{STOC-1991,
	address       = "New Orleans, Louisiana, USA",
	editor        = "Cris Koutsougeras and Jeffrey Scott Vitter",
	isbn          = "0-89791-397-3",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 23rd Annual ACM Symposium on Theory of Computing}",
	year          = 1991,
}

Contents (58 items)

12 ×#algorithm
6 ×#approximate
6 ×#parallel
6 ×#problem
5 ×#bound
4 ×#finite
4 ×#linear
4 ×#performance
3 ×#graph
3 ×#online

STOC-1991-BeigelRS

PP Is Closed Under Intersection (RB, NR, DAS), pp. 1–9.

STOC-1991-Ko #equation #polynomial

Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (KIK), pp. 10–20.

STOC-1991-BabaiFLS

Checking Computations in Polylogarithmic Time (LB, LF, LAL, MS), pp. 21–31.

STOC-1991-GemmellLRSW #approximate #self

Self-Testing/Correcting for Polynomials and for Approximate Functions (PG, RJL, RR, MS, AW), pp. 32–42.

STOC-1991-BarnesR #algorithm #polynomial #sublinear #using

Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (GB, WLR), pp. 43–53.

STOC-1991-Kaltofen #effectiveness

Effective Noether Irreducibility Forms and Applications (EK), pp. 54–63.

STOC-1991-Adleman #integer #using

Factoring Numbers Using Singular Integers (LMA), pp. 64–71.

STOC-1991-BuchmannS #finite

Constructing Nonresidues in Finite Fields and the Extended Riemann Hypothesis (JAB, VS), pp. 72–79.

STOC-1991-MenezesVO #finite

Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field (AM, SAV, TO), pp. 80–89.

STOC-1991-BabaiCFLS #algorithm #monte carlo #performance #permutation

Fast Monte Carlo Algorithms for Permutation Groups (LB, GC, LF, EML, ÁS), pp. 90–100.

STOC-1991-LeightonMPSTT #algorithm #approximate #multi #performance #problem

Fast Approximation Algorithms for Multicommodity Flow Problems (FTL, FM, SAP, CS, ÉT, ST), pp. 101–111.

STOC-1991-Gabow #approach

A Matroid Approach to Finding Edge Connectivity and Packing Arborescences (HNG), pp. 112–122.

STOC-1991-FederM #algorithm #clique #graph

Clique Partitions, Graph Compression, and Speeding-Up Algorithms (TF, RM), pp. 123–133.

STOC-1991-AgrawalKR #algorithm #approximate #network #problem

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks (AA, PNK, RR), pp. 134–144.

STOC-1991-CohenM #algorithm #difference #linear

Improved Algorithms for Linear Inequalities with Two Variables per Inequality (EC, NM), pp. 145–155.

STOC-1991-ApplegateK #integration

Sampling and Integration of Near Log-Concave functions (DA, RK), pp. 156–163.

STOC-1991-Babai #finite #generative #graph #random #transitive

Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups (LB), pp. 164–174.

STOC-1991-BrightwellW #linear

Counting Linear Extensions is #P-Complete (GB, PW), pp. 175–181.

STOC-1991-BroderFS

Finding Hidden Hamiltonian Cycles (AZB, AMF, ES), pp. 182–189.

STOC-1991-Karp #probability

Probabilistic Recurrence Relations (RMK), pp. 190–197.

STOC-1991-Shapiro #category theory #concurrent

Separating Concurrent Languages with Categories of Language Embeddings (EYS), pp. 198–208.

STOC-1991-AbiteboulV #complexity

Generic Computation and Its Complexity (SA, VV), pp. 209–219.

STOC-1991-Harel #graph #infinity

Hamiltonian Paths in Infinite Graphs (DH), pp. 220–229.

STOC-1991-CoffmanCGJMSWY #analysis #case study

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study (EGCJ, CC, MRG, DSJ, LAM, PWS, RRW, MY), pp. 230–240.

STOC-1991-CoffmanG #proving #scheduling

Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling (EGCJ, MRG), pp. 241–248.

STOC-1991-BorodinIRS #locality

Competitive Paging with Locality of Reference (AB, SI, PR, BS), pp. 249–259.

STOC-1991-Grove #algorithm #online

The Harmonic Online K-Server Algorithm Is Competitive (EFG), pp. 260–266.

STOC-1991-Kahan

A Model for Data in Motion (SK), pp. 267–277.

STOC-1991-KarloffRR #algorithm #bound #random

Lower Bounds for Randomized k-Server and Motion Planning Algorithms (HJK, YR, YR), pp. 278–288.

STOC-1991-DengM #game studies #infinity #online #problem

Infinite Games, Randomization, Computability, and Applications to Online Problems (XD, SM), pp. 289–298.

STOC-1991-Hagerup #integer #parallel #sorting

Constant-Time Parallel Integer Sorting (TH), pp. 299–306.

STOC-1991-MatiasV #parallel #probability

Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (YM, UV), pp. 307–316.

STOC-1991-GalilI #algorithm #problem

Fully Dynamic Algorithms for Edge-Connectivity Problems (ZG, GFI), pp. 317–327.

STOC-1991-BlumJLTY #approximate #linear #string

Linear Approximation of Shortest Superstrings (AB, TJ, ML, JT, MY), pp. 328–336.

STOC-1991-DjidjevR #algorithm #performance #problem

An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs (HD, JHR), pp. 337–347.

STOC-1991-AspnesHS #coordination #multi #network

Counting Networks and Multi-Processor Coordination (JA, MH, NS), pp. 348–358.

STOC-1991-AttiyaDLS #bound #nondeterminism

Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty (HA, CD, NAL, LJS), pp. 359–369.

STOC-1991-AndersonW #algorithm #parallel #problem

Wait-free Parallel Algorithms for the Union-Find Problem (RJA, HW), pp. 370–380.

STOC-1991-KedemPRS #parallel #performance

Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing (ZMK, KVP, AR, PGS), pp. 381–390.

STOC-1991-CheriyanT #algorithm #parallel

Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (JC, RT), pp. 391–401.

STOC-1991-AspnesBFR #power of

The Expressive Power of Voting Polynomials (JA, RB, MLF, SR), pp. 402–409.

STOC-1991-Nisan #bound #commutative

Lower Bounds for Non-Commutative Computation (NN), pp. 410–418.

STOC-1991-NisanW #communication #complexity #revisited

Rounds in Communication Complexity Revisited (NN, AW), pp. 419–429.

STOC-1991-LubyV #approximate #on the

On Deterministic Approximation of DNF (ML, BV), pp. 430–438.

STOC-1991-BreslauerG #bound #parallel #string

A Lower Bound for Parallel String Matching (DB, ZG), pp. 439–443.

STOC-1991-AngluinK #query #question

When Won’t Membership Queries Help? (DA, MK), pp. 444–454.

STOC-1991-KushilevitzM #fourier #learning #using

Learning Decision Trees Using the Fourier Sprectrum (EK, YM), pp. 455–464.

STOC-1991-LittlestoneLW #learning #linear #online

On-Line Learning of Linear Functions (NL, PML, MKW), pp. 465–475.

STOC-1991-YannakakisL #finite #state machine #testing

Testing Finite State Machines (MY, DL), pp. 476–485.

STOC-1991-AslamD #bound #fault

Searching in the Presence of Linearly Bounded Errors (JAA, AD), pp. 486–493.

STOC-1991-BlumRS #geometry #navigation

Navigating in Unfamiliar Geometric Terrain (AB, PR, BS), pp. 494–504.

STOC-1991-Matousek #approximate #divide and conquer #geometry

Approximations and Optimal Geometric Divide-And-Conquer (JM), pp. 505–511.

STOC-1991-Mulmuley

Hidden Surface Removal with Respect to a Moving View Point (KM), pp. 512–522.

STOC-1991-GoodrichT

Dynamic Trees and Dynamic Point Location (MTG, RT), pp. 523–533.

STOC-1991-FiatN #trade-off

Rigorous Time/Space Tradeoffs for Inverting Functions (AF, MN), pp. 534–541.

STOC-1991-DolevDN #encryption

Non-Malleable Cryptography (DD, CD, MN), pp. 542–552.

STOC-1991-Kilian #game studies #theorem

A General Completeness Theorem for Two-Party Games (JK), pp. 553–560.

STOC-1991-Maurer #encryption #independence #security

Perfect Cryptographic Security from Partially Independent Channels (UMM), pp. 561–571.