Publication:4230323
From MaRDI portal
zbMath0915.05081MaRDI QIDQ4230323
Avi Wigderson, Endre Szemerédi, Noam Nisan
Publication date: 22 April 1999
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W10: Parallel algorithms in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
05C40: Connectivity
Related Items
An unambiguous class possessing a complete set, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Pseudorandom generators for combinatorial checkerboards, Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\))., Improved algorithms via approximations of probability distributions, Universal traversal sequences with backtracking., The complexity of planarity testing