Conference paper
Closure of monadic NP
Miklos Ajtai, Ronald Fagin, et al.
STOC 1998
We present an algorithm which in n3 (log n)3 time constructs a 3-regular expander graph on n vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of length s=⌊clog n⌋ decreases (for some fixed absolute constant c). When we reach a local minimum in the number of cycles of length s the graph is an expander. © 1994 Akadémiai Kiadó.
Miklos Ajtai, Ronald Fagin, et al.
STOC 1998
Miklos Ajtai, Yuri Gurevich
FOCS 1989
Miklos Ajtai
STOC 1994
Miklos Ajtai, N. Alon, et al.
FOCS 1992