## 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)

- 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.

12 ×#algorithm

6 ×#approximate

6 ×#parallel

6 ×#problem

5 ×#bound

4 ×#finite

4 ×#linear

4 ×#performance

3 ×#graph

3 ×#online

6 ×#approximate

6 ×#parallel

6 ×#problem

5 ×#bound

4 ×#finite

4 ×#linear

4 ×#performance

3 ×#graph

3 ×#online