When I meet someone, I give them a large two-sided card with information about topics, my blog posts, and items of interest that the person will find useful, in addition to my contact details for Sales Lab. We call it a Hot Sheet.
During our conversation, I will circle an item on the Hot Sheet if pertinent, or can write a URL or other reference in the margin for use later by the recipient.
It is easy to update or change and I can print as many as needed for upcoming meetings. Usually, each time I see a person at a meeting or event, the Hot Sheet is newly revised.
I was at a meeting of YPLG (The Young Professional's Leadership Group) this week and was talking with a person who knew me but was trying to place where we had met. When I gave him a Hot Sheet, he immediately remembered where and when we met – and he said he still uses his original Hot Sheet as a technical reference.
In addition to its unique size and content, the Hot Sheet is memorable to the recipient. How memorable is another business card for your pile? Which has the best chance to begin a relationship?
I like my own handout. And if I find something someone else wrote that I really like, I'll hand that out. Some of the lost posts of Marc Andreessen and ESR's The Cathedral and the Bazaar were two I used as handouts.


Paris Cinema: The End of the Line for La Pagode?
Home Cinema Paris Cinema: The End of the Line for La Pagode?
After many months of fractious dispute, the fate of a hallowed movie venue is still in doubt. It had seemed that La Pagode, a Japanese-themed movie palace, was going to be closed down. Though it was recently announced that the closure was only temporary, it's unclear when it will re-open and in what form.
For years, La Pagode has been one of Paris' most beloved cinema destinations. Located in the posh 7th arrondissement, near the luxury department store Le Bon Marché and the Hotel Lutetia, the theater is distinctive first for its architecture. True to its name, it is designed like a stereotypical notion of a Far Eastern pagoda with a dark red exterior and curving roof. La Pagode also has a garden where people could sit on benches amidst greenery and tall bamboo, and at one time it also had a tea room. While not really an art et essai (art house) cinema, La Pagode usually ran quality films in its plush screening rooms.
The cinema has been caught between two institutions, Rembrandt Investissement, which owns the physical site, and Europalaces Etoile, a firm that manages not only La Pagode but several other theaters in Paris. Elisabeth Dauchy, who heads Rembrandt, accused Etoile of not paying its bills. The company claimed that it intended to spend considerable sums to renovate the building housing the Pagode, which was constructed in 1896, and has indeed undergone extensive work over the years. After three years of court wrangling, a judge found in favor of the landlord. A huissier de justice (equivalent of a UK bailiff or county marshal in the US) ordered Etoile to vacate the premises.
Ms. Dauchy has said that the building will continue to be renovated over the next few years, and then be sold to a "high-culture institution". A third establishment, Pathé-Caumont, which manages numerous movie theaters, has also entered the fray. It had at one time rented the Pagode's bulding, and served as an intermediary between Rembrandt and Etoile. Pathé has expressed interest in buying the site in order to keep it going as a working theater. France's strict regulations ensure that the site can't be demolished or even have its architecture modified. The building, designed by the architect Alexandre Marcel for François-Emile Morel, owner of Le Bon Marché, is classified as a historical monument. A government office called the Architecte de France must give approval for even the smallest modification.
La Pagode has been an important part of France's cinema heritage, from the days when it screened the films of Jean Renoir through the New Wave period up to the present day. Filmmaker Louis Malle even served as director for a while, and was responsible for a degree of modernization. Parisian film buffs are feeling bereft, though hopeful that one day the theater will re-open. For now, the large and upscale 7th arrondissement is without a single movie theater.
Previous articleFestive Paris Magic at the Patisserie des Rêves: 2015 Yule Logs!


The party season is starting, and for those that are considering booking entertainment for a special event this summer, now is the time to start finding your entertainer. Many of the bookings that happen all summer start in April and May. Waiting until the last minute during this time of year means that there could be some real difficulty in finding the right person for the event. In many cases when one waits too long, there can be problems. Many times customers call saying that their entertainer has canceled with barely any notice and they are in a pickle.
Considering the quality of your entertainer, and their track record could prevent some major headaches later. Party entertainment is an important necessity to have an excellent experience with both the entertainer and the guests at the party.
If someone is booking a clown and has fifty children coming, and that entertainer cancels, the host is left with a responsibility to entertain without the chance to plan ahead, without props, and without the experience of dealing with large numbers of people.
So, the time has come for booking your entertainer for the spring and summer 2018. Click on the contact link at the top of the page or contact through any social media source.
Please call the phone number at the top of this website, or email by clicking on a link or filling in a contact form, and she will get back with you shortly (within 24 hours). Booking BEE BEE or Katy BEE is very easy, quick and she will continue to communicate with you about details for your event up until the date of your celebration. Whether she is bringing a pre-designed show or a new concept related to your theme, she will always be available to discuss the details.


text:
\section{Proof of the Convexity of $f(\gamma, \delta)$}\label{appdx:proofOfConvexity}
\pushQED{\qed}
In this section, we show that the bivariate function
$$f(\gamma, \delta) = (1-\delta)\left[
\left(1 + \frac{\gamma}{1-\delta}\right)\log_q\frac{q(1-\delta)}{\frac{\gamma}{1-\delta}+1}
-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{q(1-\delta)-1}{\frac{\gamma}{1-\delta}}\right)
\right]$$
is convex.
To prove the convexity, our general strategy is to show that the Hessian matrix of $f$ is positive semi-definite. In order to do so, we take the following steps: We first characterize a domain $D$ for $f(\gamma, \delta)$, over which we analyze the convexity. We then calculate the Hessian matrix of the function $f$, $H_f$. To show the positive semi-definiteness of $H_f$, we form its characteristic polynomial and then show that both of its solutions are real and non-negative -- meaning that both eigenvalues of $H_f$ are non-negative over the domain $D$. This would imply that $H_f$ is positive semi-definite and, hence, $f$ is convex over $D$.

\paragraph{Determining the domain $D$.}Let us begin with describing the domain $D$. As stated in \Cref{sec:prior-work}, for the purposes of this paper, we only consider the error rates that are within $\delta \in [0, 1-1/q]$ and $\gamma \in [0, q-1]$. Note that for any fixed value $\delta \in [0, 1-1/q)$, $f(\gamma=0, \delta)$ is positive. We will show that as $\gamma$ grows, the value of $f(\gamma, \delta)$ continuously drops until it reaches zero at
$\gamma = (1-\delta)(q - q\delta - 1)$. This suggests that the domain $D$ has to be defined as follows:
$$D = \left\{(\gamma, \delta)\ |\ 0\leq \delta \leq 1 - \frac{1}{q}, 0 \leq \gamma \leq (1-\delta)(q - q\delta - 1) \right\}.$$
To show the claim above, we demonstrate two simple facts: (I) The partial derivative of $f$ with respect to $\gamma$ is negative within $0 \leq \gamma \leq (1-\delta)(q - q\delta - 1)$ and, (II) $f(\gamma, \delta) = 0$ for $\gamma = (1-\delta)(q - q\delta - 1)$.

To see claim (a), note that
$$\frac{\partial f}{\partial \gamma} = \log_q \left(\frac{(1-\delta)^2 q}{1 -\delta +\gamma}\right)-\log_q \left(\frac{(1-\delta) (q - q\delta -1)}{\gamma }\right)
=
\log _q \left(\frac{q(1-\delta)\gamma}{(1 - \delta + \gamma)(q - q\delta - 1)}\right)
$$
which is non-positive as long as
\begin{eqnarray}
\frac{\partial f}{\partial \gamma}\leq 0 &\Leftrightarrow& \frac{q(1-\delta)\gamma}{ (1-\delta+\gamma)(q - q\delta - 1)} < 1\nonumber\\
&\Leftrightarrow& q(1-\delta)\gamma \leq (1-\delta+\gamma)(q - q\delta - 1) \label{eqn:derivativeSign}\\
&\Leftrightarrow&
\gamma \leq (1-\delta)(q - q\delta - 1) \nonumber
\end{eqnarray}
Note that \eqref{eqn:derivativeSign} is valid since $1-\delta+\gamma \geq 0$ and $\delta \leq 1 - \frac{1}{q} \Rightarrow q - q\delta - 1 \geq 0$.
One can also easily evaluate $f(\gamma, \delta)$ for $\gamma = (1-\delta)(q - q\delta - 1)$ to confirm claim (b).

\paragraph{Hessian Matrix and Characteristic Polynomial.} We now proceed to calculating the Hessian matrix of $f$ and forming its characteristic polynomial.

\begin{eqnarray}
H_f&=&\begin{bmatrix}
 H_{1, 1} & H_{1, 2}\\
 H_{2, 1} & H_{2, 2}
\end{bmatrix}
=\begin{bmatrix}
 \frac{\partial^2 f}{\partial \gamma^2} & \frac{\partial^2 f}{\partial \gamma \partial \delta}\\ \\
 \frac{\partial^2 f}{\partial \delta \partial\gamma} & \frac{\partial^2 f}{\partial \delta^2}\\
\end{bmatrix}\nonumber\\
&=&\begin{bmatrix}
 \frac{1-\delta}{\gamma  (1-\delta +\gamma) \log (q)} & \frac{\gamma +(1 - \delta)^2 q}{(1-\delta) (1 - \delta +\gamma) (q - q\delta -1) \log (q)} \\ \\
 \frac{\gamma +(1-\delta)^2 q}{(1-\delta) (1 - \delta +\gamma) (q - q\delta -1) \log (q)} & \frac{(1-\delta)^3 q^2 (1 - \delta + 2 \gamma)+(2 (1-\delta) q -1)\left(\gamma ^2-\gamma  (1-\delta)-(1-\delta)^2\right)}
 {(1-\delta)^2 (1-\delta + \gamma) (q - q\delta -1)^2 \log (q)}\label{eqn:Hessian}
\end{bmatrix}
\end{eqnarray}

We prove semi-definiteness by deriving the characteristic polynomial of $H_f$. The eigenvalues of $H_f$ are the roots of this polynomial.

\begin{eqnarray}
\det(H_f - \lambda I) = 0 &\Leftrightarrow &
\left|\begin{matrix}
H_{1, 1}-\lambda & H_{1, 2}\\
 H_{2, 1} & H_{2, 2}-\lambda
\end{matrix}\right|=0\nonumber\\
&\Leftrightarrow&
(H_{1, 1}-\lambda)(H_{2, 2}-\lambda) - H_{1, 2}H_{2, 1} = 0\nonumber\\
&\Leftrightarrow&
\lambda ^ 2 - (H_{1, 1} + H_{2, 2})\lambda
 + (H_{1, 1}H_{2, 2} - H_{1, 2}H_{2, 1}) = 0\label{eqn:characteristicPoly}
\end{eqnarray}
To prove the semi-definiteness of $H_f$, we show that both of its eigenvalues are non-negative, or equivalently, the roots of the quadratic equation \eqref{eqn:characteristicPoly} are both non-negative. We remind the reader of the straightforward fact that in a quadratic equation of form $x^2 - S x + P = 0$, $S$ is the sum of the roots and $P$ is their product. Therefore, to show that both roots are non-negative, we only need to show that $S$ and $P$ are both non-negative and that the roots are both real, i.e., $\Delta = S^2-4P \geq 0$.
\begin{enumerate}
    \item $H_{1, 1} + H_{2, 2} \geq 0$
    \item $H_{1, 1}H_{2, 2} - H_{1, 2}H_{2, 1} \geq 0$
    \item $(H_{1, 1} + H_{2, 2})^2-4(H_{1, 1}H_{2, 2} - H_{1, 2}H_{2, 1}) \geq 0$
\end{enumerate}

In the remainder of this section, we prove the three items listed above.

\paragraph{Proof of Item 1.} Given \eqref{eqn:Hessian}, we have that
\begin{eqnarray}
H_{1, 1} + H_{2, 2} &=& \frac{1}{\log (q)}\cdot \left(\frac{1}{\gamma }+\frac{\gamma  q^2}{(q - q\delta -1)^2}+\frac{\gamma  (1 - \gamma-\delta )}{(1-\delta)^2 (1-\delta+\gamma)}\right)\nonumber\\
&=& \frac{1}{\log (q)}\cdot \left(\frac{1}{\gamma }+\frac{\gamma }{(1 - 1/q -\delta)^2}+\frac{\gamma}{(1-\delta) (1-\delta+\gamma)}
-\frac{\gamma^2}{(1-\delta)^2 (1-\delta+\gamma)}
\right)
\end{eqnarray}
Note that terms $\frac{1}{\gamma }$ and $\frac{\gamma}{(1-\delta) (1-\delta+\gamma)}$ are positive. Therefore, to prove that $H_{1, 1} + H_{2, 2}$ is non-negative, we show that
\begin{equation}
\frac{\gamma }{(1 - 1/q -\delta)^2}
-\frac{\gamma^2}{(1-\delta)^2 (1-\delta+\gamma)}\geq 0.\label{eqn:item1-step2}
\end{equation}
Note that
\begin{eqnarray}
1-\delta-1/q < 1-\delta \Rightarrow
\frac{\gamma}{(1-1/q-\delta)^2} \geq \frac{\gamma}{(1-\delta)^2}.\label{eqn:item1-step3}
\end{eqnarray}
Also, since $\delta \leq 1$, we have that $1-\delta + \gamma \geq \gamma \Rightarrow \frac{\gamma}{1-\delta + \gamma} \leq 1$. Thus, \eqref{eqn:item1-step3} holds even if one multiplies its right-hand side by $\frac{\gamma}{1-\delta + \gamma}$ which gives \eqref{eqn:item1-step2} and, thus, proves Item 1.

\paragraph{Proof of Item 2.} Given \eqref{eqn:Hessian}, we have that
$$H_{1, 1}H_{2, 2} - H_{1, 2}H_{2, 1} =
\frac{(1-\delta)^2 (q-q\delta - 1)^2
-\gamma ^2
}{\gamma  (1-\delta)^2 (1-\delta+\gamma) (q - q\delta -1)^2 \log ^2(q)}.
$$
Note that all terms in the denominator are positive. The numerator is positive as well since, as mentioned earlier, the domain $D$ is defined only to include points $(\gamma,\delta)$ where $\gamma \leq (1-\delta)(q-q\delta-1)$.

\paragraph{Proof of Item 3.}
This claim can be simply shown to be true as follows: $$ (H_{1, 1} + H_{2, 2})^2-4(H_{1, 1}H_{2, 2} - H_{1, 2}H_{2, 1}) =
(H_{1, 1} - H_{2, 2})^2 + 4H_{1, 2}H_{2, 1} =
(H_{1, 1} - H_{2, 2})^2 + 4H^2_{1, 2}
$$
The final term is trivially positive. Note that the last step follows from the fact that $H_{1, 2}=H_{2, 1}$.
\popQED

\iffalse
\section{Issues with Inner and Outer Bounds of \cite{liu2019list}}\label{appdx:errors}

In this appendix, we provide some details about the key issues with the results of \cite{liu2019list}.

The different flaws in the outer and inner bounds of \cite{liu2019list} both relate in some way to the key difference between Hamming errors and insertion-deletion errors from a combinatorial perspective, namely the lack of symmetry of balls in the edit-distance metric. In particular, while the size or volume of a Hamming ball in $\Sigma^n$ only depends on its radius, the same is not at all true for a deletion ball, whose volume highly depends on the center of the ball. Indeed, the size of the radius $n/2$ deletion ball around the all-zero word $0^n \in \{0,1\}^n$ contains only the $n/2$ all-zero codewords with length between $n/2$ and $n$. On the other hand, the same $n/2$ radius deletion ball around the alternating codeword $(01)^{n/2} \in \{0,1\}^n$ contains all words with at most $n/2$ zeros and at most $n/2$ ones and thus particularly all $2^{n/2}$ words of length $n/2$. This exponentially large dependence of ball's volume on the (code)word the ball is centered on makes the typical volume-based arguments used to analyze error-correcting codes a much harder and more delicate issue for insertion-deletion errors compared to Hamming errors.

This subtlety is also the crux of the matter in the outer bound stated as Theorem 1 on page 12 of \cite{liu2019list}. In particular, equation (6) in the proof of Theorem 1 indirectly claims that one can measure the average overlap of a code $C$ with a (uniformly random) ball of radium $\tau n$, i.e., $\sum_{c \in \Sigma^n} |B(c, \tau n) \cap C|$, by equating it to the appropriately scaled average volume of a (uniformly random) ball, i.e., $\frac{|C|}{|\Sigma^n|} \cdot \sum_{c \in \Sigma^n} |B(\tau n,c) \cap \Sigma^n|$. This equation and its useful independence from the structure of $C$ does hold for Hamming balls but completely falls apart for insertion-deletion balls, exactly due to the above-explained lack of symmetry. Without this crucial averaging or symmetrization step, the volume estimates of \cite{liu2019list} cannot be applied to give valid outer bounds of insertion-deletion codes. This affects all results concerning the rate of error-correcting codes in the outer bound Section 4 of \cite{liu2019list}, particularly, Theorem 1 and everything thereafter.

The inner bounds of \cite{liu2019list} given in Section 5, particularly Theorem 2 and the more specialized lemmas and corollaries thereafter, suffer from a slightly different problem, which goes back to the volume estimations of insertion-deletion balls in Lemma 8. The proof of Lemma 8 first uses a classical lower bound on the size of the deletion ball ($S_D$) and then, at the top of page 10, sums up the volumes of the insertion balls around every codeword within $S_D$ to derive a lower bound on the volume of the insertion-deletion ball, which is a rather intricate object. This summation does not take into account the (significant) overlaps between the insertion balls around (closely related) words in $S_D$ and thus fails to give a valid volume lower bound for the union of these balls. Unfortunately, estimating or more accurately lower bounding the volume of an insertion-deletion ball is the key step needed to analyze the list-decodability of random codes.

The authors of this paper have confirmed the above problems with the authors of \cite{liu2019list}

\fi
\section{Introduction}
Error-correcting codes are classic combinatorial objects that have been extensively studied since late 40s with broad applications in a multitude of communication and storage applications. While error-correcting codes are mostly studied within the setting that concerns symbol substitutions and erasures (i.e., Hamming-type errors), there has been a recent rise of interest in codes that correct from synchronization errors, such as insertions and deletions, from both theoretical~\cite{brakensiek2016efficient,bukh2017improved,guruswami2016efficiently,guruswami2017deletion,haeupler2017synchronization,haeupler2017synchronization3,haeupler2017synchronization2, haeupler2019near,cheng2019synchronization, liu2019list,liu2019explicit,  haeupler2019optimal, cheng2019block, cheng2018deterministic,guruswami2019optimally,cheng2020efficient,cheraghchi2019overview} and practical perspectives~\cite{organick2017scaling,blawat2016forward,goldman2013towards,church2012next,yazdi2015dna,bornholt2016dna}. Such codes and their relevant qualities are defined in the same fashion as error-correcting codes, except that the minimum distance requirement is with respect to the pairwise \emph{edit distance} between code words.

Compared to error-correcting codes for Hamming errors synchronization codes are far less understood and many fundamental questions about them remain to be explored. One such important question is the rate-distance trade-off for (worst-cases) synchronization errors, i.e., determining the largest rate that any synchronization code can achieve in the presence of a certain amount of synchronization errors. We address this question in the list-decoding setting.

A code is list-decodable if there exists a decoder $D$ which, for any corrupted codeword (within the desired error bounds), outputs a small size list of codewords that is guaranteed to include the uncorrupted codeword.
More formally, an insertion-deletion code $C \subseteq \Sigma^n$ (or insdel code, for short) is $(\gamma,\delta,L)$-list-decodable if there exists a function $D:\Sigma^*\to 2^C$ such that $|D(w)| \leq L$ for every $w \in \Sigma^*$ and for every codeword $x \in C$ and every word $w$ obtained from $x$ by at most $\gamma \cdot n$ insertions and at most $\delta\cdot n$ deletions., it is the case that $x \in D(w)$. The parameter $L$ is called the list-size.
These definitions naturally extend to families of codes with increasing block lengths in the usual way: A family of codes is $(\gamma,\delta, L(\cdot))$-list decodable if  each member of the family is $(\gamma,\delta, L(n))$-list decodable where $n$ denotes the block length. Often the function $L$ is omitted and a family of $q$-ary codes $\mathcal{C}$ is said to be $(\gamma,\delta)$-list decodable if there exist some polynomial function $L(\cdot)$ for which $\mathcal{C}$ is $(\gamma,\delta, L(\cdot))$-list decodable. The rate $R$ of a family of $q$-ary codes $\mathcal{C}$ is defined as $R = \lim_{n \rightarrow \infty} \frac{\log_q |C_n|}{n}$.

The fundamental question studied in this paper is to understand the inherent trade-off between the communication rate of a $q$-ary list-decodable insdel code and the amount of synchronization errors it can correct, i.e., the error parameters $\gamma$ and $\delta$. For every fixed alphabet size $q$, this trade-off can be nicely plotted as a 3D-surface in a 3D-chart which plots the maximum communication rate on the $z$-axis for all $\gamma$ and $\delta$ (plotted on the x- and y-axes respectively). See \Cref{fig:q=5-intro-simple} for an example of such a 3D-plot.

 \begin{figure}
     \centering
     \includegraphics[scale=.5]{q=5-no-floor.jpg}
     \caption{Depiction of our outer bound for $q=5$.}
     \label{fig:q=5-intro-simple}
 \end{figure}

\begin{sidewaysfigure}
    \centering
    \includegraphics[width=1\textwidth]{Fancy_Plot_no_floor.pdf}
    \caption{Depiction of our outer bound for $q=5$ and its three projections for the insertion-only case (on the right), the deletion-only case (on the left), and the zero-rate case (on the bottom). The projection graphs are exactly matching the state-of-the-art results of \cite{haeupler2018synchronization4,guruswami2019optimally}.}
    \label{fig:q=5-intro}
\end{sidewaysfigure}

Of course, determining the exact communication rate values for any $q$ and any non-trivial values of $(\gamma,\delta)$ is beyond the capability of current techniques. Prior work (described in \cref{sec:prior-work}) has furthermore mainly focused on obtaining a better understanding of certain special cases, which correspond to projections or cuts of the general trade-off plot. In particular, \Cref{fig:q=5-intro} shows the 2D cuts/projections onto the xz- and yz-planes, which correspond to the insertion-only setting with $\delta=0$ and the deletion-only setting with $\gamma=0$, as well as the projection/cut onto the yz-plane specifying for which error rate combinations of $\gamma$ and $\delta$ the communication rate hits zero. See \Cref{fig:q=5-intro} for examples of these three 2D-projections. It has also been studied how the shape of the 3D-plot changes asymptotically as $q$ gets larger.

\subsection{Our Results

This paper is (one of) the first to give results for the entirety of the 3D trade-off between communication rate and the two error rates for every fixed alphabet size $q$. We primarily focus on giving good outer bounds, i.e., impossibility results proving limits on the best possible communication rate (for any given $\gamma,\delta$, and $q$). The novel outer bounds we prove are given in the 3D-plot of \Cref{fig:q=5-intro} for an alphabet size of $q = 5$ (similar plots for any given $q$ apply). We develop these outer bounds in \cref{sec:outer bound}.

A notable property of our new outer bound is that, for every $q$, it exactly matches the best previously known results on all three aforementioned projections/cuts. That is, the outer bound implied for deletion-only codes (i.e., the cut on $\gamma = 0$ plane) matches the deletion-only bound from \cite{haeupler2018synchronization4}. Similarly, we match the best insertion-only bounds known when restricting or projecting our new general outer bound result to the $\delta = 0$ plane. Finally, the error resilience implied by our bound (i.e., where the curve in \Cref{fig:q=5-intro} hits the floor) precisely matches the list-decoding error resilience curve for insertions and deletions as identified by \cite{guruswami2019optimally}. As such, our bound fully encapsulates and truly generalizes the entirety of the current state-of-the-art of the fundamental rate-distance trade-off for list-decodable insertion-deletion codes for any fixed alphabet size $q$.

Lastly, for the sake of completeness and as a comparison point, we also provide a general inner bound in \cref{sec:inner_bound}. This general existence result is obtained by analyzing the list-decodability of random codes. We do this mainly through a simple bound on the size of the insertion-deletion ball. \Cref{fig:q=5-upper-and-lower} illustrates this inner bound in contrast to the outer bound depicted in \Cref{fig:q=5-intro}, also for $q=5$. It is worth noting that, in contrast to our outer bound, the cut onto the xy-plane does not match the precise error resilience identified (through matching inner and outer bounds) in \cite{guruswami2019optimally}. However, the cuts onto the xz and yz planes do match the inner bounds of \cite{haeupler2018synchronization4} for insertion-only and deletion-only cases, which were also derived by analysis of random codes. We generally believe our outer bounds to be closer to the true zero-error list-decoding channel capacity

\begin{figure}
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=1.06\linewidth]{q=5-upper-and-lower-floor-removed-3.png}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=1.06\linewidth]{q=5-upper-and-lower-floor-removed-4.png}
\end{subfigure}
\caption{Depiction of our inner and outer bounds for $q=5$ from two angles. The more transparent surface is the outer bound of \cref{sec:outer bound} and the surface underneath is the inner bound derived in \cref{sec:inner_bound}.}
\label{fig:q=5-upper-and-lower}
\end{figure}

\subsection{Related Work}\label{sec:prior-work}
This paper studies the fundamental rate-distance trade-off for error correcting codes which are capable of list-decoding from worst-cases insertions and deletions, a topic which has attracted significant attention over the last three years~\cite{guruswami2017deletion,wachter2017list,hayashi2018list,haeupler2018synchronization4,guruswami2019optimally,liu2019list}. We summarize these prior works in detail in this section. The multitude of related work on similar questions, such as, (efficient) list-decoding from Hamming errors, unique-decodable insdel codes, or decoding from random insertions or deletions are too many to list or discuss here. Instead, we refer the interested reader to the following (recent) surveys \cite{cheraghchi2019overview,mitzenmacher2009survey,guruswami2004list,mercier2010survey,haeupler2020survey}, which give detailed accounts of such works.

As noted above, with the exception of~\cite{liu2019list}, mostly special cases of the general rate-distance trade-off for list-decodable insdel codes have been studied up to now. This includes in particular (combinations of) the deletion-only case (with $\gamma=0$), the insertion-only case (with $\delta=0$), the zero-rate regime or resilience case asking for what extremal values of $(\gamma,\delta)$ a non-zero rate can be obtained, and the case of large alphabets where the alphabet size $q=O(1)$ is allowed to be a large constant that can depend on the error rates $(\gamma, \delta)$.

\subsubsection{List-Decodable Insdel Codes Over Large Constant-Size Alphabets}
The rate-distance tradeoff for list-decodable error correcting codes has been studied in \cite{haeupler2018synchronization4} under the large alphabet setting, that is the question of finding the largest possible achievable rate that $(\gamma,\delta)$-list-decodable families of codes can achieve as long as their alphabet size is constant $q=O_{\gamma, \delta}(1)$ (i.e., independent of the block length).
Using a method of constructing insdel codes by indexing ordinary error-correcting codes with synchronization strings introduced in \cite{haeupler2017synchronization}, \cite{haeupler2018synchronization4} shows the following: For every $\delta \in (0, 1)$, $\gamma \geq 0$, and sufficiently small $\varepsilon > 0$, there exists an efficient family of $(\gamma,\delta)$-list-decodable codes over an alphabet of size $q=O_{\gamma, \delta, \varepsilon}(1)$ that achieve a rate of $1-\delta-\varepsilon$ or more. It is easy to verify that no such family of codes can achieve a rate larger than $1-\delta$.

The result of \cite{haeupler2018synchronization4} points out an interesting and indeed very drastic distinction between insertions and deletions in the list-decoding setting. In the  unique-decoding setting the effect of insertions and deletions are symmetric, and the rate-distance tradeoff can be fully measured solely in terms of the edit-distance between codewords. For list-decoding it turns out that insertions behave completely different than deletions. Indeed while any $\delta$ fraction of deletions will definitely reduce the rate at the very least to $1 - \delta$, in the very extreme the impact of insertion errors can be fully compensated by taking the alphabet appropriately large. This is what makes the maximum achievable rate for arbitrarily large constant alphabets merely a function of the deletion error rate $\delta$. This stark distinction in the effects insertions and deletions have on the rate-distance tradeoff for list-decodable codes is the reason why it is crucial to use the two parameters $\gamma$ and $\delta$ to keep track of insertions and deletions separately.

\subsubsection{Error Resilience of List-Decodable Insdel Codes}

An important special case of the rate-distance trade-off for list-decodable insertion-deletion codes is the question of the best possible \emph{error resilience}. In particular, the question of what the ``largest" fraction of errors is against which list-decoding is possible for some positive-rate code -- or differently speaking, at what point(s) the maximum achievable rate of a list-decodable code hits zero-rate. Understanding this question is, in some way, a prerequisite to meaningfully talk about more general positive rates. Still, even when restricted to binary deletions-only or insertions-only codes getting good bounds on the error resilience is highly non-trivial (in contrast to the Hamming case) and has only recently been solved these special cases and general insertion-deletion errors~\cite{guruswami2019optimally}.

For deletion-only codes, i.e., the special case where $\gamma = 0$, Guruswami and Wang~\cite{guruswami2017deletion} gave binary codes that correct a $\delta = \frac{1}{2} - \epsilon$ fraction of errors attaining a $\operatorname{\text{{\rm poly}}}(\epsilon)$ rate for any $\epsilon > 0$. This implies that the error resilience for deletion coding is precisely $\delta_0 = \frac{1}{2}$ since, with a fraction of deletions $\delta \geq \frac{1}{2}$, an adversary can simply eliminate all instances of the least frequent symbol and convert any codeword from $\{0, 1\}^n$ into either $0^{n/2}$ or $1^{n/2}$.

In 2017 a work of Wachter-Zeh~\cite{wachter2017list} gave Johnson-type bounds on list-decodability and list-sizes of codes given their minimum edit-distance. In 2018, Hayashi and Yasunaga~\cite{hayashi2018list} made corrections to the results presented in \cite{wachter2017list}, and further showed that such bounds give novel results for the insertion-only case of resilience. In particular, they prove that the codes introduced by Bukh, Guruswami, and H\aa stad~\cite{bukh2017improved} can be list-decoded from up to $\gamma = 0.707$ fraction of insertions (and no deletions) while maintaining a positive-rate.

Very recently, Guruswami et al.~\cite{guruswami2019optimally} improved this fraction of insertions to an optimal $\gamma < 1$. Much more generally \cite{guruswami2019optimally} were able to tightly and fully identify the error resilience region for codes that are list-decodable from a mixture of insertions and deletions, i.e., determine exactly and for any given $q$ the set of all $(\gamma, \delta)$s where the largest achievable rate for $q$-ary $(\gamma,\delta)$-list decodable codes is non-zero. This fully resolved the zero-rate projection of the question addressed in this paper (shown in the bottom 2D chart of \Cref{fig:q=5-intro}).

\subsubsection{Alphabet dependent rate results for the deletion-only and insertion-only case}

The two other projections, i.e., bounds on the highest achievable rate for the insertion-only ($\delta = 0$) and deletion-only ($\gamma = 0$) cases in dependence on $q$ and the error parameter ($\gamma$ and $\delta$ respectively) were given by Haeupler et al.~\cite{haeupler2018synchronization4}. These projections are shown in \Cref{fig:q=5-intro} to the right and left respectively. The inner bounds presented in \cite{haeupler2018synchronization4} are derived by analyzing list-decoding properties of random codes. Here, we briefly review (the ideas of) the outer bounds from \cite{haeupler2018synchronization4} as these will be helpful for the remainder of this paper.

\paragraph{Deletion-only case.} A simple observation for deletion-only channels is that no family of positive-rate $q$-ary codes can be list-decoded from $\delta \geq 1-\frac{1}{q}$ fraction of deletions. This is due to a simple strategy that adversary can employ to eliminate all occurrences of all symbols of the alphabet except the most frequent one to convert any sent codeword into a word like $a^{n(1-\delta)}$ for some $a\in[q]$. \cite{haeupler2018synchronization4} suggest a similar strategy called \emph{Alphabet Reduction} for the adversary when $\delta = \frac{d}{q}$ for some integer $d$. With $\delta = \frac{d}{q}$ fraction of deletions, an adversary can remove all instances of the $d$ least frequent symbols and, hence, convert any transmitted codeword into a member of an ensemble of $(q-d)^{n(1-\delta)}$ strings. This implies an outer bound of $\frac{\log (q-d)^{n(1-\delta)}}{n\log q} = (1-\delta)\left(1-\log_q\frac{1}{1-\delta} \right)$ on the largest rate achievable by list-decodable deletion codes for special values of $\delta = \frac{d}{q}$ where $d = 1, 2, \cdots, q-1$. Using a simple time sharing argument between the alphabet reduction strategy over these points, \cite{haeupler2018synchronization4} provides a piece-wise linear outer bound for all values of $0 < \delta < 1-\frac{1}{q}$.

\paragraph{Insertion-only case.} In an insertion channel, the received word contains the sent codeword as a subsequence. To provide an outer bound on the highest achievable rate by insertion codes, \cite{haeupler2018synchronization4} used the probabilistic method: For a given codeword $x\in[q]^n$, \cite{haeupler2018synchronization4} computes the probability of a random string $y\in[q]^{n(1+\gamma)}$ containing $x$ as a subsequence. Having this quantity, one can compute the expected number of codewords of a given code $C$ with rate $r$ that are contained in a random string $y\in[q]^{n(1+\gamma)}$. Note that if $r$ is so high that this expectation is exponentially large in terms of $n$, then, by linearity of expectation, there exists some string $\bar{y}\in[q]^{n(1+\gamma)}$ which contains exponentially many codewords of $C$ which is a contradiction to its list-decodability from $\gamma n$ insertions. This implies an outer bound for the communication rate which we describe in more details below.

\subsubsection{General Case}

A recent work by Liu et al.~\cite{liu2019list} is the first to study the rate of list-decodable insertion-deletion codes in the same full generality as this paper. Unfortunately, after discovering direct contradictions between our results and the claims in \cite{liu2019list} we identified several correctness issues\footnote{Equation (6) in the proof of Theorem 1 is incorrect. The problem stems from the implicit assumption that the volume of a ball is independent of its center - which is true for Hamming balls but not insertion-deletion balls. Another issue stems from Lemma 8 which sums up volume estimates for insertion balls to lower bound the volume of their union without taking overlaps into account. All references above are with respect to the current arXiv version (v5) of \cite{liu2019list}.} with key approaches of~\cite{liu2019list}, particularly in the outer bounds. These issues seem hard to fix without substantially new ideas\footnote{We confirmed this with the authors of \cite{liu2019list} when we shared our results and these correctness issues mid July 2020. A correction to \cite{liu2019list} without the outer bound results is currently forthcoming.}.

\section{Outer Bounds}\label{sec:outer bound}

\subsection{Linear Outer Bounds from Resilience Results}

We start this section by providing a simple outer bound for best possible rate of an insdel code by generalizing the tight results for the resilience region of \cite{guruswami2019optimally} into a rate bound for any $(\gamma,\delta)$. Recall that the resilience region $F_q$ for any (integer) alphabet size $q >2$ is defined as the set of error rates for which there exists list-decodable codes with positive rate, i.e.,
$$F_q = \left\{ (\gamma,\delta) \mid 0 \leq \delta \leq 1, 0 \leq \gamma \leq q-1,
\exists \  (\gamma,\delta)\text{-list decodable code family with positive rate}\right\}.$$
In \cite{guruswami2019optimally}, the following exact description of $F_q$ was given:

\begin{theorem}[Theorem 1.3 of \cite{guruswami2019optimally}]\label{thm:feasibility-region}
For any positive integer $q \geq 2$, the resilience region $F_q$ is exactly the concave polygon defined over vertices $\left(\frac{i(i-1)}{q}, \frac{q-i}{q}\right)$ for $i = 1, \cdots, q$ and $(0, 0)$, not including the borders except the two segments
$\left[(0, 0), (q-1, 0)\right)$ and $\left[(0, 0), \left(0, 1-1/q\right)\right)$. (See \Cref{fig:actual-region})\\
In particular, for any $\varepsilon > 0$ and any $(\gamma, \delta) \in (1-\varepsilon)F_q$, there exists a family of $q$-ary codes with positive rate that is $(\gamma, \delta)$-list-decodable. Further, for any $(\gamma, \delta) \not\in F_q$ there exists no $(\gamma, \delta)$-list-decodable family of $q$-ary codes with positive rate.

\end{theorem}

\begin{figure}[]
  \centering
  \includegraphics[height=2in]{Region.png}
  \caption{Resilience region for $q=5$.}\label{fig:actual-region}
\end{figure}

We show that the multiplicative distance to this resilience region gives a valid outer bound on the rate of any list-decodable insertion-deletion code:

\begin{theorem}\label{thm:convex-hull-outer bound}
For any alphabet size $q$ and any $(\gamma,\delta) \in F_q$ let $\alpha \geq 1$ be the smallest number such that $(\alpha \gamma,\alpha\delta) \notin R_q$. Any family of $(\gamma,\delta)$-list decodable $q$-ary codes cannot achieve a rate of more than $1 - 1/\alpha$.
\end{theorem}

A different way of looking at this outer bound is to think of it as the collection of lines that connect every point on the (border of the) resilience region $F_q$ identified in \cref{thm:feasibility-region} on the $r=0$ plane and the point $(\gamma,\delta, r) = (0,0, 1)$ which indicates the trivial achievable rate of 1 in the absence of noise. (See \Cref{fig:outer bound-with-resilience})

\begin{figure}[]
  \centering
  \includegraphics[scale=.7]{q=5-bound-via-resilience-no-floor-lines.png}
  \caption{Illustration of the outer bound from \cref{thm:convex-hull-outer bound} for $q=5$.}\label{fig:outer bound-with-resilience}
\end{figure}

The proof of \Cref{thm:convex-hull-outer bound} is easy once one recalls how the outer bound for the feasibility region $R_q$ is proven in \cite{guruswami2019optimally}. It basically consists of a simple strategy transforming any sent string into one of a small $O_q(1)$ number of canonical strings, thus erasing almost all information sent. One can prove \Cref{thm:convex-hull-outer bound} by doing the same but only on an $\frac{1}{\alpha}$ fraction of the string. We present an alternative and shorter formal proof in the following.

\begin{proof}[Proof of \Cref{thm:convex-hull-outer bound}]
Assume for the sake of contradiction that for some $(\gamma,\delta) \in F_q$, for which $(\alpha \gamma,\alpha\delta) \notin R_q$, there exists a family of $(\gamma, \delta)$-list-decodable codes $\mathcal{C}$ with a higher rate than $1-\frac{1}{\alpha}$, i.e., codes $\mathcal{C} = \{C_1, C_2, \cdots\}$ with block lengths $n_1 < n_2 < \cdots$ and rates $r_1, r_2, \cdots$ that satisfy $r = \lim_{i\rightarrow \infty} r_i = 1-\frac{1}{\alpha}+\varepsilon$ for some $\varepsilon > 0$.

We convert this family of codes to a new family of codes $\mathcal{C}'$ by converting each code $C_i$ into a code $C'_i$ as follows: In all codewords of $C_i$, consider the $n_i\left(1-1/\alpha\right)$-long prefix. Among all such prefixes, let $p$ be the most frequent one. We set $C'_i$ to be a code containing all codewords of $C_i$ that start with $p$. Since all such codewords start with $p$, we omit the prefix $p$ from all such codewords. Note that the block length of $C'_i$ is $n'_i = n_i - n_i \left(1-1/\alpha\right) = n_i/\alpha$. Also, since there are $q^{n_i\left(1-1/\alpha\right)}$ $q$-ary strings of length $n_i\left(1-1/\alpha\right)$,
$$|C'_i| \geq \frac{|C_i|}{ q^{n_i\left(1-1/\alpha\right)} }=\frac{q^{n_i r_i}}{ q^{n_i\left(1-1/\alpha\right)} } = q^{n_i (r_i-1+1/\alpha)}.$$
This implies that the rate of $C'_i$ is at least
$$r'_i= \frac{\log_q |C'_i|}{n'_i} \geq \frac{n_i (r_i-1+1/\alpha)}{n'_i} = \alpha(r_i-1+1/\alpha)$$
and, hence, the rate of the family of codes $\mathcal{C}'$ is at least $\lim_{i\rightarrow\infty} r'_i \geq \alpha\varepsilon > 0$.

Further, we claim that if $\mathcal{C}$ is $(\gamma, \delta, L(n))$-list decodable, then $\mathcal{C}'$ will be $(\alpha\gamma, \alpha\delta, L(\alpha n'))$-list decodable. To show this, we construct such list-decoder for all codes $C'_i \in \mathcal{C}'$ with input $y'$ by simply padding the most frequent $n_i(1-1/\alpha)$-prefix of codewords of $C_i \in \mathcal{C}$, $p$, in front of $y'$ and running the list-decoder of $C_i$ with input $y = p\cdot y'$. Among the list generated by the decoder of $C_i$, the ones that do not start with $p$ are withdrawn. The remaining strings will form the output of our list-decoder for $C'_i$ after omitting their prefix $p$. Note that this indeed gives a $(\alpha\gamma, \alpha\delta, L(\alpha n'))$-list-decoder since for any codeword $x\in C'_i$ that is $(\alpha\gamma, \alpha\delta)$-close to $y$, $p\cdot x \in C_i$ is $(\gamma, \delta)$-close to $p\cdot y$.

We were able to show that the family of codes $\mathcal{C}'$ achieves a positive rate and is $(\alpha\gamma, \alpha\delta)$-list decodable for $(\alpha\gamma, \alpha\delta) \notin F_q$. This is a contradiction to \cref{thm:feasibility-region} proving that the rate of $\mathcal{C}'$ may not exceed $1-\frac{1}{\alpha}$, thus, proving the theorem.
\end{proof}

We remark that one can interpret the outer bound from \Cref{thm:convex-hull-outer bound} as a convexity argument in the following manner: We know that no code can achieve a rate of one in the presence of even a small amount of noise. The point $(\gamma, \delta, r) = (0,0,1)$ is therefore part of the (in)feasibility boundary. Further, the resilience result from \cite{guruswami2019optimally} demonstrates that all points within the region $R = \{(\gamma, \delta, 0)\ |\ (\gamma, \delta) \not\in F_q\}$ are infeasible. \Cref{thm:convex-hull-outer bound} shows that any convex combination of $(0,0,1)$ and any point in $R$ is infeasible as well, implying a pyramid-shaped feasibility region with $F_q$ as its base and $(0, 0, 1)$ as its apex. (See \Cref{fig:outer bound-with-resilience}.)
We remark that generally convex combinations of infeasible points in the rate-distance tradeoff are not known to be infeasible - even for much simpler settings including Hamming errors or unique-decoding. Even convexity results between known infeasible points can be quite challenging. Case in point, our tighter outer bound in \cref{sec:tight-outer-bound} is proven by showing infeasibility of convex combinations of (easier) infeasible points.

\subsection{Stronger Bounds Using Generalizations of Bounds from \cite{haeupler2018synchronization4}}\label{sec:tight-outer-bound}

While \Cref{thm:convex-hull-outer bound} gives a bound for all $(\gamma,\delta)$, it is easy to see that it can be quite far from guarantees given by other state-of-the-art outer bounds. This is especially apparent for the deletion-only and insertion-only cases where \Cref{thm:convex-hull-outer bound} implies fairly trivial rate bounds of $1 - \frac{\delta}{1-1/q}$ and $1 - \frac{\gamma}{q-1}$, respectively. In particular, for the insertion-only case the following outer bound of \cite{haeupler2018synchronization4} gives much tighter bounds than $1 - \frac{\gamma}{q-1}$:

\begin{theorem}[From \cite{haeupler2018synchronization4}]\label{thm:converse}
 For any alphabet size $q$ and error rate $\gamma < q-1$, any family of $q$-ary codes $\mathcal{C}$ which is list-decodable from a $\gamma$ fraction of insertions has a rate of no more than $1- \log_q(\gamma+1)-\gamma\left(\log_q\frac{\gamma+1}{\gamma} - \log_q \frac{q}{q-1}\right)$.
\end{theorem}

Next, We show how to use \Cref{thm:converse} in a black-box fashion to give a very clean and easily statable outer bound for settings with both insertions and deletions, but in which the fraction of deletions has a nice form, in particular, is a multiple of $\frac{1}{q}$. This outer bound forms the backbone of our final result.

\begin{theorem}\label{thm:nicedelta}
 For any alphabet size $q$, any insertion rate $\gamma < q-1$ and any deletion rate $\delta = \frac{d}{q}$ for some integer $d \leq q$, it is true that any family of $q$-ary codes $\mathcal{C}$ which is $(\gamma,\delta)$-list-decodable has a rate of at most $(1-\delta)\left[
\left(1 + \frac{\gamma}{1-\delta}\right)\log_q\frac{q-d}{\frac{\gamma}{1-\delta}+1}
-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{q-d-1}{\frac{\gamma}{1-\delta}}\right)\right]$.
\end{theorem}
\begin{proof}
Consider a code $C$ that is $(\gamma,\delta)$-list-decodable and assume that $\delta = \frac{d}{q}$ for some integer $d$.
Assume that we restrict the adversary to utilize its deletions in the following manner: The adversary uses the $\frac{d}{q}$ deletion to remove all occurrences of the $d$-least frequent symbols of the alphabet. If there are remaining deletions, the adversary removes symbols from the end of the transmitted word.

Let us define the code $C'$ that is obtained from $C$ by deleting a $\delta$ fraction of symbols from each codeword of $C$ as described above. Note that the block length of $C'$ is $n'=n(1-\delta)$ and each of its codewords consist of up to $q'=q(1-\delta) = q-d$ symbols of the alphabet though this subset of size $q-d$ may be different from codeword to codeword. We partition the codewords of $C'$ into $q \choose q-d$ sets $C'_1, C'_2, \cdots, C'_{q \choose q-d}$ based on which $(q-d)$-subset of the alphabet they consist of.

Since $C$ is $(\gamma,\delta)$-list-decodable, each of the $C'_i$s are list-decodable from $\gamma n$ insertions. Therefore, \cref{thm:converse} implies that the size of each code $C'_i$ is no larger than:
$$q'^{n'\left[1- \log_{q'}(\gamma'+1)-\gamma'\left(\log_{q'}\frac{\gamma'+1}{\gamma'} - \log_{q'} \frac{q'}{q'-1}\right)\right]}$$
where $q'=q-d$, $n'=n(1-\delta)$, and $\gamma' = \frac{\gamma}{1-\delta}$. Therefore, the size of the code $C$ is no larger than
$${q\choose q-d} q^{n(1-\delta)\left[\log_q q'- \log_{q}(\gamma'+1)-\gamma'\left(\log_{q}\frac{\gamma'+1}{\gamma'} - \log_{q} \frac{q'}{q'-1}\right)\right]}$$
and, consequently, its rate is no larger than
\begin{eqnarray*}
&(1-\delta)\left[\log_q (q-d)- \log_{q}\left(\frac{\gamma}{1-\delta}+1\right)-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{\gamma+1-\delta}{\gamma} - \log_{q} \frac{q-d}{q-d-1}\right)\right]\\
=&(1-\delta)\left[
\left(1 + \frac{\gamma}{1-\delta}\right)\log_q\frac{q-d}{\frac{\gamma}{1-\delta}+1}
-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{q-d-1}{\frac{\gamma}{1-\delta}}\right)
\right]\label{eqn:nice-delta-outer bound}.
\end{eqnarray*}
\end{proof}

Given the nice and explicit form of \Cref{thm:nicedelta} for any $q$ and $\gamma$ with multiple specific values of $\delta$, it seems tempting to conjecture that the restriction of $\delta$ is unnecessary making
$(1-\delta)\left[
\left(1 + \frac{\gamma}{1-\delta}\right)\log_q\frac{q-d}{\frac{\gamma}{1-\delta}+1}
-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{q-d-1}{\frac{\gamma}{1-\delta}}\right)\right]$ a valid outer bound for any value of $\delta$ (and $\gamma$). This, however, could not be further from the truth. Indeed, for any $\delta$ not of the form restricted to by \Cref{thm:nicedelta}, there exists a $\gamma$ for which this extended bound is provably wrong because it contradicts the existence of the list-decodable codes constructed in \cite{guruswami2019optimally}.

In fact, for the valid points where $\delta$ is a multiple of $\frac{1}{q}$, the rate bound of \Cref{thm:nicedelta} hits zero at exactly the corner points of the piece-wise linear resilience region $F_q$ characterized by \Cref{thm:feasibility-region}. Taking this as an inspiration, one could try to extend the bound of \Cref{thm:nicedelta} to all values of $\delta$ by considering for each $q$ and each rate $r$ the roughly $\frac{q}{r}$ points where \Cref{thm:nicedelta} hits the  plane corresponding to rate $r$ and extend these points in a piece-wise linear manner to a complete 2D-curve for this rate $r$. This would give a rate bound for any $\gamma,\delta$, and $q$ as desired, which reduces to a piece-wise linear function for any fixed $r$ and also correctly reproduce $F_q$ for $r=0$.

It turns out that this is indeed a correct outer bound. However, a stronger form of convexity, which takes full 3D-convex interpolations between any points supplied by \Cref{thm:nicedelta} and in particular combines points with different rates, also holds and is needed to give our final outer bound.

\begin{theorem}\label{thm:mainconvexitystatement}
For a fixed $q$ suppose that $(\gamma_0, \delta_0=\frac{d_0}{q})$ and $(\gamma_1, \delta_1=\frac{d_1}{q})$ are two error rate combinations for which \Cref{thm:nicedelta} implies a maximal communication rate of $r_0$ and $r_1$, respectively. For any $0 \leq \alpha \leq 1$ consider the following convex combinations of these quantities: $\gamma = \alpha\gamma_0+(1-\alpha)\gamma_1$, $\delta = \alpha\delta_0+(1-\alpha)\delta_1$, and $r = \alpha r_0 + (1-\alpha)r_1$.
It is true that any $(\delta,\gamma)$-list-decodable $q$-ary code has a rate of at most $r$.
\end{theorem}
See \Cref{fig:q=2} for an illustration of this bound for $q=5$. Red curves indicate the outer bound described above for the special values of $\delta$ of the form $\frac{d}{q}$ as given by \Cref{thm:nicedelta}.

\Cref{thm:mainconvexitystatement} together with \Cref{thm:nicedelta} gives a conceptually very clean description of our outer bound. However, an (exact) evaluation of the outer bound as given by \Cref{thm:mainconvexitystatement} is not straightforward since there are many convex combinations which all produce valid bound but how to compute or select the one which gives the strongest guarantee on the rate for a given $(\gamma,\delta)$ pair is not clear. This is particularly true since, as already mentioned above, the optimal points to combine do not lie on the same rate-plane. To remedy this, we give, as an alternative statement to  \Cref{thm:mainconvexitystatement}, the next theorem which produces an explicit outer bound for any $(\gamma, \delta)$ as an $\alpha$-convex combination of two points $(\gamma_0, \delta_0)$ and $(\gamma_1, \delta_1)$ only in dependence on the free parameter $\gamma_0$. We then show in \Cref{lem:optimal-gamma} an explicit expression for the optimal value for $\gamma_0$. Together, this produces a significantly less clean but on the other hand fully explicit description of our outer bound.

\begin{sidewaysfigure}
    \centering
    \includegraphics[width=1\textwidth]{q=5-with-insertions-no-floor-with-resilience.jpg}
    \caption{Outer bound for rate for $q=5$. The special case where $\delta=\frac{d}{q}$ for some integer $d$ is indicated with red lines.}
    \label{fig:q=2}
\end{sidewaysfigure}

\begin{theorem}\label{thm:outer bound}
Let $C$ be a $q$-ary insertion-deletion code that is list-decodable from $\gamma \in [0, q-1]$ fraction of insertions and $\delta \in [0, 1-\frac{1}{q}]$ fraction of deletions. Then, the rate of $C$ is no larger than
\begin{eqnarray*}
&&    \alpha\left(1-\frac{d}{q}\right) \left(
(1+\gamma_0)\log_{q} \frac{q-d}{1+\gamma_0}
-
\gamma_0 \log_{q}\frac{q-d - 1}{\gamma_0}
\right)\\
&+&
(1-\alpha)\left(1-\frac{d+1}{q}\right)\left(
(1+\gamma_1)\log_{q} \frac{q-d-1}{1+\gamma_1}
-
\gamma_1 \log_{q}\frac{q-d - 2}{\gamma_1}
\right)
\end{eqnarray*}
for $d =\lfloor \delta q \rfloor$, $\alpha = 1 - \delta q + d$, and all $\gamma_0, \gamma_1 \geq 0$ where
$\alpha(1-\frac{d}{q})\gamma_0
+
(1-\alpha)(1-\frac{d+1}{q}) \gamma_1
 = \gamma$. We present the optimal choice of $\gamma_0$ in \cref{lem:optimal-gamma}.
\end{theorem}

\begin{proof}[Proof of \cref{thm:outer bound,thm:mainconvexitystatement}]

We first note that the statements of \cref{thm:outer bound} and \cref{thm:mainconvexitystatement} are merely a rephrasing of each other with the exception that \cref{thm:outer bound} only allows and optimizes over convex combinations of neighboring spokes of \Cref{thm:nicedelta}, namely the ones for $d_0 = d$ and $d_1 = d+1$ for $d = \lfloor\delta q\rfloor$. This restriction, however, is without loss of generality. Indeed, for any values from the domain $\left\{(\gamma, \delta) \mid \delta = \frac{d}{q}, 0\leq d \leq q-1, d\in \mathbb{Z}\right\}$, \Cref{thm:nicedelta} gives values which come from the function $f(\gamma, \delta) = (1-\delta)\left[
\left(1 + \frac{\gamma}{1-\delta}\right)\log_q\frac{q(1-\delta)}{\frac{\gamma}{1-\delta}+1}
-\frac{\gamma}{1-\delta}\cdot\left(\log_{q}\frac{q(1-\delta)-1}{\frac{\gamma}{1-\delta}}\right)
\right]$. This function $f(\gamma, \delta)$ is convex. (see \Cref{appdx:proofOfConvexity} for a formal proof.) Any value given as a convex combination between two non-neighboring spokes can therefore be at least matched (and indeed, thanks to the strict convexity of $f(\cdot,\cdot)$ always be improved) by choosing a different convex combination between neighboring spokes. This justifies the ``restricted" formulation of \cref{thm:outer bound}, which helps in reducing the number of parameters and simplifies calculations.

In order to prove \cref{thm:outer bound} we, again, fix a  specific strategy for the adversary's use of deletions. In particular, the adversary will use $n\alpha\frac{d}{q}$ deletions on the first $n\alpha$ symbols of the transmitted codeword to eliminate all instances of the $d$ least-frequent symbols there. Similarly, he removes all instances of the respective $d+1$ least frequent symbols from the last $n(1-\alpha)$ symbols of the codeword. The resulting string is one out of some $\Sigma_0 ^ {n\alpha(1-\frac{d}{q})} \times \Sigma_1 ^ {n(1-\alpha)(1-\frac{d+1}{q})}$ where $\Sigma_0, \Sigma_1 \subseteq [q]$, $q_0 = |\Sigma_0| = q - d$, $q_1 = |\Sigma_1| = q - d - 1$. This deletion strategy fits within the budgeted number of deletions since $\delta = \alpha \frac{d}{q} + (1-\alpha)\frac{d + 1}{q}$ for $d = \lfloor \delta q \rfloor$ and $\alpha = 1 - \delta q + d$.

Note that while the adversary can convert any codeword of $C$ to a string of such form, the sub-alphabets $\Sigma_0$ and $\Sigma_1$ will likely be different between different codewords of $C$. Let $(\Sigma_0, \Sigma_1)$ be the pair of the most frequently reduced to alphabets and let $C_0$ be the set of codewords of $C$ that, after undergoing the above-described procedure, turn into a string out of $\Sigma_0 ^ {n\alpha(1-\frac{d}{q})} \times \Sigma_1 ^ {n(1-\alpha)(1-\frac{d+1}{q})}$. Note that $\frac{|C|}{{q\choose d}{q\choose d + 1}}\leq |C_0| \leq |C|$. Further, let $D_0$ be the set of codewords in $C_0$ after undergoing the alphabet reduction procedure mentioned above. To give an outer bound of the rate of $C$ it thus suffices to bound from above the size of $C_0$ (or equivalently, $D_0$.)

We bound above the size of $D_0$ by showing that if $|D_0|$ is too large, there will be some received word that can be obtained by exponentially many words in $D_0$ after $n\gamma$ insertions. Similar to \cite{haeupler2018synchronization4}, we utilize the linearity of expectation to derive this. Let us pick a random string $Z = (Z_0, Z_1)$ that consists of $n\alpha(1-\frac{d}{q})(1 + \gamma_0)$ symbols chosen uniformly out of $\Sigma_0$ (referred to by $Z_0$) and
$n(1-\alpha)(1-\frac{d+1}{q})(1+\gamma_1)$ symbols uniformly chosen out of $\Sigma_1$ (referred to by $Z_1$). We have that
$
\alpha(1-\frac{d}{q})\gamma_0
+
(1-\alpha)(1-\frac{d+1}{q}) \gamma_1
 = \gamma $. ($\gamma_0$ and $\gamma_1$ will be determined later.) We calculate the expected number of the members of $D_0$ that are subsequences of such string -- denoted by $X$. In the following, we will often describe members of $D_0$ like $y$ as the concatenation $(y_0, y_1)$ where
 $|y_0| = n_0 = n\alpha(1-\frac{d}{q})$
 and
 $|y_1| = n_1 = n(1-\alpha)(1-\frac{d+1}{q})$.

 \begin{eqnarray}
\mathbb{E}[X
 &=& \sum_{y=(y_0, y_1)\in{D_0}}\Pr\{y\text{ is a subsequence of }Z\}\nonumber\\
 &\geq& \sum_{y=(y_0, y_1)\in{D_0}}\Pr\{y_0\text{ is a subsequence of }Z_0\} \cdot \Pr\{y_1\text{ is a subsequence of }Z_1\} \nonumber\\
&=& \sum_{y=(y_0, y_1)\in{D_0}}\prod_{j=1, 2} \Pr\{y_j\text{ is a subsequence of }Z_j\} \nonumber\\
&=& \sum_{y=(y_0, y_1)\in{D_0}}\prod_{j=1, 2} \sum_{1\le a_1<a_2<\cdots <a_{n_j} \le     n_j(1+\gamma_j)} \frac{1}{|\Sigma_j|^{n_j}}\left(1-\frac{1}{|\Sigma_j|}\right)^{a_{n_j}-{n_j}}
\label{eqn:ExpectationComputationStep1}\\
&=& |D_0|\prod_{j=1, 2}\left(|\Sigma_j|-1\right)^{-n_j}\sum_{l=n_j}^{n_j(1+\gamma_j)} {l \choose n_j} \left(\frac{|\Sigma_j|-1}{|\Sigma_j|}\right)^l\nonumber\\
&\ge& |D_0|\prod_{j=1, 2}\left(|\Sigma_j|-1\right)^{-n_j} {n_j(1+\gamma_j) \choose n_j} \left(\frac{|\Sigma_j|-1}{|\Sigma_j|}\right)^{n_j(1+\gamma_j)}\label{eqn:ExpectationComputationStep2}\\
&=& |D_0| \prod_{j=1, 2}(|\Sigma_j|-1)^{n_j\gamma_j}|\Sigma_j|^{-n_j(1+\gamma_j)}2^{n_j(1+\gamma_j)H\left(\frac{1}{1+\gamma_j}\right)+o(n)}\nonumber\\
&=& |D_0| \prod_{j=1, 2} q^{n_j\left(
\gamma_j \log_{q}(q_j-1)
-(1+\gamma_j)\log_q q_{j}
+(1+\gamma_j)\log_{q} (1+\gamma_j)
-\gamma_j\log_{q} \gamma_j
\right)+o(1)}\nonumber\\
&=& |D_0| \prod_{j=0, 1} q^{n_j\left(
\gamma_j \log_{q}\frac{q_j - 1}{\gamma_j}
-(1+\gamma_j)\log_{q} \frac{q_j}{1+\gamma_j}\right)+o(1)}\nonumber\\
&=& |D_0| q^{\sum_{j=0, 1} n_j\left(
\gamma_j \log_{q}\frac{q_j - 1}{\gamma_j}
-(1+\gamma_j)\log_{q} \frac{q_j}{1+\gamma_j}\right)+o(1)
\label{eqn:ExpectationComputationStep3}
\end{eqnarray}
Step~\eqref{eqn:ExpectationComputationStep1} is obtained by conditioning the probability of $y_j$ being a subsequence of $Z_j$ over the leftmost occurrence of $y_j$ in $Z_j$ indicated by $a_1, a_2, \cdots, a_n$ as indices of $Z_j$ where the leftmost occurrence of $y_j$ is located. In that event, $Z_j[a_i]$ has to be similar to $y_j[i]$ and $y_j[i]$ cannot appear in $Z_j[a_{i-1}+1, a_{i}-1]$. Therefore, the probability of this event is $\left(\frac{1}{q_j}\right)^n_j\left(1-\frac{1}{q_j}\right)^{a_n-n_j}$.
To verify Step~\eqref{eqn:ExpectationComputationStep2}, we show that the summation in previous step takes its largest value when $l=n_j(1+\gamma_j)$ and bound the summation below by that term. To see that ${l \choose n_j} \left(\frac{q_j-1}{q_j}\right)^l$ is maximized for $l=n_j(1+\gamma_j)$ in $n_j \le l \le n_j(1+\gamma_j)$, it suffices to show that the ratio of consecutive terms is larger than one for $l \le n_j(1+\gamma_j)$:
$$\frac{{l \choose n_j} \left(\frac{q_j-1}{q_j}\right)^{l}}{{l-1 \choose n_j} \left(\frac{q_j-1}{q_j}\right)^{l-1}} = \frac{l}{l-n_j} \cdot\frac{q_j-1}{q_j}=\frac{1-\frac{1}{q_j}}{1-\frac{n_j}{l}} \ge 1$$
The last inequality follows from the fact that $l\le n_j(\gamma_j+1)\le n_j q_j \Rightarrow \frac{1}{q_j} < \frac{n_j}{l}$.

Finally, by \eqref{eqn:ExpectationComputationStep3}, there exists some realization of $Z$ to which at least
$$|D_0| q^{\sum_{j=0, 1} n_j\left(
\gamma_j \log_{q}\frac{q_j - 1}{\gamma_j}
-(1+\gamma_j)\log_{q} \frac{q_j}{1+\gamma_j}\right)+o(1)}$$
codewords of $\mathcal{C}$ are subsequences. In order for $C$ to be list-decodable, this quantity needs to be sub-exponential. Therefore,
\begin{eqnarray}
 r_C &=& \frac{\log_q |D_0| + O(1)}{n} \leq
\sum_{j=0, 1} \frac{n_j}{n}\left(
(1+\gamma_j)\log_{q} \frac{q_j}{1+\gamma_j}
-
\gamma_j \log_{q}\frac{q_j - 1}{\gamma_j}
\right)\nonumber\\
&=&
\alpha\left(1-\frac{d}{q}\right) \left(
(1+\gamma_0)\log_{q} \frac{q_0}{1+\gamma_0}
-
\gamma_0 \log_{q}\frac{q_0 - 1}{\gamma_0}
\right)\nonumber\\
&&+
(1-\alpha)\left(1-\frac{d+1}{q}\right)\left(
(1+\gamma_1)\log_{q} \frac{q_1}{1+\gamma_1}
-
\gamma_1 \log_{q}\frac{q_1 - 1}{\gamma_1}
\right)\nonumber\\
&=&
\alpha\left(1-\frac{d}{q}\right) \left(
(1+\gamma_0)\log_{q} \frac{q-d}{1+\gamma_0}
-
\gamma_0 \log_{q}\frac{q-d - 1}{\gamma_0}
\right)\nonumber\\
&&+
(1-\alpha)\left(1-\frac{d+1}{q}\right)\left(
(1+\gamma_1)\log_{q} \frac{q-d-1}{1+\gamma_1}
-
\gamma_1 \log_{q}\frac{q-d - 2}{\gamma_1}
\right)\label{eqn:parametrized-bound}
\end{eqnarray}

Note that \eqref{eqn:parametrized-bound} is an outer bound for the rate for all choices of $\gamma_0, \gamma_1 \geq 0$ where
$\alpha(1-\frac{d}{q})\gamma_0
+
(1-\alpha)(1-\frac{d+1}{q}) \gamma_1
 = \gamma.$

\end{proof}

\begin{theorem}\label{lem:optimal-gamma}
The optimal choice for the value of $\gamma_0$ in \cref{thm:outer bound} satisfies

$$\left(1 + \frac{1}{\gamma_1}\right)\left(1-\frac{1}{q-d-1}\right)= \left(1 + \frac{1}{\gamma_0}\right)\left(1-\frac{1}{q-d}\right).$$

\smallskip
\noindent Together with the equation $\alpha(1-\frac{d}{q})\gamma_0 + (1-\alpha)(1-\frac{d+1}{q}) \gamma_1  = \gamma $, this gives the following explicit expression for $\gamma_0$ in terms of $q$,$\gamma$, $d =\lfloor \delta q \rfloor$, and $\alpha = 1 - \delta q + d$:

$$\gamma_0=\frac{1}{2\alpha (q-d)} \cdot \left(A - \sqrt{B^2 + C}\right)$$

for

\smallskip

$A = 3 \alpha  d^2 q+d^2 q-3 \alpha  d q^2-2 d q^2+4 \alpha  d q+2 d q+\alpha  q^3-2 \alpha  q^2+q^3-2 q^2+\gamma  q+q -\alpha  d^3-2 \alpha  d^2$

\smallskip

$B= \alpha  d^3+2 \alpha  d^2-3 \alpha  d^2 q-d^2 q+3 \alpha  d q^2+2 d q^2-4 \alpha  d q-2 d q-\alpha  q^3+2 \alpha  q^2-q^3+2 q^2-\gamma  q-q$

\smallskip

$C = 4 (\alpha  q-\alpha  d) \left(\gamma  d^2 q-2 \gamma  d q^2+2 \gamma  d q+\gamma  q^3-2 \gamma  q^2\right)$
\end{theorem}
\begin{proof}
To find the optimal value for $\gamma_0$, we find the choice of $\gamma_0$ that minimizes \eqref{eqn:ExpectationComputationStep1}. To this end, we calculate the ratio between the values of \eqref{eqn:ExpectationComputationStep1} when $n\gamma$ insertions are distributed between two parts as $(n_0\gamma_0, n_1\gamma_1)$ and when distributed as $(n_0\gamma_0 + 1, n_1\gamma_1 - 1)$. We then find out the choice of $\gamma_0$ for which this ratio exceeds one. This would indicate the value of $\gamma_0$ for which  \eqref{eqn:ExpectationComputationStep1} is minimized and, hence, the optimal choice of $\gamma_0$.
\begin{eqnarray*}
&&\frac{
{n_0(1+\gamma_0) \choose n_0} \left(\frac{|\Sigma_0|-1}{|\Sigma_0|}\right)^{n_0(1+\gamma_0)}
{n_1(1+\gamma_1) \choose n_1} \left(\frac{|\Sigma_1|-1}{|\Sigma_1|}\right)^{n_1(1+\gamma_1)}
}{
{n_0(1+\gamma_0)+1 \choose n_0} \left(\frac{|\Sigma_0|-1}{|\Sigma_0|}\right)^{n_0(1+\gamma_0)+1}
{n_1(1+\gamma_1)-1 \choose n_1} \left(\frac{|\Sigma_1|-1}{|\Sigma_1|}\right)^{n_1(1+\gamma_1)-1}
}\allowdisplaybreaks\\
&=&\frac{
{n_0(1+\gamma_0) \choose n_0}
{n_1(1+\gamma_1) \choose n_1} \left(\frac{|\Sigma_1|-1}{|\Sigma_1|}\right)
}{
{n_0(1+\gamma_0)+1 \choose n_0} \left(\frac{|\Sigma_0|-1}{|\Sigma_0|}\right)
{n_1(1+\gamma_1)-1 \choose n_1}
}\\
&=&\frac{
{n_0(1+\gamma_0) \choose n_0}
{n_1(1+\gamma_1) \choose n_1}
}{
{n_0(1+\gamma_0)+1 \choose n_0}
{n_1(1+\gamma_1)-1 \choose n_1}
}
\times \frac{|\Sigma_0| \times (|\Sigma_1|-1)}{(|\Sigma_0|-1) \times |\Sigma_1|}
\\
&=&\frac{
\frac{n_1(1+\gamma_1)}{n_1(1+\gamma_1) - n_1}
}{
\frac{n_0(1+\gamma_0)+1} {n_0(1+\gamma_0)+1 - n_0}
}
\times \frac{|\Sigma_0| \times (|\Sigma_1|-1)}{(|\Sigma_0|-1) \times |\Sigma_1|}
\\
&=&\frac{
\frac{n_1(1+\gamma_1)}{n_1\gamma_1}
}{
\frac{n_0(1+\gamma_0)+1} {n_0\gamma_0+1}
}
\times \frac{|\Sigma_0| \times (|\Sigma_1|-1)}{(|\Sigma_0|-1) \times |\Sigma_1|}
\\
&=&\frac{
1 + \frac{1}{\gamma_1}
}{
1+\frac{1}{\gamma_0+1/n_0}
}
\times
\frac{1-\frac{1}{|\Sigma_1|}}{1-\frac{1}{|\Sigma_0|}}
\end{eqnarray*}
Therefore, the optimal choice of $\gamma_0$ would be one for which:
\begin{eqnarray*}
&& \frac{1 + \frac{1}{\gamma_1}
}{
1+\frac{1}{\gamma_0+1/n_0}
}
\times
\frac{1-\frac{1}{|\Sigma_1|}}{1-\frac{1}{|\Sigma_0|}} = 1\\
&\Leftrightarrow&
\left(1 + \frac{1}{\gamma_1}\right)\left(1-\frac{1}{|\Sigma_1|}\right)=
\left(1+\frac{1}{\gamma_0+1/n_0}\right)\left(1-\frac{1}{|\Sigma_0|}\right)
\end{eqnarray*}
Given that families of codes with increasing block lengths $n$ are considered, the term $\frac{1}{n_0} = \frac{1}{n\cdot \alpha(1-d/q)}$ vanishes. Thus, we are looking for a choice of $\gamma_0$ that satisfies
$$
\left(1 + \frac{1}{\gamma_1}\right)\left(1-\frac{1}{|\Sigma_1|}\right)=
\left(1 + \frac{1}{\gamma_0}\right)\left(1-\frac{1}{|\Sigma_0|}\right).$$

Putting this together with the equation $\alpha(1-\frac{d}{q})\gamma_0 + (1-\alpha)(1-\frac{d+1}{q}) \gamma_1  = \gamma $ from \cref{thm:outer bound} and solving the resulting system of equations analytically using computer software, the stated equation for the optimal choice of $\gamma_0$ is derived.
\end{proof}

\newpage
\section{Inner Bound via Analyzing Random Codes}\label{sec:inner_bound}
In this section, we provide an inner bound on the highest rate achievable by list-decodable insertion-deletion codes. We start with a preliminary lemma.
\begin{lemma}[From \cite{levenshtein1974elements}]\label{lem:insertion-ball}
Let $n, n_i$, and $q$ be positive integers and $S\in[q]^{n_i}$. Then, the number of strings that lie inside the insertion ball of radius $n_i$ around $S$ is
$$|\mathcal{B}_i(S, n_i)| = \sum_{i=0}^{n_i}{n+n_i \choose i}(q-1)^i.$$
\end{lemma}

In the following, we give a simple bound on the size of the insertion-deletion ball.
\begin{lemma}\label{lem:insdel-ball}
Let $x\in[q]^n$, $\delta \in \left[0, 1-\frac{1}{q}\right]$ and $\gamma \in [0, (q-1)(1-\delta)]$. The size of the insertion-deletion ball of insertion-radius $\gamma n$ and deletion-radius $\delta n$ around $x$ is no larger than
$$\mathcal{B}(x, \gamma n, \delta n) \leq q^{n\left(H_q(\delta)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- \delta\log_q(q-1)
\right)+o(n)}.$$
\end{lemma}
\begin{proof}

\begin{eqnarray}
\mathcal{B}(x, \gamma n, \delta n) &=& \sum_{x_0 \in \mathcal{B}_d(x, \delta)} |\mathcal{B}_i(x_0, \gamma)|\nonumber\\
&\leq&  {n \choose \delta n} \sum_{i=0}^{\gamma n}{n(1-\delta+\gamma) \choose i}(q-1)^i
\label{eqn:ball1}\\
&\leq& n\gamma {n \choose n\delta} {n(1-\delta+\gamma) \choose n\gamma} (q-1)^{\gamma n}\label{eqn:ball2}\\
&=&q^{n\left(H_q(\delta) - \delta\log_q(q-1)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right) - \gamma\log_q(q-1) + \gamma\log_q(q-1)
\right)+o(n)}\label{eqn:ball3}\\
&=&q^{n\left(H_q(\delta)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- \delta\log_q(q-1)
\right)+o(n)}\nonumber
\end{eqnarray}
Note that \eqref{eqn:ball1} follows from \cref{lem:insertion-ball} and \eqref{eqn:ball2} is true because the term in summation reaches its maximum when $i=n\gamma$. To see this, we test the ratio between the value of the term for two consecutive parameter values $i$ and $i+1$:
$$\frac{{n(1-\delta+\gamma) \choose i+1}(q-1)^{i+1}}{{n(1-\delta+\gamma) \choose i}(q-1)^i} = \frac{n(1-\delta+\gamma)-i}{i+1}(q-1)$$
Note that
$\frac{n(1-\delta+\gamma)-i}{i+1}(q-1)\geq 1 \Leftrightarrow \frac{n(1-\delta+\gamma)-i}{i+1} \geq \frac{1}{q-1} \Leftrightarrow iq+1 \leq n(1-\delta+\gamma)(q-1)
$. This holds for all $i\leq n\gamma$ because:
$n\gamma q+1 \leq n(1-\delta+\gamma)(q-1) \Leftrightarrow n\gamma < n(1-\delta)(q-1)$.
Finally, \eqref{eqn:ball3} follows from the definition of the $q$-qry entropy function
$$H_q(x) = x\log_q(q-1) - x\log_q x - (1-x) \log_q(1-x)$$ and the equation ${n\choose np} = q^{n(H_q(p)-p\log_q(q-1))+o(n)}$.
\end{proof}

Using the bound on the size of the insertion-deletion ball presented above, we give the following inner bound on the highest achievable rate for $(\gamma, \delta)$-list-decodable codes derived by analysis of the list-decodability of random codes.

\begin{theorem}
For any integer $q\geq 2$, $\delta \in \left[0, 1-\frac{1}{q}\right]$ and $\gamma \in [0, q-1]$, a family of random $q$-ary codes with rate
$$0 \leq R < 1-
(1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- H_q\left(\delta\right)
+ \gamma\log_q(q-1)
$$
is list-decodable from $\gamma n$ insertions and $\delta n$ deletions with high probability.
\end{theorem}
\begin{proof}
Take the random codeword $X\in[q]^{n}$ and some string $y\in[q]^{n(1-\delta+\gamma)}$ of length $n'=n(1-\delta+\gamma)$. Using \cref{lem:insdel-ball}, the probability of $X$ being inside the insertion-deletion ball of deletion-radius $\delta'n' = \gamma n$ and insertion-radius $\gamma'n' = \delta n$ of $y$ is
\begin{eqnarray*}
\Pr\{X\in\mathcal{B}(y, \gamma' n', \delta' n')\}
&\leq& \frac{
q^{n'\left(H_q(\delta')
+ (1-\delta'+\gamma')H_q\left(\frac{\gamma'}{1-\delta'+\gamma'}\right)
- \delta'\log_q(q-1)
\right)+o(n)}
}{q^n}\\
&=& \frac{
q^{n(1-\delta+\gamma)\left(H_q(\frac{\gamma}{1-\delta+\gamma})
+ \frac{1}{1-\delta+\gamma}H_q\left(\delta\right)
- \frac{\gamma}{1-\delta+\gamma}\log_q(q-1)
\right)+o(n)}
}{q^n}\\
&=& q^{n\left(H_q(\delta)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- \gamma\log_q(q-1)
 - 1\right)+o(n)}
\end{eqnarray*}
For the random code $C$ with rate $R$ to not be $l$-list decodable for some integer $l$, there has to exists some string $y\in[q]^{n(1-\delta+\gamma)}$ that can be obtained by $l+1$ codewords of $C$ via $\delta n$ deletions and $\gamma n$ insertions, i.e., codewords that lie in $\mathcal{B}(y, \delta n, \gamma n)$. Using the union bound over all $y\in[q]^{n(1-\delta+\gamma)}$, the probability of the existence of such $y$ is at most.
 \begin{eqnarray}
&&q^{n(1-\delta+\gamma)} \left(q^{nR}\right)^{l+1} \left(q^{n\left(H_q(\delta)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- \gamma\log_q(q-1)
 - 1\right)+o(n)}\right)^{l+1}\nonumber\\
&=&q^{n(l+1)
\left(R + H_q(\delta)
+ (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
- \gamma\log_q(q-1)
 - 1  + \frac{1-\delta+\gamma}{l+1}+o_l(1)
\right)
 }\label{eqn:list-dec-prob}
 \end{eqnarray}
 Note that we used the trivial bound ${q^{nR} \choose l+1} \leq \left(q^{nR}\right)^{l+1}$ in the above calculation.
Equation \eqref{eqn:list-dec-prob} implies that as long as
 $$R <  1-
 (1-\delta+\gamma)H_q\left(\frac{\gamma}{1-\delta+\gamma}\right)
 - H_q\left(\delta\right)
+ \gamma\log_q(q-1),
 $$
for an appropriately large $l=O_{\gamma,\delta,q}(1)$, the exponent of \eqref{eqn:list-dec-prob} is negative and, therefore, the family of random codes is $(\gamma, \delta)$-list-decodable with high probability.
\end{proof}

redpajama_set_name: RedPajamaArXiv


Grab one of our Breast Cancer Awareness sweatshirts and show your support for Breast Cancer. Four sayings to choose from, all on our super-comfortable, super-soft hot pink or black heavyweight sweatshirts. All proceeds collected are donated to various Breast Cancer agencies.


text:
Bolo, also known as Ngoya and Kibala, is a Bantu language of Angola that is closely related to Kimbundu.

Name
The only name for the language as a whole, 'Ngoya', was originally pejorative, though it is becoming increasingly accepted. 'Kibala' is the Umbundu name for the central dialect, Ipala. 'Bolo' is a peripheral dialect.

Varieties
The dialects of this language are Ipala, Hebó, Ucela, Mbwĩ, Bolo and Sende.

References

Languages of Angola
Kimbundu languages

redpajama_set_name: RedPajamaWikipedia


text:
The MacFarland Hubbard House: Its History
Home » About Us » The MacFarland Hubbard House: Its History
The MacFarland-Hubbard House was built in 1836 by Charleston builder Norris Stanley Whittaker, on land purchased from Isaac Noyes. It is a landmark property listed in the National Register of Historic Places, and one of only a handful of antebellum houses remaining in the Charleston area.
Whittaker built the house "on spec"—he did not have a definite buyer during the building, but hoped to secure one when the job was complete. He built this house while he was in his mid to late 20s, along with the Rand House next door (a near twin) and the Thayer House on the corner (the current location of the UMWA), all at about the same time. The MacFarland and Rand houses were built from unfired brick made on site, and in keeping with southern construction traditions, the bricks were painted to seal them. (Click any image to view larger)
MacFarland House
Rand House
The first owner of the MacFarland-Hubbard House was Henry Devol MacFarland, a wealthy merchant who purchased the house on December 19, 1836. MacFarland resided here with his wife and two young children until his death in 1845.
Newly discovered census records indicate that MacFarland enslaved at least five individuals. Though the property was not used as a farm or plantation, the lot was at that time much larger than its current size of 3/4 acre, and likely included gardens, a stable, and other outbuildings. The original lot extended across what is now Virginia Street, and nearly 2/3rds of the way to Quarrier Street.
1874 map of Charleston.
The house's second owners were the Ruby family. John C. Ruby II and his wife, Mary Frances Noyes, daughter of wealthy salt-maker and merchant Bradford Noyes, were residing in the house by 1851. Ruby established a grocery business on Kanawha Street in Charleston, and served as mayor from 1875-77.
During the Civil War, when the Union took control of the Kanawha Valley, the Rubys removed to the South. In the fall of 1862 Union troops were pulled from the valley for the campaign against General Lee, just before the Battle of Antietam. As the Confederates recaptured the valley, a round shot from a field cannon was fired into the house (though the house was not the intended target). It is thought to have been fired from what would now be the riverbank of the University of Charleston, just under a mile away as the crow flies. For a time during the war, the house was used as a makeshift hospital for wounded and recovering soldiers. (Read more about the Battle of Charleston at e-WV: The West Virginia Encyclopedia.)
When the Rubys returned at the end of the war, the convalescing soldiers were moved from the house to a tent hospital on the lawn. Following the war, the census listed Ruby, his mother, five children, and three domestic servants residing at the property. Though verification has yet to be found, it is possible that these servants, David, Harriet, and John Jefferson, were enslaved prior to and during the war.
The Rubys sold the house in 1921 to the Crowley family, who undertook substantial renovations. It is likely that this transfer of ownership involved partitioning of the original property into the lot as it exists today, as during this period Ruby formed the Ruby-Sterret Packard car dealership, headquartered in the red brick building situated to the rear of the property currently.
John B. Crowley worked in wholesale and real estate, and underwrote the construction of Charleston's Hotel Kanawha, Holley Hotel, and Capitol Theater. Though the Crowleys lived in the house for only a short period, their alterations to the house effectively brought twentieth century standards of amenity into it. Hardwood floors were laid down over the original heart of pine flooring, the current staircase was installed, the sunroom, porte cochère, and carriage house were added, and other small updates were made.
In 1941 the Crowleys sold the house to the Hubbard family, known in the Charleston area for the Hubbard Grocery Company. John W. Hubbard died the following year, leaving equal shares of the house to his daughter Elizabeth and wife Mary Ashby Hubbard. Elizabeth lived in the house with her stepmother Mary and half-brother Bill, who left for the Navy shortly after the Hubbard women assumed ownership. During their residency the Hubbard family added the rear second floor, creating a new master bedroom, and also extended the kitchen to the southeast exterior wall. Mary, upon her death in 1966, bequeathed her half of the house to Elizabeth.
Having no heirs, Elizabeth left the house and its contents to the First Presbyterian Church of Charleston when she died in 1997.
The Council purchased the house from the Church in 1998, and immediately undertook to renovate and restore it for use.
The House: Its Renovation (Exterior and Carriage House)
The House: Its Renovation (First Floor)
The House: Its Renovation (Second Floor)
Exhibit Main Page

redpajama_set_name: RedPajamaCommonCrawl


text:
Wynette, Texas #3
How does the most famous woman in the world hide in plain sight? The beautiful young widow of the President of the United States thought she was free of the White House, but circumstances have forced her back into the role of First Lady. Not for long, however, because she's made up her mind to escape — if only for a few days — so she can live the life of an ordinary person. All she needs is the perfect disguise . . . and she's just found it.
An entire nation is searching for her, but the First Lady is in the last place anybody would think to look: in the company of a man, an infuriatingly secretive and quietly seductive stranger whose charm, good looks, and sensuous appeal are awakening the forgotten woman within the dignitary. And with two adorable little orphaned girls in need of a family along for the ride, they're heading out across the heartland chasing their own American Dream — on a wild journey of love, adventure, and glorious rebirth.
First Lady: A star-spangled, richly emotional story of self-discovery, celebrity, love, and family.
Reissued with new cover October 2009.
"…another of Phillips's brilliant romantic romps, deftly combining laughter and love with real women's issues and served up with a sophisticated flair." —Library Journal
"…when Phillips wields the pen, you know you're in for a good time. The lady's a sorceress, I tell you." —The Oakland Press
"Leave it to the always inventive Susan Elizabeth Phillips to deliver humor, tenderness, and empathy with a decided twist. No one does it quite like Ms. Phillips!" —Romantic Times
"Even though it's early in the new year, I feel confident in predicting that First Lady will be a nominee for Best Contemporary Romance of 2000. It's that good. You don't want to miss it." —The Romance Reader
RITA Award; Single Title Contemporary Romance, 2001
Top Ten Favorite Book of the Year, Romance Writers of America
Other Books in Wynette, Texas Series


text:
Stamp duty holiday 'to be extended until end of June' as think tank calls for the tax to be scrapped altogether
The stamp duty threshold has been temporarily increased to £500,000 for property sales in England and Northern Ireland.
Wednesday 24 February 2021 09:57, UK
Image: The current stamp duty holiday deadline is 31 March
The stamp duty holiday could be extended by three months, according to a media report.
As part of his Budget plans next week, Chancellor Rishi Sunak will be moving the deadline from 31 March to the end of June, The Times has reported.
The chancellor had been urged to push back the deadline as many people have been left scrambling to complete their transactions before the end date - with the property website Rightmove estimating 100,000 could miss out.
Image: Chancellor Rishi Sunak has been urged to extend the deadline
Under the current rules, announced by the Treasury last year in a bid to fire up the property market, the stamp duty threshold has been temporarily raised from £125,000 to £500,000 for property sales in England and Northern Ireland.
In Scotland and Wales, it was increased to £250,000.
The holiday appears to have had a positive impact on the housing market, with right-leaning think tank the Centre for Policy Studies reporting house sales had increased to their highest level since before the 2007 financial crisis.
Some 129,400 transactions went through in the UK in December, compared with 87,040 in 2014, according to provisional figures from HM Revenue & Customs.
Cost of living: Almost half of working age households 'behind on or struggling with housing costs'
Awaab Ishak: Regulator finds 'significant failings' at Rochdale housing association linked to boy's mould death
England's ageing housing stock poses 'massive health risk' in cost of living crisis
Rightmove also reported the average number of days it took to sell a property fell to 49 in November, compared with 67 a year earlier.
Almost a third of house sales 'fall through' as stamp duty deadline nears
The Centre for Policy Studies is now calling on the government to either permanently increase the threshold on primary residences to £500,000 or abolish it altogether.
The think tank's data analyst Jethro Elsden warned scrapping the stamp duty holiday would be a "sledgehammer blow to the housing market".
A spokesperson for the Treasury has said they cannot speculate on tax ahead of fiscal events.


text:
The RBA Response to Covid Supported Employment
Written by Russell Shor 3 June 2021, 4:00 pm
Australian Unemployment and the RBA's Response During the Covid Pandemic
The Covid-19 Pandemic and Australia's Labour Market.
The RBA's Monetary Policy Response to Support the Economy
The RBA Statement of 1 June 2021
Australian Unemployment and the RBA's Response During the Covid Pandemic
The Reserve Bank of Australia or RBA is Australia's central bank. It is the custodian of the country's monetary policy and aims to contribute to:
The stability of the currency of Australia;
The maintenance of full employment in Australia; and
The economic prosperity and welfare of the people of Australia.
As the central bank decides on and institutes its various policy decision, it will do so in reference to these obligations. It has independence in exercising policy as it sees fit but is accountable to Parliament for its actions. In this article, we focus on unemployment and how the RBA's response during the covid pandemic period contributed to achieving its second mandate.
The Covid-19 Pandemic and Australia's Labour Market.
As the covid pandemic spread globally, regional economies were severely affected as lockdowns took hold and business and consumer confidence levels fell sharply. Prior to this period, Australia's unemployment rate was around the 5.2% mark with a labour participation rate of 65.9%. However, as the global lockdown period progressed, taking its toll on economic activity, the labour statistics deteriorated considerably. By May the labour force participation rate had dropped to 62.6% and unemployment had climbed above 7%.
The RBA's Monetary Policy Response to Support the Economy
The RBA countered the economic shocks caused by the covid pandemic in a number of ways, ensuring a comprehensive and effective response that provided support to jobs, incomes and business:
The RBA adjusted its policy interest rate by lowering the cash rate twice. First to 0.25% in March 2020 and then to 0.1% in November 2020. This aimed for easier borrowing and spending confidence.
Forward guidance was emphasised, and the RBA has stated that the cash rate will only be adjusted when actual inflation falls within the 2-3% target range, which is expected in 2024. This has increased certainty regarding the economic outlook.
The 3-year bond has a targeted yield of 0.1% and the RBA will provide the demand so that this is achieved. Moreover, the central bank is purchasing 5- and 10-year bonds as part of its quantitative easing effort. This helps keep a lower yield across the yield curve, which is supportive of expansion, through easier borrowings and spending confidence across longer times frames.
The RBA also extended favourable term funding to commercial banks at a rate of 0.1%. These borrowings are able to be passed on as loans to business and households. This is regarded as especially important to support the liquidity requirements of small- and medium sized businesses.
Lastly, the central bank ensured a floor under the cash rate by implementing zero interest on Exchange Settlement balances. This in turn put a floor under all rates.
Whilst monetary policy was not Australia' only response to the pandemic, it certainly may be regarded as a strong response and largely successful in terms of supporting Australia's unemployment rate. In its statement dated 1 June 2021 the following paragraph is noteworthy:
"Progress in reducing unemployment has been faster than expected, with the unemployment rate declining to 5.5 per cent in April. Job vacancies are at a high level and a further decline in the unemployment rate to around 5 per cent is expected by the end of this year. There are reports of labour shortages in some parts of the economy."
To conclude this article, consider the line charts of Australia's unemployment rate (top chart) and participation rate (bottom chart) from 1 January 2020 until the present as a testament to the RBA and its policy response to the Covid pandemic.
Russell Shor
Russell Shor joined FXCM in October 2017 as a Senior Market Specialist. He is a certified FMVA® and has an Honours Degree in Economics from the University of South Africa. Russell is a full member of the Society of Technical Analysts in the United Kingdom. With over 20 years of financial markets experience, his analysis is of a high standard and quality.
Nikos Tzabouras 3 hours ago
Global News Currencies
Nikos Tzabouras 3 days ago
Economies Global News Stock Market Currencies
Global News Stock Market
The Fed is Noticeably Behind the Curve
Russell Shor 4 days ago
Currencies Economies
Global News Stock Market Currencies Economies
10-2 Treasury Yield Curve Almost Compels Fed Balance Sheet Runoff
Tweets by FXCM_MarketData
Popular Insights
What Is The Best Forex Trading Platform?
Determining the best forex platform is largely subjective. Trading Station, MetaTrader 4, NinjaTrader and ZuluTrader are four of the forex industry leaders in market connectivity.
Forex Trading Tools and Strategies Forex Terms
What Is The Difference Between Trading And Investing?
Although similar in objective, trading and investing are unique disciplines. Duration, frequency and mechanics are key differences separating the approaches.
Beginner Trading
10 Largest Companies In Australia By Market Capitalisation
The Australian Securities Exchange (ASX) is one of the 10 largest global securities exchanges by value, with a total market capitalisation of about A$2 trillion. It is also the largest market for interest rate derivatives in Asia and among the top five exchanges globally for raising capital. The ASX, which is based in Sydney, was the first major financial market open every day. The Australian Stock Exchange was formed on the 1st of April 1987, combining the country's six independent state-based stock exchanges. Each of those exchanges dated back to the 1800s, although stock trading in Australia can be traced…
12 Of The Best Forex Trading Strategies
Familiarity with the wide variety of forex trading strategies may help traders adapt and improve their success rates in ever-changing market conditions.
Beginner Trading Forex Strategies
Introduction To Futures Trading
A futures trading contract is an agreement between a buyer and seller to trade an underlying asset at an agreed upon price on a specified date.
The Best Forex Indicators For Currency Traders
Achieving success in the foreign exchange (forex) marketplace can be challenging. Nonetheless, traders from around the globe, both experienced and novice, attempt to do exactly that on a daily basis. Given the above-average failure rate of new entrants to the market, one has to wonder how long-run profitability may be attained via forex trading. Among the many ways that forex participants approach the market is through the application of technical analysis. By definition, technical analysis is the study of past and present price action for the accurate prediction of future market behaviour. The premier tools for the practice of technical…
Forex Trading Tools and Strategies
The Most Popular Cryptocurrency Terms And Phrases
Due diligence is important when looking into any asset class. However, doing one's homework may be even more important when it comes to digital currency, as this asset class has been around for far less time than more traditional assets (like stocks and bonds) and comes with substantial uncertainty. Conducting the proper research on cryptocurrencies may require a would-be investor to explore many areas. One area in particular that could prove helpful is simply learning the basic industry terminology. Certain lingo is highly unique to digital currency, making it unlikely that traders would have picked it up when studying other…
Top 5 Cryptocurrencies Traders Should Know
Bitcoin (BTC), Ethereum (ETH), Litecoin (LTC), Bitcoin Cash (BTH) and Ripple (XRP) are leading cryptocurrency products. Each provides volatility and opportunity to traders. Learn more about them at FXCM.
What Are The Pros And Cons Of Forex Trading?
Forex trading is challenging and can present adverse conditions, but it also offers traders access to a large, liquid market with opportunities for gains.
Beginner Trading Forex Terms


text:
Category: Obamacare
In Congress: tax deduction for out-of-pocket medical expenses.
In terms of floor activity, the House of Representatives is scheduled to day, with votes expected on 19 bills that will be considered under suspension of the rules. The suspension package includes legislation reported out of the Foreign Affairs, Veterans Affairs, Natural Resources, and the Energy and Commerce Committees.
On Tuesday, members will take up three additional bills under suspension of the rules, including H.R. 3590, the Halt Tax Increases on the Middle Class and Seniors Act, legislation that would roll back changes scheduled to take place in 2017 under the Affordable Care Act to the tax deduction for out-of-pocket medical expenses. Under current law, taxpayers can deduct medical expenses which exceed 7.5 percent of their adjusted gross income for an individual year. Under the Affordable Care Act, this threshold is scheduled to increase to 10 percent of AGI in 2017. H.R. 3590 would amend the Internal Revenue Code to preserve the threshold at 7.5 percent of AGI.
Posted on September 12, 2016 Categories Affordable Care Act, Medical Access, Medical tax expense, Obamacare, Uncategorized, US CongressTags 114th Congress, appropriations and budget matters, Congress, taxesLeave a comment on In Congress: tax deduction for out-of-pocket medical expenses.
House To Devise Obamacare Replacement
Republican leaders of three House committees will collaborate to develop an alternative to the Affordable Care Act, as a vote on the party's latest bill to repeal the law is anticipated next week.
Ways and Means Committee Chairman Paul Ryan, R-Wis.; Energy and Commerce Committee Chairman Fred Upton, R-Mich.; and Education and the Workforce Committee Chairman John Kline, R-Minn., will serve on a working group to replace the ACA with a "patient-centered" program, according to a joint statement.
"This law is fundamentally flawed: It takes power away from the patient and hands it to bureaucrats," the lawmakers said in the statement. "Instead of making people's health care decisions easier, in many cases it makes those decisions for them."
On Tuesday, Rep. Marsha Blackburn, R-Tenn., said that she reintroduced The Health Care Choice Act, which never made it out of the House last year, to do away with the government-funded health care marketplace in favor of allowing people to shop for insurance across state lines.
The move marked at least the third time in 2015 that Republican legislators have introduced in the House a bill that would fully repeal the ACA. The bill is expected to be voted on next week.
The new working group will also develop a contingency plan in case the U.S. Supreme Court decides to invalidate subsidies under the ACA in King v. Burwell, according to the lawmakers' statement.
The high court is set to determine in the case whether the federal government is allowed to provide subsidies in the nearly two dozen states that have opted not to expand Medicare coverage. If the Supreme Court rules against the federal government and nixes that critical aspect of the law, it could call into question the individual mandate, which requires people to get covered or face a penalty, as well as see employers freed from paying a penalty in states currently receiving subsidies — calling the whole law into question.
While Republican lawmakers wait for a ruling in that case, which is set for oral arguments in March, they continue to introduce legislation to free employers from the supposed burden caused by the provision requiring those with more than 50 full-time workers to provide insurance or face a penalty.
The new working group's contingency plan if the Supreme Court rules against the government in King v. Burwell would be consistent with its eventual complete plan to replace the ACA, the lawmakers said.
The health care expansion law has been under attack from Republican lawmakers since it first was signed into law in 2010, but attempts at a full repeal have thus far failed to garner any real support.
Posted on February 2, 2015 Categories congress, duane morris government strategies, Healthcare Policy, ObamacareTags 114th Congress, Healthcare Law, Healthcare policy, ObamacareLeave a comment on House To Devise Obamacare Replacement


Option 2: SEP2000 UPS with a BB SEP 72-A3 Battery pack giving 16 minutes autonomy at full load.
Option 3: SEP2000 UPS with a BB SEP 72-M1 battery pack giving 27 minutes autonomy at full load.
Option 4: SEP2000 UPS with 2 x BB SEP 72-B1 battery packs giving 55 minutes autonomy at full load.


Over the past month I've left my job and home in Los Angeles, spent good, quality, relaxing time with family in Mississippi and now I'm preparing to move to Austin. (In 1 week?!?!) As usual I've shared bits and pieces of this journey with you through Chic Little Poor Girl. Stories and updates accompany the occasional instagram or outfit post. But no move or transition is completely easy/glamorous. Like most bloggers, I am guilty of not really showing the messy, the unknown, the difficult. Because this is a blog about style, why would I share those dirty details? We all deal with lots of negativity in our day to day, so I try to keep things light. That being said, my life is far from summed up by the 2 or 3 outfit posts I share each week. And I think it may be important for me to say that from time to time.
I recently listened to a PodCast about the "Blog Mask." (The persona or image created by a blog.) The discussion reminded me how important it is to remember that what we see on a blog is just a tiny slice of what is actually going on. It's easy to forget, especially while scrolling through glowing photos of perfect homes and flawless outfits. What we don't see and therefore don't think about is what happens right before or right after these photographs are taken. The work/preparation that goes into staging interior shots, and the chaos involved. For example, when I shot this outfit, what you can't see is our puppy, SallieAnne, pooping off camera (true) or her running off and me yelling at her to return. Normal stuff. Boring stuff. Unimpressive stuff. But on this blog, I like to share positive stuff and stuff that inspires (hopefully). That being said, I am going to make an effort to be more "real" with y'all and to occasionally share those less glamorous details.
I'm wearing: DIY Denim shorts that I discovered at a local thrift shop. Classic Calvin Klein high waisted goodness. They were full length jeans upon purchase but I quickly took my scissors to them. When cutting denim I'm always nervous I'll cut them too short and ruin them. So I tend to air on the long side when making the first incision. Once I trimmed these shorts they were still long enough for me to roll up, and I like that. So for now, they will remain my "rolled up" denim cut offs.