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

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

15 ×#algorithm

11 ×#complexity

9 ×#approximate

9 ×#on the

9 ×#problem

9 ×#random

8 ×#bound

7 ×#performance

6 ×#graph

5 ×#network

11 ×#complexity

9 ×#approximate

9 ×#on the

9 ×#problem

9 ×#random

8 ×#bound

7 ×#performance

6 ×#graph

5 ×#network