  In this paper we give new bounds on the bisection width of random 3-regular
graphs on $n$ vertices. The main contribution is a new lower bound of
$0.103295n$ based on a first moment method together with a structural analysis
of the graph, thereby improving a 27-year-old result of Kostochka and Melnikov.
We also give a complementary upper bound of $0.139822n$ by combining a result
of Lyons with original combinatorial insights. Developping this approach
further, we obtain a non-rigorous improved upper bound with the help of Monte
Carlo simulations.
