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)

10 ×#problem
8 ×#algorithm
5 ×#complexity
5 ×#parallel
4 ×#graph
3 ×#bound
3 ×#linear
3 ×#logic
3 ×#random
3 ×#source code

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.