%0 Conference Paper %B Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM '05) %D 2005 %T Derandomized squaring of graphs %A Eyal Rozenman %A Salil Vadhan %X

We introduce a “derandomized” analogue of graph squaring. This operation increases the connectivity of the graph (as measured by the second eigenvalue) almost as well as squaring the graph does, yet only increases the degree of the graph by a constant factor, instead of squaring the degree.

One application of this product is an alternative proof of Reingold’s recent breakthrough result that S-T Connectivity in Undirected Graphs can be solved in deterministic logspace.

%B Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM '05) %I Springer Verlag, Lecture Notes in Computer Science %C Berkeley, CA %V 3624 %P 436-447 %G eng %U https://link.springer.com/chapter/10.1007/11538462_37