Richard A. DeMillo
Proceedings of the 16th Annual ACM Symposium on Theory of Computing
STOC, 1984.

@proceedings{STOC-1984,
	address       = "Washington, District of Columbia, USA",
	editor        = "Richard A. DeMillo",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 16th Annual ACM Symposium on Theory of Computing}",
	year          = 1984,
}

Contents (66 items)

8 ×#on the
8 ×#problem
7 ×#performance
6 ×#algorithm
6 ×#bound
6 ×#logic
6 ×#parallel
6 ×#polynomial
4 ×#network
4 ×#probability

STOC-1984-HartS #bound #finite #logic #modelling #probability

Probabilistic Temporal Logics for Finite and Bounded Models (SH, MS), pp. 1–13.

STOC-1984-EmersonS #branch #logic

Deciding Branching Time Logic (EAE, APS), pp. 14–24.

STOC-1984-Hennessy #modelling #process

Modelling Fair Processes (MH), pp. 25–30.

STOC-1984-DeganoM #convergence #liveness #metric

Liveness Properties as Convergence in Metric Spaces (PD, UM), pp. 31–38.

STOC-1984-Gerth #composition #how #logic

Transition Logic: How to Reason About Temporal Properties in a Compositional Way (RG), pp. 39–50.

STOC-1984-BarringerKP #logic #specification

Now You May Compose Temporal Logic Specifications (HB, RK, AP), pp. 51–63.

STOC-1984-BilardiP #network #sorting

A Minimum Area VLSI Network for O(log n) Time Sorting (GB, FPP), pp. 64–70.

STOC-1984-Leighton #bound #complexity #parallel #sorting

Tight Bounds on the Complexity of Parallel Sorting (FTL), pp. 71–80.

STOC-1984-DurisGS #bound #communication #complexity

Lower Bounds on Communication Complexity (PD, ZG, GS), pp. 81–91.

STOC-1984-Blum #layout #trade-off

An Area-Maximum Edge Length Tradeoff for VLSI Layout (NB), pp. 92–97.

STOC-1984-BussS #graph #on the

On the Pagenumber of Planar Graphs (JFB, PWS), pp. 98–100.

STOC-1984-Mirzaian

Channel Routing in VLSI (AM), pp. 101–107.

STOC-1984-Post

Minimum Spanning Ellipsoids (MJP), pp. 108–116.

STOC-1984-KimA

Digital Disks and a Digital Compactness Measure (CEK, TAA), pp. 117–124.

STOC-1984-Chazelle #sorting

Intersecting Is Easier than Sorting (BC), pp. 125–134.

STOC-1984-GabowBT #geometry #problem #scalability

Scaling and Related Techniques for Geometry Problems (HNG, JLB, RET), pp. 135–143.

STOC-1984-SharirS #on the

On Shortest Paths in Polyhedral Spaces (MS, AS), pp. 144–153.

STOC-1984-ColeSY #on the #problem

On k-hulls and Related Problems (RC, MS, CKY), pp. 154–166.

STOC-1984-FranzblauK #algorithm #generative #independence #set

An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals (DSF, DJK), pp. 167–174.

STOC-1984-Huang #algebra #finite

Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields (MDAH), pp. 175–182.

STOC-1984-BachMS

Sums of Divisors, Perfect Numbers, and Factoring (EB, GLM, JS), pp. 183–190.

STOC-1984-KannanLL #algebra #polynomial

Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers (RK, AKL, LL), pp. 191–200.

STOC-1984-Coppersmith

Evaluating Logarithms in GF(2^n) (DC), pp. 201–207.

STOC-1984-OngSS #equation #performance #polynomial

An Efficient Signature Scheme Based on Quadratic Equations (HO, CPS, AS), pp. 208–216.

STOC-1984-OrlitskyE #communication #constraints

Communication with Secrecy Constraints (AO, AEG), pp. 217–224.

STOC-1984-DolevMMU #fault #memory management

Correcting Faults in Write-Once Memory (DD, DM, HGM, JDU), pp. 225–229.

STOC-1984-Vishkin #parallel #random

Randomized Speed-Ups in Parallel Computation (UV), pp. 230–239.

STOC-1984-Galil #algorithm #parallel #string

Optimal Parallel Algorithms for String Matching (ZG), pp. 240–248.

STOC-1984-AwerbuchIS #parallel

Finding Euler Circuits in Logarithmic Parallel Time (BA, AI, YS), pp. 249–257.

STOC-1984-Upfal #modelling #parallel #probability

A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version) (EU), pp. 258–265.

STOC-1984-KarpW #algorithm #independence #parallel #performance #problem #set

A Fast Parallel Algorithm for the Maximal Independent Set Problem (RMK, AW), pp. 266–272.

STOC-1984-Manber #concurrent #information management #maintenance #on the

On Maintaining Dynamic Information in a Concurrent Environment (UM), pp. 273–278.

STOC-1984-BentleyJLMM #behaviour

Some Unexpected Expected Behavior Results for Bin Packing (JLB, DSJ, FTL, CCM, LAM), pp. 279–288.

STOC-1984-KarpLM #analysis #multi #probability #problem

A Probabilistic Analysis of Multidimensional Bin Packing Problems (RMK, ML, AMS), pp. 289–298.

STOC-1984-KahnS #comparison

Every Poset Has a Good Comparison (JK, MES), pp. 299–301.

STOC-1984-Karmarkar #algorithm #linear #polynomial #programming

A New Polynomial-Time Algorithm for Linear Programming (NK), pp. 302–311.

STOC-1984-AdlerM #algorithm #bound #polynomial

A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension (IA, NM), pp. 312–323.

STOC-1984-HochbaumS #approximate #graph #problem

Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems (DSH, DBS), pp. 324–333.

STOC-1984-Gonnet #equivalence #polynomial #random

Determining Equivalence of Expressions in Random Polynomial Time (GHG), pp. 334–341.

STOC-1984-Clarkson #algorithm #approximate #geometry #performance

Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees (KLC), pp. 342–348.

STOC-1984-BlumerBEHM #linear #set

Building a Complete Inverted File for a Set of Text Files in Linear Time (AB, JB, AE, DH, RMM), pp. 349–358.

STOC-1984-GoldbergM #on the #problem

On Finding the Exact Solution of a Zero-One Knapsack Problem (AVG, AMS), pp. 359–368.

STOC-1984-CuntoM

Average Case Selection (WC, JIM), pp. 369–375.

STOC-1984-Miller #graph

Finding Small Simple Cycle Separators for 2-Connected Planar Graphs (GLM), pp. 376–382.

STOC-1984-FredericksonS #data type #online

Data Structures for On-Line Updating of Matroid Intersection Solutions (GNF, MAS), pp. 383–390.

STOC-1984-SlotB #on the #performance

On Tape Versus Core; An Application of Space Efficient Perfect Hash Functions to the Invariance of Space (CFS, PvEB), pp. 391–400.

STOC-1984-Maass #bound #nondeterminism #polynomial #turing machine

Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (WM), pp. 401–408.

STOC-1984-Rougemont #finite

Uniform Definability on Finite Structures with Successor (MdR), pp. 409–417.

STOC-1984-Harel #infinity

A General Result on Infinite Trees and Its Applications (DH), pp. 418–427.

STOC-1984-Kozen #equation #logic

Pebblings, Edgings, and Equational Logic (DK), pp. 428–435.

STOC-1984-Valiant #formal method

A Theory of the Learnable (LGV), pp. 436–445.

STOC-1984-VardiW #automaton #logic #source code

Automata Theoretic Techniques for Modal Logics of Programs (MYV, PW), pp. 446–456.

STOC-1984-Ben-OrKR #algebra #complexity #geometry

The Complexity of Elementary Algebra and Geometry (MBO, DK, JHR), pp. 457–464.

STOC-1984-Levin #problem

Problems, Complete in “Average” Instance (LAL), p. 465.

STOC-1984-Alt #comparison

Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (HA), pp. 466–470.

STOC-1984-AjtaiB #constant #probability #theorem

A Theorem on Probabilistic Constant Depth Computations (MA, MBO), pp. 471–474.

STOC-1984-Boppana #bound

Threshold Functions and Bounded Depth Monotone Circuits (RBB), pp. 475–479.

STOC-1984-KlawePPY #on the #strict

On Monotone Formulae with Restricted Depth (MMK, WJP, NP, MY), pp. 480–487.

STOC-1984-SleatorT #performance

Amortized Efficiency of List Update Rules (DDS, RET), pp. 488–492.

STOC-1984-FredericksonL #communication #problem

The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring (GNF, NAL), pp. 493–503.

STOC-1984-DolevHS #on the

On the Possibility and Impossibility of Achieving Clock Synchronization (DD, JYH, HRS), pp. 504–511.

STOC-1984-Willard #protocol

Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (DEW), pp. 512–521.

STOC-1984-Awerbuch #network #performance #protocol

An Efficient Network Synchronization Protocol (BA), pp. 522–525.

STOC-1984-DolevHSS #fault tolerance #network

A New Look at Fault Tolerant Network Routing (DD, JYH, BS, HRS), pp. 526–535.

STOC-1984-BroderDFS #fault tolerance #network #performance

Efficient Fault Tolerant Routings in Networks (AZB, DD, MJF, BS), pp. 536–541.

STOC-1984-Vitanyi #distributed

Distributed Elections in an Archimedean Ring of Processors (PMBV), pp. 542–547.