S. Rao Kosaraju, David S. Johnson, Alok Aggarwal
Proceedings of the 25th Annual ACM Symposium on Theory of Computing
STOC, 1993.

@proceedings{STOC-1993,
	address       = "San Diego, California, USA",
	editor        = "S. Rao Kosaraju and David S. Johnson and Alok Aggarwal",
	isbn          = "0-89791-591-7",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 25th Annual ACM Symposium on Theory of Computing}",
	year          = 1993,
}

Contents (86 items)

13 ×#algorithm
9 ×#approximate
8 ×#graph
7 ×#multi
7 ×#problem
6 ×#network
6 ×#performance
5 ×#bound
5 ×#linear
4 ×#learning

STOC-1993-ChouK #2d #complexity

Some complexity issues on the simply connected regions of the two-dimensional plane (AWC, KIK), pp. 1–10.

STOC-1993-BernsteinV #complexity #quantum

Quantum complexity theory (EB, UVV), pp. 11–20.

STOC-1993-BennettGLVZ #distance

Thermodynamics of computation and information distance (CHB, PG, ML, PMBV, WHZ), pp. 21–30.

STOC-1993-GarayM #polynomial

Fully polynomial Byzantine agreement in t+1 rounds (JAG, YM), pp. 31–41.

STOC-1993-CanettiR #performance

Fast asynchronous Byzantine agreement with optimal resilience (RC, TR), pp. 42–51.

STOC-1993-Ben-OrCG

Asynchronous secure computation (MBO, RC, OG), pp. 52–61.

STOC-1993-JiangL #string

k one-way heads cannot do string-matching (TJ, ML), pp. 62–70.

STOC-1993-Baker #algorithm #formal method #pattern matching

A theory of parameterized pattern matching: algorithms and applications (BSB), pp. 71–80.

STOC-1993-IduryS #multi

Multiple matching of rectangular patterns (RMI, AAS), pp. 81–90.

STOC-1993-BorowskyG

Generalized FLP impossibility result for t-resilient asynchronous computations (EB, EG), pp. 91–100.

STOC-1993-SaksZ

Wait-free k-set agreement is impossible: the topology of public knowledge (MES, FZ), pp. 101–110.

STOC-1993-HerlihyS #theorem

The asynchronous computability theorem for t-resilient tasks (MH, NS), pp. 111–120.

STOC-1993-PapadimitriouY #linear #matrix #programming

Linear programming without the matrix (CHP, MY), pp. 121–129.

STOC-1993-BorgstromK #fault

Comparison-based search in the presence of errors (RSB, SRK), pp. 130–136.

STOC-1993-FarachKW #robust

A robust model for finding optimal evolutionary trees (MF, SK, TW), pp. 137–145.

STOC-1993-FelsnerW #algorithm #combinator #set

Maximum k-chains in planar point sets: combinatorial structure and algorithms (SF, LW), pp. 146–153.

STOC-1993-KushilevitzMRZ #bound #random

Lower bounds for randomized mutual exclusion (EK, YM, MOR, DZ), pp. 154–163.

STOC-1993-AwerbuchBF #distributed

Competitive distributed file allocation (BA, YB, AF), pp. 164–173.

STOC-1993-DworkHW #algorithm #memory management

Contention in shared memory algorithms (CD, MH, OW), pp. 174–183.

STOC-1993-NaorS #question #what

What can be computed locally? (MN, LJS), pp. 184–193.

STOC-1993-CohenBKT #data type #query

Reinventing the wheel: an optimal data structure for connectivity queries (RFC, GDB, AK, RT), pp. 194–200.

STOC-1993-SzegedyV #graph #locality

Locality based graph coloring (MS, SV), pp. 201–207.

STOC-1993-EppsteinGIS #algorithm #graph

Separator based sparsification for dynamic planar graph algorithms (DE, ZG, GFI, THS), pp. 208–217.

STOC-1993-Goldberg #algorithm #graph #polynomial #product line

Polynomial space polynomial delay algorithms for listing families of graphs (LAG), pp. 218–225.

STOC-1993-Bodlaender #algorithm #linear

A linear time algorithm for finding tree-decompositions of small treewidth (HLB), pp. 226–234.

STOC-1993-NisanZ #simulation

More deterministic simulation in logspace (NN, DZ), pp. 235–244.

STOC-1993-WigdersonZ #bound

Expanders that beat the eigenvalue bound: explicit construction and applications (AW, DZ), pp. 245–251.

STOC-1993-BoppanaN #problem

The biased coin problem (RBB, BON), pp. 252–257.

STOC-1993-LinialLSZ #combinator #performance #set

Efficient construction of a small hitting set for combinatorial rectangles in high dimension (NL, ML, MES, DZ), pp. 258–267.

STOC-1993-KollerM #constraints

Constructing small sample spaces satisfying given constraints (DK, NM), pp. 268–277.

STOC-1993-Karp #biology #combinator #problem

Mapping the genome: some combinatorial problems arising in molecular biology (RMK), pp. 278–285.

STOC-1993-LundY #approximate #on the #problem

On the hardness of approximating minimization problems (CL, MY), pp. 286–293.

STOC-1993-BellareGLR #approximate #performance #proving

Efficient probabilistically checkable proofs and applications to approximations (MB, SG, CL, AR), pp. 294–304.

STOC-1993-CondonFLS #algorithm #approximate

Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (AC, JF, CL, PWS), pp. 305–314.

STOC-1993-FreundKRRSS #automaton #finite #learning #performance #random

Efficient learning of typical finite automata from random walks (YF, MJK, DR, RR, RES, LS), pp. 315–324.

STOC-1993-MacintyreS #network

Finiteness results for sigmoidal “neural” networks (AM, EDS), pp. 325–334.

STOC-1993-Maass #bound #complexity #learning

Bounds for the computational power and learning complexity of analog neural nets (WM), pp. 335–344.

STOC-1993-BaruahCPV #resource management

Proportionate progress: a notion of fairness in resource allocation (SKB, NKC, CGP, DAV), pp. 345–354.

STOC-1993-Pippenger #self

Self-routing superconcentrators (NP), pp. 355–361.

STOC-1993-BlumofeL #parallel #scheduling #thread

Space-efficient scheduling of multithreaded computations (RDB, CEL), pp. 362–371.

STOC-1993-Kharitonov #encryption #learning

Cryptographic hardness of distribution-specific learning (MK), pp. 372–381.

STOC-1993-Cesa-BianchiFHHSW #how

How to use expert advice (NCB, YF, DPH, DH, RES, MKW), pp. 382–391.

STOC-1993-Kearns #learning #performance #query #statistics

Efficient noise-tolerant learning from statistical queries (MJK), pp. 392–401.

STOC-1993-PhillipsW #network #online

Online load balancing and network flow (SP, JW), pp. 402–411.

STOC-1993-CoffmanJSW #analysis #markov #proving

Markov chains, computer proofs, and average-case analysis of best fit bin packing (EGCJ, DSJ, PWS, RRW), pp. 412–421.

STOC-1993-BernGR #algorithm #online

On-line algorithms for cache sharing (MWB, DHG, AR), pp. 422–430.

STOC-1993-BattistaV #graph

Angles of planar triangular graphs (GDB, LV), pp. 431–437.

STOC-1993-RaviMRRH #algorithm #approximate #multi

Many birds with one stone: multi-objective approximation algorithms (RR, MVM, SSR, DJR, HBHI), pp. 438–447.

STOC-1993-LubyN #algorithm #approximate #linear #parallel #programming

A parallel approximation algorithm for positive linear programming (ML, NN), pp. 448–457.

STOC-1993-ChariRS #problem

Randomness-optimal unique element isolation, with applications to perfect matching and related problems (SC, PR, AS), pp. 458–467.

STOC-1993-Fleischer

Decision trees: old and new results (RF), pp. 468–477.

STOC-1993-MatousekS #3d #algorithm #problem

A deterministic algorithm for the three-dimensional diameter problem (JM, OS), pp. 478–484.

STOC-1993-HershbergerS #matrix #metric

Matrix searching with the shortest path metric (JH, SS), pp. 485–494.

STOC-1993-ChazelleEGGSW #bound #set

Improved bounds on weak epsilon-nets for convex sets (BC, HE, MG, LJG, MS, EW), pp. 495–504.

STOC-1993-BergMS #linear

Piecewise linear paths among convex obstacles (MdB, JM, OS), pp. 505–514.

STOC-1993-AllenderJ #commutative #reduction

Depth reduction for noncommutative arithmetic circuits (EA, JJ), pp. 515–522.

STOC-1993-PudlakR

Modified ranks of tensors and the size of circuits (PP, VR), pp. 523–531.

STOC-1993-KarchmerW #nondeterminism

Characterizing non-deterministic circuit size (MK, AW), pp. 532–540.

STOC-1993-ImpagliazzoPS #trade-off

Size-depth trade-offs for threshold circuits (RI, RP, MES), pp. 541–550.

STOC-1993-GoldmannK #simulation

Simulating threshold circuits by majority circuits (MG, MK), pp. 551–560.

STOC-1993-ColeMS #array #configuration management #fault #multi #self

Multi-scale self-simulation: a technique for reconfiguring arrays with faults (RC, BMM, RKS), pp. 561–572.

STOC-1993-BorodinRSU #hardware #how #question

How much can hardware help routing? (AB, PR, BS, EU), pp. 573–582.

STOC-1993-AlonCG #graph #permutation

Routing permutations on graphs via matchings (NA, FRKC, RLG), pp. 583–591.

STOC-1993-AlurHV #parametricity #realtime #reasoning

Parametric real-time reasoning (RA, TAH, MYV), pp. 592–601.

STOC-1993-Jones #constant #matter

Constant time factors do matter (NDJ), pp. 602–611.

STOC-1993-FederV #constraints #monad

Monotone monadic SNP and constraint satisfaction (TF, MYV), pp. 612–622.

STOC-1993-AspnesAFPW #online #scheduling

On-line load balancing with applications to machine scheduling and virtual circuit routing (JA, YA, AF, SAP, OW), pp. 623–631.

STOC-1993-AielloAMR #approximate #network

Approximate load balancing on dynamic and asynchronous networks (WA, BA, BMM, SR), pp. 632–641.

STOC-1993-FeldmannKST #dependence #online #parallel #scheduling

Optimal online scheduling of parallel jobs with dependencies (AF, MYK, JS, SHT), pp. 642–651.

STOC-1993-AwerbuchKMPV #self

Time optimal self-stabilizing synchronization (BA, SK, YM, BPS, GV), pp. 652–661.

STOC-1993-CooperL #linear #performance #protocol

Fast perfection-information leader-election protocol with linear immunity (JC, NL), pp. 662–671.

STOC-1993-RackoffS #analysis #encryption

Cryptographic defense against traffic analysis (CR, DRS), pp. 672–681.

STOC-1993-KleinPR #composition #multi #network

Excluded minors, network decomposition, and multicommodity flow (PNK, SAP, SR), pp. 682–690.

STOC-1993-PlotkinT #bound #multi

Improved bounds on the max-flow min-cut ratio for multicommodity flows (SAP, ÉT), pp. 691–697.

STOC-1993-GargVY #approximate #multi #theorem

Approximate max-flow min-(multi)cut theorems and their applications (NG, VVV, MY), pp. 698–707.

STOC-1993-WilliamsonGMV #algorithm #approximate #network #problem

A primal-dual approximation algorithm for generalized Steiner network problems (DPW, MXG, MM, VVV), pp. 708–717.

STOC-1993-Edmonds #trade-off

Time-space trade-offs for undirected st-connectivity on a JAG (JE), pp. 718–727.

STOC-1993-BarnesF #graph #random

Short random walks on graphs (GB, UF), pp. 728–737.

STOC-1993-KenyonRS #graph

Matchings in lattice graphs (CK, DR, AS), pp. 738–746.

STOC-1993-Schulman #communication #interactive

Deterministic coding for interactive communication (LJS), pp. 747–756.

STOC-1993-KargerS #algorithm

An O~(n2) algorithm for minimum cuts (DRK, CS), pp. 757–765.

STOC-1993-ParkP #graph

Finding minimum-quotient cuts in planar graphs (JKP, CAP), pp. 766–775.

STOC-1993-Phillips #network #problem

The network inhibition problem (CAP), pp. 776–785.

STOC-1993-ArBCG #approximate

Checking approximate computations over the reals (SA, MB, BC, PG), pp. 786–795.

STOC-1993-Shamir #generative #multi #on the

On the generation of multivariate polynomials which are hard to factor (AS), pp. 796–804.

STOC-1993-GathenKS

Counting curves and their projections (JvzG, MK, IS), pp. 805–812.