NONDETERMINISTIC VERSUS PROBABILISTIC LINEAR SEARCH ALGORITHMS.Friedhelm Meyer auf der Heide1984FOCS 1984
SOLVING SOME GRAPH PROBLEMS WITH OPTIMAL OR NEAR-OPTIMAL SPEEDUP ON MESH-OF-TREES NETWORKS.Ming-Deh A. Huang1984FOCS 1984
DETERMINISTIC SIMULATION OF PROBABILISTIC CONSTANT DEPTH CIRCUITS.Miklos AjtaiAvi Wigderson1984FOCS 1984
A model-theoretic analysis of knowledge: Preliminary reportRonald FaginJoseph Y. Halpernet al.1984FOCS 1984
Flipping coins in many pockets (byzantine agreement on uniformly random values)Andrei Z. BroderDanny Dolev1984FOCS 1984