  The online bisection problem is a natural dynamic variant of the classic
optimization problem, where one has to dynamically maintain a partition of $n$
elements into two clusters of cardinality $n/2$. During runtime, an online
algorithm is given a sequence of requests, each being a pair of elements: an
inter-cluster request costs one unit while an intra-cluster one is free. The
algorithm may change the partition, paying a unit cost for each element that
changes its cluster.
  This natural problem admits a simple deterministic $O(n^2)$-competitive
algorithm [Avin et al., DISC 2016]. While several significant improvements over
this result have been obtained since the original work, all of them either
limit the generality of the input or assume some form of resource augmentation
(e.g., larger clusters). Moreover, the algorithm of Avin et al. achieves the
best known competitive ratio even if randomization is allowed.
  In this paper, we present the first randomized online algorithm that breaks
this natural quadratic barrier and achieves a competitive ratio of
$\tilde{O}(n^{23/12})$ without resource augmentation and for an arbitrary
sequence of requests.
