S. Rao Kosaraju, Mike Fellows, Avi Wigderson, John A. Ellis
Proceedings of the 24th Annual ACM Symposium on Theory of Computing
STOC, 1992.

@proceedings{STOC-1992,
	address       = "Victoria, British Columbia, Canada",
	editor        = "S. Rao Kosaraju and Mike Fellows and Avi Wigderson and John A. Ellis",
	isbn          = "0-89791-511-9",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 24th Annual ACM Symposium on Theory of Computing}",
	year          = 1992,
}

Contents (75 items)

11 ×#algorithm
8 ×#performance
7 ×#on the
7 ×#parallel
6 ×#approximate
6 ×#complexity
6 ×#network
6 ×#random
5 ×#distributed
5 ×#graph

STOC-1992-AzarBKLP #random

Biased Random Walks (YA, AZB, ARK, NL, SP), pp. 1–9.

STOC-1992-EvenGLNV #approximate #independence

Approximations of General Independent Distributions (GE, OG, ML, NN, BV), pp. 10–16.

STOC-1992-Schulman

Sample Spaces Uniform on Neighborhoods (LJS), pp. 17–25.

STOC-1992-FederM

Balanced Matroids (TF, MM), pp. 26–38.

STOC-1992-BartalFR #algorithm #data transformation #distributed

Competitive Algorithms for Distributed Data Management (YB, AF, YR), pp. 39–50.

STOC-1992-BartalFKV #algorithm #problem #scheduling

New Algorithms for an Ancient Scheduling Problem (YB, AF, HJK, RV), pp. 51–58.

STOC-1992-AmirBF #2d #independence

Alphabet Independent Two Dimensional Matching (AA, GB, MF), pp. 59–68.

STOC-1992-Galil #algorithm #parallel #string

A Constant-Time Optimal Parallel String-Matching Algorithm (ZG), pp. 69–76.

STOC-1992-Leighton #parallel

Methods for Message Routing in Parallel Machines (FTL), pp. 77–96.

STOC-1992-GathenS

Computing Frobenius Maps and Factoring Polynomials (JvzG, VS), pp. 97–105.

STOC-1992-Cai #parallel

Parallel Computation Over Hyperbolic Groups (JyC), pp. 106–115.

STOC-1992-BealsS #composition #linear

Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time (RB, ÁS), pp. 116–125.

STOC-1992-Barvinok #equation #polynomial #testing

Feasibility Testing for Systems of Real Quadratic Equations (AIB), pp. 126–132.

STOC-1992-Lin #communication #fault tolerance #network

Fault Tolerant Planar Communication Networks (GL), pp. 133–139.

STOC-1992-BroderFU #graph

Existence and Construction of Edge Disjoint Paths on Expander Graphs (AZB, AMF, EU), pp. 140–149.

STOC-1992-MaggsS #algorithm #bound #network

Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (BMM, RKS), pp. 150–161.

STOC-1992-AumannB #array

Computing with Faulty Arrays (YA, MBO), pp. 162–169.

STOC-1992-BjornerLY #bound #linear

Linear Decision Trees: Volume Estimates and Topological Bounds (AB, LL, ACCY), pp. 170–177.

STOC-1992-KahnK #sorting

Entropy and Sorting (JK, JHK), pp. 178–187.

STOC-1992-BeameL #communication #complexity #nondeterminism #random

Randomized versus Nondeterministic Communication Complexity (PB, JL), pp. 188–199.

STOC-1992-BeameIKPPW #bound #exponential #principle

Exponential Lower Bounds for the Pigeonhole Principle (PB, RI, JK, TP, PP, ARW), pp. 200–220.

STOC-1992-Reed #approximate

Finding Approximate Separators and Computing Tree Width Quickly (BAR), pp. 221–228.

STOC-1992-Rao #algorithm #graph #performance

Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (SR), pp. 229–240.

STOC-1992-DahlhausJPSY #complexity #multi

The Complexity of Multiway Cuts (ED, DSJ, CHP, PDS, MY), pp. 241–251.

STOC-1992-DorT #composition #graph #proving

Graph Decomposition Is NPC-A Complete Proof of Holyer’s Conjecture (DD, MT), pp. 252–263.

STOC-1992-LeeY #online

Online Minimization of Transition Systems (DL, MY), pp. 264–274.

STOC-1992-Safra #automaton #exponential

Exponential Determinization for ω-Automata with Strong-Fairness Acceptance Condition (SS), pp. 275–282.

STOC-1992-BellantoniC #recursion

A New Recursion-Theoretic Characterization of the Polytime Functions (SB, SAC), pp. 283–293.

STOC-1992-GroveHK #first-order #logic

Asymptotic Conditional Probabilities for First-Order Logic (AJG, JYH, DK), pp. 294–305.

STOC-1992-KedemPRR #parallel #performance #program transformation

Efficient Program Transformations for Resilient Parallel Computation via Randomization (ZMK, KVP, MOR, AR), pp. 306–317.

STOC-1992-KarpLH #distributed #memory management #performance #simulation

Efficient PRAM Simulation on a Distributed Memory Machine (RMK, ML, FMadH), pp. 318–326.

STOC-1992-AjtaiM #algorithm #linear #programming

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension (MA, NM), pp. 327–338.

STOC-1992-Kelsen #complexity #independence #on the #parallel #set

On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph (PK), pp. 339–350.

STOC-1992-Angluin #learning #overview

Computational Learning Theory: Survey and Selected Bibliography (DA), pp. 351–369.

STOC-1992-BshoutyHH #learning

Learning Arithmetic Read-Once Formulas (NHB, TRH, LH), pp. 370–381.

STOC-1992-BlumR #learning #performance #query

Fast Learning of k-Term DNF Formulas with Queries (AB, SR), pp. 382–389.

STOC-1992-Ben-David #detection #finite #question

Can Finite Samples Detect Singularities of Real-Valued Functions? (SBD), pp. 390–399.

STOC-1992-Lindell #algorithm

A Logspace Algorithm for Tree Canonization (SL), pp. 400–404.

STOC-1992-Plaxton #network #sorting

A Hypercubic Sorting Network with Nearly Logarithmic Depth (CGP), pp. 405–416.

STOC-1992-KlugermanP #network

Small-Depth Counting Networks (MK, CGP), pp. 417–428.

STOC-1992-PatersonZ #multi

Shallow Multiplication Circuits and Wise Financial Investments (MP, UZ), pp. 429–437.

STOC-1992-BabaiBT #complexity #symmetry

Symmetry and Complexity (LB, RB, PTN), pp. 438–449.

STOC-1992-Beigel

When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One (RB), pp. 450–454.

STOC-1992-BarringtonBR #representation

Representing Boolean Functions as Polynomials Modulo Composite Numbers (DAMB, RB, SR), pp. 455–461.

STOC-1992-NisanS #on the

On the Degree of Boolean Functions as Real Polynomials (NN, MS), pp. 462–467.

STOC-1992-Paturi #approximate #on the #symmetry

On the Degree of Polynomials that Approximate Symmetric Boolean Functions (RP), pp. 468–474.

STOC-1992-Kalai #algorithm #random

A Subexponential Randomized Simplex Algorithm (GK), pp. 475–482.

STOC-1992-AdlerB #algebra #algorithm #linear #polynomial #programming

Polynomial Algorithms for Linear Programming over the Algebraic Numbers (IA, PAB), pp. 483–494.

STOC-1992-GalilIS #testing

Fully Dynamic Planarity Testing (ZG, GFI, NS), pp. 495–506.

STOC-1992-Goodrich #parallel

Planar Separators and Parallel Polygon Triangulation (MTG), pp. 507–516.

STOC-1992-AgarwalM #parametricity

Ray Shooting and Parametric Search (PKA, JM), pp. 517–526.

STOC-1992-MalitzP #graph #on the

On the Angular Resolution of Planar Graphs (SMM, AP), pp. 527–538.

STOC-1992-LoMS

Ham-Sandwich Cuts in R^d (CYL, JM, WLS), pp. 539–545.

STOC-1992-CallahanK #composition #multi #nearest neighbour

A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields (PBC, SRK), pp. 546–556.

STOC-1992-AwerbuchPPS #adaptation #network

Adapting to Asynchronous Dynamic Networks (BA, BPS, DP, MES), pp. 557–570.

STOC-1992-AwerbuchKP #distributed #scheduling

Competitive Distributed Job Scheduling (BA, SK, DP), pp. 571–580.

STOC-1992-PanconesiS #algorithm #composition #distributed #network #problem

Improved Distributed Algorithms for Coloring and Network Decomposition Problems (AP, AS), pp. 581–592.

STOC-1992-ChoyS #algorithm #distributed #fault tolerance #performance #resource management

Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems (MC, AKS), pp. 593–602.

STOC-1992-Sipser

The History and Status of the P versus NP Question (MS), pp. 603–618.

STOC-1992-Nisan

RL ⊆ SC (NN), pp. 619–623.

STOC-1992-SimonS #complexity #on the #ram #set

On the Complexity of RAM with Various Operation Sets (JS, MS), pp. 624–631.

STOC-1992-VenkatesanR #matrix #problem

Average Case Intractability of Matrix and Diophantine Problems (RV, SR), pp. 632–642.

STOC-1992-FeigeL #matrix #on the #random

On the Hardness of Computing the Permanent of Random Matrices (UF, CL), pp. 643–654.

STOC-1992-DworkW #bound #concurrent #exclamation #performance

Simple and Efficient Bounded Concurrent Timestamping or Bounded Concurrent Timestamp Systems are Comprehensible! (CD, OW), pp. 655–666.

STOC-1992-MayerOOY #self #symmetry

Self-Stabilizing Symmetry Breaking in Constant-Space (AJM, YO, RO, MY), pp. 667–678.

STOC-1992-AttiyaF #correctness #multi

A Correctness Condition for High-Performance Multiprocessors (HA, RF), pp. 679–690.

STOC-1992-BrightwellOW #random

Target Shooting with Programmed Random Variables (GB, TJO, PW), pp. 691–698.

STOC-1992-FranklinY #communication #complexity

Communication Complexity of Secure Computation (MKF, MY), pp. 699–710.

STOC-1992-BellareP #performance #proving

Making Zero-Knowledge Provers Efficient (MB, EP), pp. 711–722.

STOC-1992-Kilian #performance #proving

A Note on Efficient Zero-Knowledge Proofs and Arguments (JK), pp. 723–732.

STOC-1992-FeigeL92a #problem #proving

Two-Prover One-Round Proof Systems: Their Power and Their Problems (UF, LL), pp. 733–744.

STOC-1992-Seidel #on the #problem

On the All-Pairs-Shortest-Path Problem (RS), pp. 745–749.

STOC-1992-KleinS #approximate #parallel #random

A Parallel Randomized Approximation Scheme for Shortest Paths (PNK, SS), pp. 750–758.

STOC-1992-KhullerV #approximate #graph

Biconnectivity Approximations and Graph Carvings (SK, UV), pp. 759–770.

STOC-1992-LinV #approximate #constraints

epsilon-Approximations with Minimum Packing Constraint Violation (JHL, JSV), pp. 771–782.