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

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

13 ×#algorithm

9 ×#approximate

8 ×#graph

7 ×#multi

7 ×#problem

6 ×#network

6 ×#performance

5 ×#bound

5 ×#linear

4 ×#learning

9 ×#approximate

8 ×#graph

7 ×#multi

7 ×#problem

6 ×#network

6 ×#performance

5 ×#bound

5 ×#linear

4 ×#learning