Frank Thomson Leighton, Michael T. Goodrich
Proceedings of the 26th Annual ACM Symposium on Theory of Computing
STOC, 1994.

@proceedings{STOC-1994,
	address       = "Québec, Canada",
	editor        = "Frank Thomson Leighton and Michael T. Goodrich",
	isbn          = "0-89791-663-8",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 26th Annual ACM Symposium on Theory of Computing}",
	year          = 1994,
}

Contents (81 items)

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

STOC-1994-ChungY #algorithm

A near optimal algorithm for edge separators (FRKC, STY), pp. 1–8.

STOC-1994-KleinT #algorithm #linear #random

A randomized linear-time algorithm for finding minimum spanning trees (PNK, RET), pp. 9–15.

STOC-1994-Cohen #approximate

Polylog-time and near-linear work approximation scheme for undirected shortest paths (EC), pp. 16–26.

STOC-1994-KleinRRS #algorithm #graph #performance

Faster shortest-path algorithms for planar graphs (PNK, SR, MRH, SS), pp. 27–37.

STOC-1994-TanakaN #complexity #network #on the

On the complexity of negation-limited Boolean networks (KT, TN), pp. 38–47.

STOC-1994-KrauseP #on the #power of

On the computational power of depth 2 circuits with threshold and modulo gates (MK, PP), pp. 48–57.

STOC-1994-JakobyRS #complexity

Circuit complexity: from the worst case to the average case (AJ, RR, CS), pp. 58–67.

STOC-1994-Grolmusz #trade-off

A weight-size trade-off for circuits with MOD m gates (VG), pp. 68–74.

STOC-1994-Chazelle #geometry

Computational geometry: a retrospective (BC), pp. 75–94.

STOC-1994-Pellegrini #on the

On point location and motion planning among simplices (MP), pp. 95–104.

STOC-1994-BergDS #incremental #lazy evaluation #on the #random

On lazy randomized incremental construction (MdB, KD, OS), pp. 105–114.

STOC-1994-KalyanasundaramP #fault tolerance #scheduling

Fault-tolerant scheduling (BK, KP), pp. 115–124.

STOC-1994-KarlinNT #fault tolerance #on the

On the fault tolerance of the butterfly (ARK, GN, HT), pp. 125–133.

STOC-1994-RaghavanU #network #performance

Efficient routing in all-optical networks (PR, EU), pp. 134–143.

STOC-1994-BrewerCL #random #scalability

Scalable expanders: exploiting hierarchical random wiring (EAB, FTC, TL), pp. 144–152.

STOC-1994-MacKenziePR #on the #probability #protocol

On contention resolution protocols and associated probabilistic phenomena (PDM, CGP, RR), pp. 153–162.

STOC-1994-BlumCCPRS #latency #problem

The minimum latency problem (AB, PC, DC, WRP, PR, MS), pp. 163–171.

STOC-1994-FeigeK #fault #protocol #proving

Two prover protocols: low error at affordable rates (UF, JK), pp. 172–183.

STOC-1994-BellareS

Improved non-approximability results (MB, MS), pp. 184–193.

STOC-1994-PolishchukS #artificial reality #proving

Nearly-linear size holographic proofs (AP, DAS), pp. 194–203.

STOC-1994-RazborovR #proving

Natural proofs (AAR, SR), pp. 204–213.

STOC-1994-AwerbuchCS #distributed #performance #symmetry

Efficient asynchronous distributed symmetry breaking (BA, LC, MAS), pp. 214–223.

STOC-1994-YangA #bound #problem

Time bounds for mutual exclusion and related problems (JHY, JHA), pp. 224–233.

STOC-1994-OstrovskyRV #performance

Simple and efficient leader election in the full information model (RO, SR, UVV), pp. 234–242.

STOC-1994-HerlihyS #theorem

A simple constructive computability theorem for wait-free computation (MH, NS), pp. 243–252.

STOC-1994-BlumFJKMR #analysis #fourier #learning #query #statistics #using

Weakly learning DNF and characterizing statistical query learning using Fourier analysis (AB, MLF, JCJ, MJK, YM, SR), pp. 253–262.

STOC-1994-AuerL #learning #simulation

Simulating access to hidden information while learning (PA, PML), pp. 263–272.

STOC-1994-KearnsMRRSS #on the

On the learnability of discrete distributions (MJK, YM, DR, RR, RES, LS), pp. 273–282.

STOC-1994-ApsitisFS #approach #learning

Choosing a learning team: a topological approach (KA, RF, CHS), pp. 283–289.

STOC-1994-Hariharan #parallel

Optimal parallel suffix tree construction (RH), pp. 290–299.

STOC-1994-SahinalpV #symmetry

Symmetry breaking for suffix tree construction (SCS, UV), pp. 300–309.

STOC-1994-Kosaraju #pattern matching #realtime

Real-time pattern matching and quasi-real-time construction of suffix trees (SRK), pp. 310–316.

STOC-1994-AnderssonHHP #array #complexity #string

The complexity of searching a sorted array of strings (AA, TH, JH, OP), pp. 317–325.

STOC-1994-AlonYZ #graph #named #scalability

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (NA, RY, UZ), pp. 326–335.

STOC-1994-Odlyzko #random

Search for the maximum of a random walk (AMO), pp. 336–345.

STOC-1994-AlonK #graph #random

A spectral technique for coloring random 3-colorable graphs (NA, NK), pp. 346–355.

STOC-1994-ImpagliazzoNW #algorithm #network #pseudo

Pseudorandomness for network algorithms (RI, NN, AW), pp. 356–364.

STOC-1994-Kurshan #complexity #verification

The complexity of verification (RPK), pp. 365–371.

STOC-1994-MansourNV #communication #parallel #throughput #trade-off

Trade-offs between communication throughput and parallel time (YM, NN, UV), pp. 372–381.

STOC-1994-Hagerup #algorithm #parallel #sorting #string

Optimal parallel string algorithms: sorting, merging and computing the minimum (TH), pp. 382–391.

STOC-1994-MaG #complexity #permutation

The computational complexity of recognizing permutation functions (KM, JvzG), pp. 392–401.

STOC-1994-KhullerRY

Low degree spanning trees of small weight (SK, BR, NEY), pp. 412–421.

STOC-1994-GoemansW #algorithm #approximate #satisfiability

.879-approximation algorithms for MAX CUT and MAX 2SAT (MXG, DPW), pp. 422–431.

STOC-1994-GargH #algorithm #approximate #problem

An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane (NG, DSH), pp. 432–438.

STOC-1994-HalldorssonR #approximate #bound #graph #independence #set

Greed is good: approximating independent sets in sparse and bounded-degree graphs (MMH, JR), pp. 439–448.

STOC-1994-BodlaenderFH #bound #problem

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (HLB, MRF, MTH), pp. 449–458.

STOC-1994-AroraRV #polynomial #simulation

Simulating quadratic dynamical systems is PSPACE-complete (SA, YR, UVV), pp. 459–467.

STOC-1994-MaratheHSR #approximate #problem #specification

Approximation schemes for PSPACE-complete problems for succinct specifications (MVM, HBHI, RES, VR), pp. 468–477.

STOC-1994-Sitharam #algorithm #generative #learning #pseudo

Pseudorandom generators and learning algorithms for AC (MS), pp. 478–486.

STOC-1994-AwerbuchL #algorithm #approximate #multi #network #problem

Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks (BA, TL), pp. 487–496.

STOC-1994-VavasisY

An accelerated interior point method whose running time depends only on A (SAV, YY), pp. 512–521.

STOC-1994-SantisDFY #how

How to share a function securely (ADS, YD, YF, MY), pp. 522–533.

STOC-1994-GoldreichOP #complexity

Computational complexity and knowledge complexity (OG, RO, EP), pp. 534–543.

STOC-1994-BenalohT

Receipt-free secret-ballot elections (JCB, DT), pp. 544–553.

STOC-1994-FeigeKN

A minimal model for secure computation (UF, JK, MN), pp. 554–563.

STOC-1994-GoldreichW #product line #random #trade-off

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing (OG, AW), pp. 574–584.

STOC-1994-ChariRS #algorithm #approximate #probability

Improved algorithms via approximations of probability distributions (SC, PR, AS), pp. 584–592.

STOC-1994-AzarBKU

Balanced allocations (YA, AZB, ARK, EU), pp. 593–602.

STOC-1994-Mulmuley #bound #linear #parallel #problem #programming

Lower bounds for parallel linear programming and other problems (KM), pp. 603–614.

STOC-1994-Yao #complexity

Decision tree complexity and Betti numbers (ACCY), pp. 615–624.

STOC-1994-Miltersen #bound #problem #random

Lower bounds for union-split-find related problems on random access machines (PBM), pp. 625–634.

STOC-1994-GrigorievKV #algebra #bound #testing

Lower bounds on testing membership to a polyhedron by algebraic decision trees (DG, MK, NV), pp. 635–644.

STOC-1994-Wigderson #independence #power of

The amazing power of pairwise independence (AW), pp. 645–647.

STOC-1994-Karger #design #network #problem #random

Random sampling in cut, flow, and network design problems (DRK), pp. 648–657.

STOC-1994-JiangSV

Two heads are better than two tapes (TJ, JIS, PMBV), pp. 668–675.

STOC-1994-CondonHPW #automaton #finite #nondeterminism #on the #power of #probability

On the power of finite automata with both nondeterministic and probabilistic states (AC, LH, SP, AW), pp. 676–685.

STOC-1994-Rauch #data type

Improved data structures for fully dynamic biconnectivity (MR), pp. 686–695.

STOC-1994-Gabow #algorithm #graph #performance

Efficient splitting off algorithms for graphs (HNG), pp. 696–705.

STOC-1994-Poutre #incremental #testing

Alpha-algorithms for incremental planarity testing (JALP), pp. 706–715.

STOC-1994-DinitzV #graph #incremental #maintenance #set

The connectivity carcass of a vertex subset in a graph and its incremental maintenance (YD, AV), pp. 716–725.

STOC-1994-PapadimitriouY #bound #complexity #on the

On complexity as bounded rationality (CHP, MY), pp. 726–733.

STOC-1994-LiptonY #complexity #game studies #scalability

Simple strategies for large zero-sum games with applications to complexity theory (RJL, NEY), pp. 734–740.

STOC-1994-FortnowW #bound #game studies

Optimality and domination in repeated games with bounded players (LF, DW), pp. 741–749.

STOC-1994-KollerMS #algorithm #game studies #performance #random

Fast algorithms for finding randomized strategies in game trees (DK, NM, BvS), pp. 750–759.

STOC-1994-JiangLW #approximate #complexity #sequence

Aligning sequences via an evolutionary tree: complexity and approximation (TJ, ELL, LW), pp. 760–769.

STOC-1994-MuthukrishnanP #algorithm #complexity #standard #string

Non-standard stringology: algorithms and complexity (SM, KVP), pp. 770–779.

STOC-1994-JacquetS #algorithm #analysis #equation #functional

A functional equation often arising in the analysis of algorithms (PJ, WS), pp. 780–789.

STOC-1994-RajagopalanS #distributed #theorem

A coding theorem for distributed computation (SR, LJS), pp. 790–799.

STOC-1994-AlurAT #adaptation #algorithm

Time-adaptive algorithms for synchronization (RA, HA, GT), pp. 800–809.

STOC-1994-Patt-ShamirR #formal method

A theory of clock synchronization (BPS, SR), pp. 810–819.

STOC-1994-BellareGLR #approximate #performance #probability #proving

Efficient probabilistic checkable proofs and applications to approximation (MB, SG, CL, AR), p. 820.