1987/01/01 by Miklós Ajtai, János Komlós, Endre Szemerédi · 4 citations
Computer Science · Engineering · #Algorithms and Data Compression #semigroups and automata theory #graph theory and CDMA systems
paper · pdf · doi:10.1145/28395.28410
openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size.