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)

11 ×#problem
10 ×#bound
9 ×#random
8 ×#approximate
7 ×#algorithm
7 ×#polynomial
6 ×#complexity
6 ×#network
5 ×#graph
5 ×#on the

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.