## Frank Thomson Leighton, Allan Borodin

*Proceedings of the 27th Annual ACM Symposium on Theory of Computing*

STOC, 1995.

@proceedings{STOC-1995, address = "Las Vegas, Nevada, USA", editor = "Frank Thomson Leighton and Allan Borodin", isbn = "0-89791-718-9", publisher = "{ACM}", title = "{Proceedings of the 27th Annual ACM Symposium on Theory of Computing}", year = 1995, }

### Contents (78 items)

- STOC-1995-KhullerR #algorithm #approximate #problem
- Improved approximation algorithms for uniform connectivity problems (SK, BR), pp. 1–10.
- STOC-1995-Karger #approximate #network #polynomial #problem #random #reliability
- A randomized fully polynomial time approximation scheme for the all terminal network reliability problem (DRK), pp. 11–17.
- STOC-1995-KargerP #combinator #constraints #multi #optimisation #problem
- Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows (DRK, SAP), pp. 18–25.
- STOC-1995-KleinbergT #approximate #network #problem
- Approximations for the disjoint paths problem in high-diameter planar networks (JMK, ÉT), pp. 26–35.
- STOC-1995-FranklinY #privacy
- Secure hypergraphs: privacy from partial broadcast (MKF, MY), pp. 36–44.
- STOC-1995-BellareGG #encryption #incremental
- Incremental cryptography and application to virus protection (MB, OG, SG), pp. 45–56.
- STOC-1995-BellareR
- Provably secure session key distribution: the three party case (MB, PR), pp. 57–66.
- STOC-1995-Yao #metric #protocol #quantum #security
- Security of quantum protocols against coherent measurements (ACCY), pp. 67–75.
- STOC-1995-LovaszW #markov #performance
- Efficient stopping rules for Markov chains (LL, PW), pp. 76–82.
- STOC-1995-RabaniRS
- A computational view of population genetics (YR, YR, AS), pp. 83–92.
- STOC-1995-KaplanT #persistent #recursion
- Persistent lists with catenation via recursive slow-down (HK, RET), pp. 93–102.
- STOC-1995-MiltersenNSW #communication #complexity #data type #on the #symmetry
- On data structures and asymmetric communication complexity (PBM, NN, SS, AW), pp. 103–111.
- STOC-1995-DiaconisS #algorithm #question #what
- What do we know about the Metropolis algorithm? (PD, LSC), pp. 112–129.
- STOC-1995-Ponzio #bound #branch #integer #multi #source code
- A lower bound for integer multiplication with read-once branching programs (SP), pp. 130–139.
- STOC-1995-NisanT #symmetry
- Symmetric logspace is closed under complement (NN, ATS), pp. 140–146.
- STOC-1995-EdmondsP #bound
- A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model (JE, CKP), pp. 147–156.
- STOC-1995-HartI #performance
- Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (WEH, SI), pp. 157–168.
- STOC-1995-KosarajuD #assembly #scalability #string
- Large-scale assembly of DNA strings and space-efficient construction of suffix trees (SRK, ALD), pp. 169–177.
- STOC-1995-HannenhalliP #algorithm #permutation #polynomial #sorting
- Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals (SH, PAP), pp. 178–189.
- STOC-1995-HellersteinPRW #how #query #question
- How many queries are needed to learn? (LH, KP, VR, DW), pp. 190–199.
- STOC-1995-KarpinskiM #bound #network #polynomial
- Polynomial bounds for VC dimension of sigmoidal neural networks (MK, AM), pp. 200–208.
- STOC-1995-KivinenW #linear #predict
- Additive versus exponentiated gradient updates for linear prediction (JK, MKW), pp. 209–218.
- STOC-1995-BshoutyT #fourier #on the
- On the Fourier spectrum of monotone functions (NHB, CT), pp. 219–228.
- STOC-1995-RaghavanU #probability
- Stochastic contention resolution with short delays (PR, EU), pp. 229–237.
- STOC-1995-AdlerCMR #parallel #random
- Parallel randomized load balancing (MA, SC, MM, LER), pp. 238–247.
- STOC-1995-Harchol-BalterW #bound #network
- Bounding delays in packet-routing networks (MHB, DW), pp. 248–257.
- STOC-1995-MansourP
- Many-to-one packet routing on grids (YM, BPS), pp. 258–267.
- STOC-1995-Srinivasan #approximate #problem
- Improved approximations of packing and covering problems (AS), pp. 268–276.
- STOC-1995-AwerbuchABV #approximate
- Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen (BA, YA, AB, SV), pp. 277–283.
- STOC-1995-AroraKK #approximate #np-hard #polynomial #problem
- Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.
- STOC-1995-BlumCV #approximate #problem
- A constant-factor approximation for the k-MST problem in the plane (AB, PC, SV), pp. 294–302.
- STOC-1995-BeameCEIP #complexity #problem
- The relative complexity of NP search problems (PB, SAC, JE, RI, TP), pp. 303–314.
- STOC-1995-GradelM #complexity
- Descriptive complexity theory over the real numbers (EG, KM), pp. 315–324.
- STOC-1995-Wang #problem #word
- Average-case completeness of a word problem for groups (JW), pp. 325–334.
- STOC-1995-CuckerKKLW #on the #turing machine
- On real Turing machines that toss coins (FC, MK, PK, TL, KW), pp. 335–342.
- STOC-1995-AgarwalRT
- Motion planning for a steering-constrained robot through moderate obstacles (PKA, PR, HT), pp. 343–352.
- STOC-1995-KavrakiLMR #query #random
- Randomized query processing in robot path planning (LEK, JCL, RM, PR), pp. 353–362.
- STOC-1995-AlurCY #nondeterminism #probability #testing
- Distinguishing tests for nondeterministic and probabilistic machines (RA, CC, MY), pp. 363–372.
- STOC-1995-HenzingerKPV #automaton #decidability #hybrid #question #what
- What’s decidable about hybrid automata? (TAH, PWK, AP, PV), pp. 373–382.
- STOC-1995-Pulleyblank #problem
- Two Steiner tree packing problems (WRP), pp. 383–387.
- STOC-1995-Spielman #linear
- Linear-time encodable and decodable error-correcting codes (DAS), pp. 388–397.
- STOC-1995-KaltofenS #finite
- Subquadratic-time factoring of polynomials over finite fields (EK, VS), pp. 398–406.
- STOC-1995-Ergun #generative #linear #multi #testing
- Testing multivariate linear functions: overcoming the generator bottleneck (FE), pp. 407–416.
- STOC-1995-AnderssonHP #array #bound
- A tight lower bound for searching a sorted array (AA, JH, OP), pp. 417–426.
- STOC-1995-AnderssonHNR #linear #question #sorting
- Sorting in linear time? (AA, TH, SN, RR), pp. 427–436.
- STOC-1995-KahaleLMPSS #bound #network #sorting
- Lower bounds for sorting networks (NK, FTL, YM, CGP, TS, ES), pp. 437–446.
- STOC-1995-Raz #parallel #theorem
- A parallel repetition theorem (RR), pp. 447–456.
- STOC-1995-FeigeK #proving #random
- Impossibility results for recycling random bits in two-prover proof systems (UF, JK), pp. 457–468.
- STOC-1995-AielloBV #statistics
- Knowledge on the average-perfect, statistical and logarithmic (WA, MB, RV), pp. 469–478.
- STOC-1995-SaksSZ
- Explicit dispersers with polylog degree (MES, AS, SZ), pp. 479–488.
- STOC-1995-AryaDMSS
- Euclidean spanners: short, thin, and lanky (SA, GD, DMM, JSS, MHMS), pp. 489–498.
- STOC-1995-GalilY #theorem
- Short length versions of Menger’s theorem (ZG, XY), pp. 499–508.
- STOC-1995-DinitzN #graph #incremental #maintenance
- A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance (YD, ZN), pp. 509–518.
- STOC-1995-HenzingerK #algorithm #graph #random
- Randomized dynamic graph algorithms with polylogarithmic time per operation (MRH, VK), pp. 519–527.
- STOC-1995-DolevKKP #adaptation #named #network #performance
- Bubbles: adaptive routing scheme for high-speed dynamic networks (SD, EK, DK, DP), pp. 528–537.
- STOC-1995-AfekDT #performance
- Wait-free made fast (YA, DD, DT), pp. 538–547.
- STOC-1995-GhoshLMMPRRTZ #algorithm #analysis
- Tight analyses of two local load balancing algorithms (BG, FTL, BMM, SM, CGP, RR, AWR, RET, DZ), pp. 548–558.
- STOC-1995-KushilevitzOR #communication #polynomial
- Log-space polynomial end-to-end communication (EK, RO, AR), pp. 559–568.
- STOC-1995-GoldmannH
- Monotone circuits for connectivity have depth (log n)2-o(1) (MG, JH), pp. 569–574.
- STOC-1995-BonetPR #bound #proving
- Lower bounds for cutting planes proofs with small coefficients (MLB, TP, RR), pp. 575–584.
- STOC-1995-BealsNT #complexity
- More on the complexity of negation-limited circuits (RB, TN, KT), pp. 585–595.
- STOC-1995-KremerNR #communication #complexity #on the #random
- On randomized one-round communication complexity (IK, NN, DR), pp. 596–605.
- STOC-1995-CanettiI #bound #power of #random #scheduling
- Bounding the power of preemption in randomized scheduling (RC, SI), pp. 606–615.
- STOC-1995-Bar-NoyCKMS
- Bandwidth allocation with preemption (ABN, RC, SK, YM, BS), pp. 616–625.
- STOC-1995-FiatK #locality #multi #random
- Randomized and multipointer paging with locality of reference (AF, ARK), pp. 626–634.
- STOC-1995-Feige #graph #random
- Randomized graph products, chromatic numbers, and Lovasz theta-function (UF), pp. 635–640.
- STOC-1995-BorchersD #graph
- The k-Steiner ratio in graphs (AB, DZD), pp. 641–649.
- STOC-1995-RaschleS #graph #recognition
- Recognition of graphs with threshold dimension two (TR, KS), pp. 650–661.
- STOC-1995-Eppstein #bound #geometry #optimisation #parametricity
- Geometric lower bounds for parametric matroid optimization (DE), pp. 662–671.
- STOC-1995-AmatoGR
- Computing faces in segment and simplex arrangements (NMA, MTG, EAR), pp. 672–682.
- STOC-1995-MillerTTW #generative
- A Delaunay based numerical method for three dimensions: generation, formulation, and partition (GLM, DT, SHT, NW), pp. 683–692.
- STOC-1995-FerraginaG #data type #string
- A fully-dynamic data structure for external substring search (PF, RG), pp. 693–702.
- STOC-1995-FarachT #string
- String matching in Lempel-Ziv compressed strings (MF, MT), pp. 703–712.
- STOC-1995-CzumajGGPP #algorithm #parallel #problem #string
- Work-time-optimal parallel algorithms for string problems (AC, ZG, LG, KP, WP), pp. 713–722.
- STOC-1995-NisanW #complexity #memory management #on the
- On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern (NN, AW), pp. 723–732.
- STOC-1995-Chazelle #bound
- Lower bounds for off-line range searching (BC), pp. 733–740.
- STOC-1995-Pan #algorithm #approximate #parallel #polynomial
- Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros (VYP), pp. 741–750.
- STOC-1995-Reif #parallel #performance #polynomial
- Work efficient parallel solution of Toeplitz systems and polynomial GCD (JHR), pp. 751–761.

11 ×#problem

10 ×#bound

9 ×#random

8 ×#approximate

7 ×#algorithm

7 ×#polynomial

6 ×#complexity

6 ×#network

5 ×#graph

5 ×#on the

10 ×#bound

9 ×#random

8 ×#approximate

7 ×#algorithm

7 ×#polynomial

6 ×#complexity

6 ×#network

5 ×#graph

5 ×#on the