  Let $A(n, d)$ denote the maximum size of a binary code of length $n$ and
minimum Hamming distance $d$. Studying $A(n, d)$, including efforts to
determine it as well to derive bounds on $A(n, d)$ for large $n$'s, is one of
the most fundamental subjects in coding theory. In this paper, we explore new
lower and upper bounds on $A(n, d)$ in the large-minimum distance regime, in
particular, when $d = n/2 - \Omega(\sqrt{n})$. We first provide a new
construction of cyclic codes, by carefully selecting specific roots in the
binary extension field for the check polynomial, with length $n= 2^m -1$,
distance $d \geq n/2 - 2^{c-1}\sqrt{n}$, and size $n^{c+1/2}$, for any $m\geq
4$ and any integer $c$ with $0 \leq c \leq m/2 - 1$. These code parameters are
slightly worse than those of the Delsarte--Goethals (DG) codes that provide the
previously known best lower bound in the large-minimum distance regime.
However, using a similar and extended code construction technique we show a
sequence of cyclic codes that improve upon DG codes and provide the best lower
bound in a narrower range of the minimum distance $d$, in particular, when $d =
n/2 - \Omega(n^{2/3})$. Furthermore, by leveraging a Fourier-analytic view of
Delsarte's linear program, upper bounds on $A(n, n/2 - \rho\sqrt{n})$ with
$\rho\in (0.5, 9.5)$ are obtained that scale polynomially in $n$. To the best
of authors' knowledge, the upper bound due to Barg and Nogin
\cite{barg2006spectral} is the only previously known upper bound that scale
polynomially in $n$ in this regime. We numerically demonstrate that our upper
bound improves upon the Barg-Nogin upper bound in the specified high-minimum
distance regime.
