## Robert Sedgewick

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

STOC, 1985.

@proceedings{STOC-1985, address = "Providence, Rhode Island, USA", editor = "Robert Sedgewick", publisher = "{ACM}", title = "{Proceedings of the 17th Annual ACM Symposium on Theory of Computing}", year = 1985, }

### Contents (53 items)

- STOC-1985-Luby #algorithm #independence #parallel #problem #set
- A Simple Parallel Algorithm for the Maximal Independent Set Problem (ML), pp. 1–10.
- STOC-1985-VaziraniV #problem #scheduling
- The Two-Processor Scheduling Problem is in R-NC (UVV, VVV), pp. 11–21.
- STOC-1985-KarpUW #random
- Constructing a Perfect Matching is in Random NC (RMK, EU, AW), pp. 22–32.
- STOC-1985-Anderson #algorithm #parallel #problem
- A Parallel Algorithm for the Maximal Path Problem (RA), pp. 33–37.
- STOC-1985-FichT #complexity #finite #parallel
- The Parallel Complexity of Exponentiating Polynomials over Finite Fields (FEF, MT), pp. 38–47.
- STOC-1985-FichHRW #bound #infinity #parallel
- One, Two, Three … Infinity: Lower Bounds for Parallel Computation (FEF, FMadH, PR, AW), pp. 48–58.
- STOC-1985-Aggarwal #modelling #trade-off
- Tradeoffs for VLSI Models with Subpolynomial Delay (AA), pp. 59–68.
- STOC-1985-LeisersonM #algorithm #testing
- Algorithms for Routing and Testing Routability of Planar VLSI Layouts (CEL, FMM), pp. 69–78.
- STOC-1985-RaghavanT #array #graph
- Provably Good Routing in Graphs: Regular Arrays (PR, CDT), pp. 79–87.
- STOC-1985-JimboM
- Expanders Obtained from Affine Transformations (SJ, AM), pp. 88–97.
- STOC-1985-Alon #sorting
- Expanders, Sorting in Rounds and Superconcentrators of Limited Depth (NA), pp. 98–102.
- STOC-1985-Wilber
- White Pebbles Help (REW), pp. 103–112.
- STOC-1985-BakerFG
- Stable Prehension with Three Fingers (BSB, SF, EG), pp. 114–120.
- STOC-1985-Huang #finite
- Riemann Hypothesis and Finding Roots over Finite Fields (MDAH), pp. 121–130.
- STOC-1985-Kaltofen #source code
- Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors (EK), pp. 131–142.
- STOC-1985-PanR #linear #parallel #performance
- Efficient Parallel Solution of Linear Systems (VYP, JHR), pp. 143–152.
- STOC-1985-FriedlR #algebra #polynomial #problem
- Polynomial Time Solutions of Some Problems in Computational Algebra (KF, LR), pp. 153–162.
- STOC-1985-YaoY #approach #geometry #query
- A General Approach to d-Dimensional Geometric Queries (ACCY, FFY), pp. 163–168.
- STOC-1985-Vaidya #orthogonal #query #trade-off
- Space-Time Tradeoffs for Orthogonal Range Queries (PMV), pp. 169–174.
- STOC-1985-Clarkson #algorithm #probability #problem
- A Probabilistic Algorithm for the Post Office Problem (KLC), pp. 175–184.
- STOC-1985-Harel #algorithm #graph #linear #problem
- A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems (DH), pp. 185–194.
- STOC-1985-SuzukiNS #graph #multi
- Multicommodity Flows in Planar Undirected Graphs and Shortest Paths (HS, TN, NS), pp. 195–204.
- STOC-1985-Culberson
- The Effect of Updates in Binary Search Trees (JCC), pp. 205–212.
- STOC-1985-BentJ
- Finding the Median Requires 2n Comparisons (SWB, JWJ), pp. 213–216.
- STOC-1985-ChungHS #self
- Self-Organizing Sequential Search and Hilbert’s Inequalities (FRKC, DJH, PDS), pp. 217–223.
- STOC-1985-BollobasS #algorithm #behaviour #on the #set
- On the Expected Behaviour of Disjoint Set Union Algorithms (BB, IS), pp. 224–231.
- STOC-1985-Peleg #concurrent #logic
- Concurrent Dynamic Logic (DP), pp. 232–239.
- STOC-1985-VardiS #bound #logic #source code
- Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report (MYV, LJS), pp. 240–251.
- STOC-1985-BakkerMOZ #concurrent #semantics
- Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency (JWdB, JJCM, ERO, JIZ), pp. 252–262.
- STOC-1985-BruceL #equation #modelling #morphism
- Provable Isomorphisms and Domain Equations in Models of Typed Languages (KBB, GL), pp. 263–272.
- STOC-1985-CosmadakisK #constraints #database #equation
- Equational Theories and Database Constraints (SSC, PCK), pp. 273–284.
- STOC-1985-Buss #bound #polynomial
- The Polynomial Hierarchy and Fragments of Bounded Arithmetic (SRB), pp. 285–290.
- STOC-1985-GoldwasserMR #complexity #interactive
- The Knowledge Complexity of Interactive Proof-Systems (SG, SM, CR), pp. 291–304.
- STOC-1985-FaginV #logic #semantics
- An Internal Semantics for Modal Logic: Preliminary Report (RF, MYV), pp. 305–315.
- STOC-1985-Bracha #protocol #random
- An O(lg n) Expected Rounds Randomized Byzantine Generals Protocol (GB), pp. 316–326.
- STOC-1985-Feldman #fault tolerance #network
- Fault Tolerance of Minimal Path Routings in a Network (PF), pp. 327–334.
- STOC-1985-CoanDDS #distributed #problem
- The Distributed Firing Squad Problem (BAC, DD, CD, LJS), pp. 335–345.
- STOC-1985-HalpernMM #nondeterminism #precise
- Optimal Precision in the Presence of Uncertainty (JYH, NM, AAM), pp. 346–355.
- STOC-1985-HastadS #encryption #security
- The Cryptographic Security of Truncated Linearly Related Variables (JH, AS), pp. 356–362.
- STOC-1985-Levin #generative #pseudo
- One-Way Functions and Pseudorandom Generators (LAL), pp. 363–365.
- STOC-1985-Vazirani #communication #complexity #generative #sequence #towards
- Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (UVV), pp. 366–378.
- STOC-1985-GoodmanGMM #on the
- On the Stability of the Ethernet (JG, AGG, NM, PM), pp. 379–387.
- STOC-1985-GacsR #3d #array #realtime #reliability
- A Simple Three-Dimensional Real-Time Reliable Cellular Array (PG, JHR), pp. 388–395.
- STOC-1985-Lubiw #matrix #order
- Doubly Lexical Orderings of Matrices (AL), pp. 396–404.
- STOC-1985-Huynh #commutative #complexity #equivalence #problem #symmetry
- The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems (DTH), pp. 405–412.
- STOC-1985-Heide #algorithm #performance #problem #strict
- Fast Algorithms for N-Dimensional Restrictions of Hard Problems (FMadH), pp. 413–420.
- STOC-1985-Babai
- Trading Group Theory for Randomness (LB), pp. 421–429.
- STOC-1985-BollobasFF #algorithm #graph #random
- An Algorithm for Finding Hamilton Cycles in a Random Graph (BB, TIF, AMF), pp. 430–439.
- STOC-1985-GoldbergS #ranking
- Compression and Ranking (AVG, MS), pp. 440–448.
- STOC-1985-CarterSW #backtracking #complexity
- The Complexity of Backtrack Searches (LC, LJS, MNW), pp. 449–457.
- STOC-1985-ValiantV #detection
- NP Is as Easy as Detecting Unique Solutions (LGV, VVV), pp. 458–463.
- STOC-1985-KarpUW85a #problem #question
- Are Search and Decision Problems Computationally Equivalent? (RMK, EU, AW), pp. 464–475.
- STOC-1985-AharoniEL #integer #linear #source code
- Dual Integer Linear Programs and the Relationship between their Optima (RA, PE, NL), pp. 476–483.

10 ×#problem

8 ×#algorithm

5 ×#complexity

5 ×#parallel

4 ×#graph

3 ×#bound

3 ×#linear

3 ×#logic

3 ×#random

3 ×#source code

8 ×#algorithm

5 ×#complexity

5 ×#parallel

4 ×#graph

3 ×#bound

3 ×#linear

3 ×#logic

3 ×#random

3 ×#source code