William C. Rounds, Nancy Martin, Jack W. Carlyle, Michael A. Harrison
Proceedings of the Seventh Annual ACM Symposium on Theory of Computing
STOC, 1975.

@proceedings{STOC-1975,
	address       = "Albuquerque, New Mexico, USA",
	editor        = "William C. Rounds and Nancy Martin and Jack W. Carlyle and Michael A. Harrison",
	publisher     = "{ACM}",
	title         = "{Proceedings of the Seventh Annual ACM Symposium on Theory of Computing}",
	year          = 1975,
}

Contents (31 items)

10 ×#complexity
8 ×#on the
4 ×#bound
4 ×#problem
3 ×#combinator
3 ×#polynomial
3 ×#proving
2 ×#algorithm
2 ×#data type
2 ×#evaluation

STOC-1975-LiptonD #complexity #evaluation #integer #metric

Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms (RJL, DPD), pp. 1–5.

STOC-1975-RivestV #proving

A Generalization and Proof of the Aanderaa-Rosenberg Conjecture (RLR, JV), pp. 6–11.

STOC-1975-HyafilK #complexity #evaluation #linear #parallel

The Complexity of Parallel Evaluation of Linear Recurrence (LH, HTK), pp. 12–22.

STOC-1975-Yao #on the #polynomial

On Computing the Minima of Quadratic Forms (ACCY), pp. 23–26.

STOC-1975-Paul #bound #combinator #complexity

A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions (WJP), pp. 27–36.

STOC-1975-FischerMP #bound

Lower Bounds on the Size of Boolean Formulas: Preliminary Report (MJF, ARM, MP), pp. 37–44.

STOC-1975-Valiant #bound #complexity #on the

On Non-linear Lower Bounds in Computational Complexity (LGV), pp. 45–53.

STOC-1975-HuntS #complexity #on the #problem

On the Complexity of Grammar and Related Problems (HBHI, TGS), pp. 54–65.

STOC-1975-EvenT #combinator #polynomial #problem

a Combinatorial Problem which is Complete in Polynomial Space (SE, RET), pp. 66–71.

STOC-1975-Galil #bound #complexity #on the

On the Validity and Complexity of Bounded Resolution (ZG), pp. 72–82.

STOC-1975-Cook #calculus #proving

Feasibly Constructive Proofs and the Propositional Calculus (SAC), pp. 83–97.

STOC-1975-EgliC #concept #programming language #semantics

Computability Concepts for Programming Language Semantics (HE, RLC), pp. 98–106.

STOC-1975-OppenC #data type #proving #source code

Proving Assertions about Programs that Manipulate Data Structures (DCO, SAC), pp. 107–116.

STOC-1975-EhrenfeuchtR #formal method #on the #predict

On (Un)predictability of Formal Languages (AE, GR), pp. 117–120.

STOC-1975-Skyum #on the #parallel

On Decomposing Languages Defined by Parallel Devices (SS), pp. 121–125.

STOC-1975-Perrault #theorem #transducer

Intercalation Theorems for Tree Transducer Languages (CRP), pp. 126–136.

STOC-1975-EhrenfeuchtR75a #combinator #interactive #on the

On the (Combinatorial) Structure of L Languages without Interactions (AE, GR), pp. 137–144.

STOC-1975-Wotschke #polynomial #problem #recognition

Degree-Languages, Polynomial Time Recognition, and the LBA Problem (DW), pp. 145–152.

STOC-1975-GinsburgL #comparative #complexity

Comparative Complexity of Grammar Forms (SG, NAL), pp. 153–158.

STOC-1975-RosenbergS #array

Hashing Schemes for Extendible Arrays (Extended Arrays) (ALR, LJS), pp. 159–166.

STOC-1975-Pratt #analysis #modelling #optimisation

Four Models for the Analysis of Optimization of Program Control Structures (TWP), pp. 167–176.

STOC-1975-AhoU #graph

Node Listings for Reducible Flow Graphs (AVA, JDU), pp. 177–185.

STOC-1975-LiptonED #complexity #data type

The Complexity of Control Structures and Data Structures (RJL, SCE, RAD), pp. 186–193.

STOC-1975-MannaS #recursion #source code

The Optimal Fixedpoint of Recursive Programs (ZM, AS), pp. 194–206.

STOC-1975-AhoJ #code generation

Optimal Code Generation for Expression Trees (AVA, SCJ), pp. 207–217.

STOC-1975-Wagner #complexity #on the #problem #string

On the Complexity of the Extended String-to-String Correction Problem (RAW), pp. 218–223.

STOC-1975-Shamos #complexity #geometry

Geometric Complexity (MIS), pp. 224–233.

STOC-1975-Miller #testing

Riemann’s Hypothesis and Tests for Primality (GLM), pp. 234–239.

STOC-1975-Fredman #probability #sorting

Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees (MLF), pp. 240–244.

STOC-1975-RoseT #algorithm #aspect-oriented

Algorithmic Aspects of Vertex Elimination (DJR, RET), pp. 245–254.

STOC-1975-BoothL #algorithm #graph #linear

Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property (KSB, GSL), pp. 255–265.