  The {\em binary deletion channel} with deletion probability $d$
($\text{BDC}_d$) is a random channel that deletes each bit of the input message
i.i.d with probability $d$. It has been studied extensively as a canonical
example of a channel with synchronization errors.
  Perhaps the most important question regarding the BDC is determining its
capacity. Mitzenmacher and Drinea (ITIT 2006) and Kirsch and Drinea (ITIT 2009)
show a method by which distributions on run lengths can be converted to codes
for the BDC, yielding a lower bound of $\mathcal{C}(\text{BDC}_d) > 0.1185
\cdot (1-d)$. Fertonani and Duman (ITIT 2010), Dalai (ISIT 2011) and Rahmati
and Duman (ITIT 2014) use computer aided analyses based on the Blahut-Arimoto
algorithm to prove an upper bound of $\mathcal{C}(\text{BDC}_d) <
0.4143\cdot(1-d)$ in the high deletion probability regime ($d > 0.65$).
  In this paper, we show that the Blahut-Arimoto algorithm can be implemented
with a lower space complexity, allowing us to extend the upper bound analyses,
and prove an upper bound of $\mathcal{C}(\text{BDC}_d) < 0.3745 \cdot(1-d)$ for
all $d \geq 0.68$. Furthermore, we show that an extension of the Blahut-Arimoto
algorithm can also be used to select better run length distributions for
Mitzenmacher and Drinea's construction, yielding a lower bound of
$\mathcal{C}(\text{BDC}_d) > 0.1221 \cdot (1 - d)$.
