text:
\ifappendix
\section{Structural Rounding Proofs}\label{appendix-structural-rounding-proofs}

Here we present the missing proofs from Section~\ref{sec:structural-rounding}.

\subsection{General Framework}

\begin{proof}[Proof of Theorem~\ref{thm:general-edit-sr}]
We write $\opt(G)$ for $\optsol{\Pi}{G}$.
Let $G$ be a graph that is $(\delta \cdot \opt(G))$-close to the class~$\mCp$.
By Definition~\ref{definition:bicriteria-approx}, the polynomial-time
$(\alpha,\beta)$-approximation algorithm finds
edit operations $\psi_1, \psi_2, \dots, \psi_k$
where $k \leq \alpha \delta \cdot \opt(G)$
such that $G' = \kPsieditsG \in \mC_{\beta \lambda}$.

\footnote{We assume that $C_i \subseteq C_j$ for $i \leq j$,
  or equivalently, that $\rho(\lambda)$ is monotonically increasing in~$\lambda$.}

Let $\rho = \rho(\beta \lambda)$ be the approximation factor we can attain
on the graph $G' \in \mC_{\beta \lambda}$.

First we prove the case when $\Pi$ is a minimization problem.
Because $\Pi$ has a $\rho$-approximation in $\mC_{\beta \lambda}$
(where $\rho > 1$), we can obtain a solution $S'$ with cost at most
$\rho \cdot \opt(G')$ in polynomial time.
Applying structural lifting (Definition~\ref{definition:struct-lift-c-psi}), we can use $S'$ to obtain a solution
$S$ for $G$ with $\cost(S) \leq \cost(S') + c k \leq \cost(S') + c \alpha \delta \cdot \opt(G)$ in polynomial time.
Because $\Pi$ is stable under $\psi$ with constant $c'$,
\begin{align*}
\opt(G') &\leq \opt(G) + c' k
\leq \opt(G) + c' \alpha \delta \cdot \opt(G)
= (1 + c' \alpha \delta) \opt(G),
\end{align*}
and we have
\begin{align*}
\cost(S) &\leq \rho \cdot \opt(G') + c \alpha \delta \cdot \opt(G)\\
&\leq \rho (1 + c' \alpha \delta) \opt(G) + c \alpha \delta \cdot \opt(G)\\
&= (\rho + \rho c' \alpha \delta + c \alpha \delta) \opt(G),
\end{align*}
proving that we have a polynomial time $(\rho + (c + c' \rho) \alpha \delta)$-approximation algorithm as required.

Next we prove the case when $\Pi$ is a maximization problem.
Because $\Pi$ has a $\rho$-approximation in $\mC$ (where $\rho < 1$),
we can obtain a solution $S'$ with cost at least
$\rho \cdot \opt(G')$ in polynomial time.
Applying structural lifting (Definition~\ref{definition:struct-lift-c-psi}), we can use $S'$ to obtain a solution
$S$ for $G$ with $\cost(S) \geq \cost(S') - c k \geq \cost(S') - c \alpha \delta \cdot \opt(G)$ in polynomial time.
Because $\Pi$ is stable under $\psi$ with constant~$c'$,
\begin{align*}
\opt(G') &\geq \opt(G) - c' k
\geq \opt(G) - c' \alpha \delta \cdot \opt(G)
= (1 - c' \alpha \delta) \opt(G),
\end{align*}
and we have
\begin{align*}
\cost(S) &\geq \rho \cdot \opt(G') - c \alpha \delta \cdot \opt(G) \\
&\geq \rho (1 - c' \alpha \delta) \opt(G) - c \alpha \delta \cdot \opt(G) \\
&= (\rho - (c + c' \rho) \alpha \delta) \opt(G),
\end{align*}
proving that we have a polynomial-time $(\rho - (c + c'\rho) \alpha \delta)$-approximation algorithm as required.
Note that this approximation is meaningful only when $\rho > (c + c'\rho) \alpha \delta$.
\end{proof}

\subsection{Vertex Deletion}

\begin{lemma}\label{lemma:IS-stable}
  \ISfull is stable under vertex deletion with constant $c'=1$.
\end{lemma}

\begin{proof}
  Given a graph $G$ and any set $X \subseteq V(G)$ with $|X| \leq \gamma$, let $G' = G[V\setminus X]$.
  For any independent set $Y \subset V(G)$, $Y' = Y\setminus X$ is also an independent set in $G'$ with size $|Y'| \geq |Y|-|X|$, which is bounded below by $|Y| - \gamma$.
  In particular, for $Y$ optimal in $G$ we have
  $|Y'| \geq \opt(G) - \gamma$, and so $\opt(G') \geq \opt(G) - \gamma$.
\end{proof}

\begin{lemma}\label{lemma:IS-stable-lift}
  \ISfull can be structurally lifted with respect to vertex deletion with constant $c=0$.
\end{lemma}

\begin{proof}
  An independent set in $G' = G \setminus X$ is also an independent set in~$G$.
  Thus, a solution $S'$ for $G'$ yields a solution $S$ for $G$ such that $\cost_\IS(S') = \cost_\IS(S)$.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:vertex-edits-approx}]\label{cor:appendix-is-vertex-edit-approximation}
    For graphs $(\delta \cdot \opt(G))$-close to a graph class $\mC_\lambda$ via vertex deletions, \ISfull has the following approximations.  For degeneracy $\Tr$, \IS has a $(1 - 4 \delta)/(4\Tr+1)$-approximation, for treewidth~$\Tw$ such that $w\sqrt{\log w} = O(\log n)$, \IS has a $(1 - O(\delta \log^{1.5} n))$-approximation, and for planar-$H$-minor-free, \IS has a $(1 - c_H \delta)$-approximation.
\end{corollary}

\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with $c'=1$ (Lemma~\ref{lemma:IS-stable})
  and structural lifting with $c=0$ (Lemma~\ref{lemma:IS-stable-lift}).
  The independent-set approximation algorithm and the
  editing approximation algorithm depend on the class~$\mC_\lambda$.

  For degeneracy $\Tr$, we use our $(4,4)$-approximate editing algorithm
  (Section~\ref{section:positive_degeneracy_LP_vertex})
  and a simple $1/(\Tr+1)$-approximation algorithm for independent set:
  the $\Tr$-degeneracy ordering on the vertices of a graph gives a canonical
  $(\Tr+1)$-coloring, and the pigeonhole principle guarantees an independent
  set of size at least $|V|/(\Tr+1)$, which is at least $1/(\Tr+1)$ times the
  maximum independent set.
  Thus $\alpha=\beta=4$ and $\rho(\beta \Tr) = 1/(\beta \Tr + 1)$,
  resulting in an approximation factor of $(1-4 \delta)/(4 \Tr+1)$.

  For treewidth $\Tw$ such that $w\sqrt{\log w} = O(\log n)$, we use our
  $(O(\log^{1.5} n), O(\sqrt{\log \Tw}))$-approximate editing algorithm
  (Section~\ref{section:positive_treewidth}) and an exact algorithm for
  independent set \cite{bodlaender1988dynamic,alber01improved} given a tree decomposition of width $O(\log n)$ of the edited graph.
  Thus $\alpha=O(\log^{1.5} n)$ and $\rho = 1$,
  resulting in an approximation factor of $1 - O(\log^{1.5} n) \delta$.

  For planar-$H$-minor-free, we use Fomin's $c_H$-approximate editing algorithm
  \cite{fomin2012planar} and the same exact algorithm for \IS in bounded treewidth
  (as any planar-$H$-minor-free graph has bounded treewidth \cite{Chekuri-Chuzhoy-2016}).
  Thus $\alpha=c_H$ and $\rho = 1$,
  resulting in an approximation factor of $1 - c_H \delta$.
\end{proof}

\begin{lemma}\label{lemma:VD-hereditary}
The problems \VCfull, \FVSfull, \MMMfull, and \CNfull are hereditary (closed under vertex deletion).
\end{lemma}

\begin{proof}
Let $G$ be a graph, and $G' = G\setminus X$ where $X \subseteq V(G)$.
Any vertex cover in $G$ remains
a cover in $G'$ because $E(G') \subseteq E(G)$, so \VC is hereditary.

Let $S$ bs a feedback vertex set in $G$ and $S' = S \setminus X$.
For \FVS, we observe that removing vertices can only decrease the number of cycles in the graph.
Deleting a vertex in $S$ breaks
all cycles it is a part of and, thus, the cycles no longer need to be covered by a vertex in the feedback vertex set of $G'$.
Deleting a vertex not in $S$ can only decrease the
number of cycles, and, thus, all cycles in $G'$ are still covered by $S'$.
Hence, \FVS is hereditary.

For \MMM, deleting vertices with adjacent edges not in the matching only decreases the number of edges; thus, the original matching
is a still a matching in the edited graph. Deleting vertices adjacent to an edge in the matching means that at most one edge in the matching
per deleted vertex is deleted. For each edge in the matching with one of its two endpoints deleted, at most one additional edge (an edge adjacent
to its other endpoint) needs to be added to maintain the maximal matching. Thus, the size of the maximal matching does not increase
and \MMM is hereditary.

\CN is trivially hereditary because deleting vertices can only decrease the number of colors necessary  to color the graph.
\end{proof}

\begin{lemma}\label{lemma:VD-sr}
The problems \VCfull, \FVSfull, \MMMfull, and \CNfull can be structurally lifted with respect to vertex
deletion with constant $c = 1$.
\end{lemma}

\begin{proof}
    Let $G$ be a graph, and $G' = G\setminus X$ where $X \subseteq V(G)$.
    Let $S'$ be a solution to optimization problem $\Pi$ on $G'$. We will
    show that $S \subseteq S' \cup X$ is a valid solution to $\Pi$ on $G$ for each $\Pi$ listed in the Lemma.

    Given a solution $S'$ to \VC for the graph $G'$, the only edges not covered by $S'$ in $G'$ are edges
    between $X$ and $G'$ and between two vertices in $X$. Both sets of such edges are covered by $X$. Thus,
    $S = S' \cup X$ is a valid cover for $G$.

    Given a solution $S'$ to \FVS for the graph $G'$, the only cycles not covered by $S'$ in $G'$ are
    cycles that include a vertex in $X$. Thus, $S = S' \cup X$ is a valid feedback vertex set for $G$ since $X$ covers
    all newly introduced cycles in $G$.

    Given a solution $S'$ to \MMM for the graph $G'$, the only edges not in the matching and not adjacent to
    edges in the matching are edges between $X$ and $G'$ and edges between two vertices in $X$. Thus, any additional
    edges added to the maximal matching will come from $X$, and $S \subseteq S' \cup X$ (by picking edges to add to the maximal matching
    greedily for example) is a valid solution.

    Given a solution $S'$ to \CN for the graph $G'$, the only vertices that could violate the coloring of the
    graph $G'$ are vertices in $X$. Making each vertex in $X$ a different color from each other as well as the colors in
    $G'$ creates a valid coloring of $G$.
    Thus, $S = S' \cup X$ is a valid coloring.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:vertex-edits-approx}]
  The problems \VCfull, and \FVSfull have
  $(1 + O(\delta \log^{1.5} n))$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to treewidth~$w$ via vertex deletions where $w\sqrt{\log w} = O(\log n)$;
  and $(1 + c_H \delta)$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to planar-$H$-minor-free via vertex deletions.
\end{corollary}

\begin{proof}

  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lemma:VD-hereditary})
  and structural lifting with constant $c=1$ (Lemma~\ref{lemma:VD-sr}).

  For treewidth $\Tw$, we use our
  $(O(\log^{1.5} n), O(\sqrt{\log \Tw}))$-approximate editing algorithm
  (Section~\ref{section:positive_treewidth}) and an exact polynomial-time algorithm for
  the problem of interest \cite{bodlaender1988dynamic,alber01improved,cygan2011solving} given the tree-decomposition of width $O(w\sqrt{\log w})$ of the edited graph.
  Thus $\alpha=O(\log^{1.5} n)$ and $c = 1$,
  resulting in an approximation factor of $1 + O(\log^{1.5} n) \delta$.
  Note that since the edited graph has treewidth $O(w\sqrt{\log w}) = O(\log n)$, the exact algorithm runs in polynomial-time.

  For planar-$H$-minor-free graphs, we use Fomin's $c_H$-approximate editing algorithm
  \cite{fomin2012planar} and the same exact algorithm for bounded treewidth
  (as any planar-$H$-minor-free graph has bounded treewidth \cite{Chekuri-Chuzhoy-2016}).
  Thus $\alpha=c_H$ and $c = 1$,
  resulting in an approximation factor of $1 + c_H \delta$.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:vertex-edits-approx}]
  The problems \MMMfull, and \CNfull have
  $(1 + O(\delta \log^{1.5} n))$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to treewidth~$w$ via vertex deletions where $w\log^{1.5} w = O(\log n)$;
  and $(1 + c_H \delta)$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to planar-$H$-minor-free via vertex deletions.
\end{corollary}

\begin{proof}

  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lemma:VD-hereditary})
  and structural lifting with constant $c=1$ (Lemma~\ref{lemma:VD-sr}).

  For treewidth $\Tw$, we use our
  $(O(\log^{1.5} n), O(\sqrt{\log \Tw}))$-approximate editing algorithm
  (Section~\ref{section:positive_treewidth}) and an exact algorithm for
  the problem of interest \cite{bodlaender1988dynamic} given a tree-decomposition of width $O(w\sqrt{\log w})$ of the edited graph.
  Thus $\alpha=O(\log^{1.5} n)$ and $c = 1$,
  resulting in an approximation factor of $1 + O(\log^{1.5} n) \delta$.
  Note that since the edited graph has treewidth $O(w\log^{1.5} w) = O(\log n)$, the exact algorithm runs in polynomial-time.

  For planar-$H$-minor-free graphs, we use Fomin's $c_H$-approximate editing algorithm
  \cite{fomin2012planar} and the same exact algorithm for bounded treewidth
  (as any planar-$H$-minor-free graph has bounded treewidth \cite{Chekuri-Chuzhoy-2016}).
  Thus $\alpha=c_H$ and $c = 1$,
  resulting in an approximation factor of $1 + c_H \delta$.
\end{proof}

\subsection{Vertex Deletion for Annotated Problems ($\text{Vertex}^*$ Deletion)}\label{sec:annotated-vertex-deletion}
In this section, we show that several important variants of {\em annotated} \DSfull (\ALDS) (which include their non-annotated variants as special cases) are closed under a relaxed version of vertex deletion, denoted by $\text{vertex}^*$ deletion, which is sufficient to apply the  structural rounding framework. Given an instance of \ALDSfull with input graph $G=(V,E)$ and a subset of vertices $B$, the resulting \ALDS instance $(G', B')$ after deleting the set $X\subset V$ is defined as follows: $G' = (V\setminus X, E[V\setminus X])$ and $B' = B\setminus N_{\ell}[X]$ where $N_{\ell}[X]$ denotes the set of all vertices at distance at most $\ell$ from $X$ in $G$.

\begin{lemma}\label{lem:annotated-dom-set-stable}
For $\ell\geq 1$, \ALDSfull is stable under $\text{vertex}^*$ deletion with $c' =0$.
\end{lemma}
\begin{proof}
Note that \ALDSfull with $B = V$ reduces to \LDSfull and in particular \LDSfull is stable under $\text{vertex}^*$ deletion with constant $c' = 0$.

Let $(G', B')$ denote the \ALDS instance after performing $\text{vertex}^*$ deletion with edit set $X$; $G' = (V\setminus X, E[V\setminus X])$ and $B' = B\setminus N_{\ell}[X]$ where $N_{\ell}[X]$ denotes the set of all vertices at distance at most $\ell$ from $X$ in $G$.
Moreover, let $\opt(G, B)$ denote an optimal solution of $\ALDS(G, B)$. We show that $\opt(G,B)\setminus X$ is a feasible solution of $\ALDS(G', B')$.
Since $X$ $\ell$-dominates $N_{\ell}[X]$, the set $B\setminus N_{\ell}[X]$ is $\ell$-dominated by $\opt(G,S) \setminus X$; hence, $\opt(G,S)\setminus X$ is a feasible solution of $\ALDS(G', S')$. Thus $|\opt(G',S')| \leq |\opt(G,S)\setminus X| \leq |\opt(G,S)|$.
\end{proof}

\begin{lemma}\label{lem:annotated-dom-set-lifting}
For $\ell\geq 1$, \ALDSfull can be structurally lifted with respect to $\text{vertex}^*$ deletion with constant $c = 1$.
\end{lemma}
\begin{proof}
Note that \ALDSfull with $B = V$ reduces to \LDSfull and in particular \LDSfull can be structurally lifted with respect to $\text{vertex}^*$ deletion with constant $c=1$.

Let $(G', B') = ((V\setminus X, E[V\setminus X]), B\setminus N_{\ell}[X])$ denote the \ALDS instance after performing $\text{vertex}^*$ deletion with edit set $X$ on $\ALDS(G,B)$ and let $\opt(G',B')$ denote an optimal solution of $\ALDS(G', B')$ instance. Since the set $X$ $\ell$-dominates $N_{\ell}[X]$, $\opt(G',B')\cup X$ $\ell$-dominates $B' \cup N_{\ell}[X] =B$. Hence, $|\opt(G,B)| \leq |\opt(G',B')| + |X|$.
\end{proof}

\begin{corollary}\label{cor:annotated-dom-set-vertex-degen}
\ADSfull has an $O(\Tr+\delta)$-approximation for graphs $(\delta\cdot \opt(G))$-close to degeneracy $\Tr$ via vertex deletion.
\end{corollary}
\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lem:annotated-dom-set-stable})
  and structural lifting with constant $c=1$ (Lemma~\ref{lem:annotated-dom-set-lifting}).

  We use a $(O(1), O(1))$-approximate editing algorithm (Section~\ref{section:positive_degeneracy_localratio}/~\ref{section:positive_degeneracy_lp}) and $O(\Tr)$-approximation algorithm for the problem of interest~\cite{bansal2017tight} in $\Tr$-degenerate graphs. Note that although the algorithm of~\cite{bansal2017tight} is for \DSfull, it can easily be modified to work for the annotated variant. Thus, $\alpha = O(1)$ and $c=1$, resulting in an $O(r+\delta)$-approximation algorithm.
\end{proof}

\begin{corollary}\label{cor:annotated-dom-set-vertex-treewidth}
\ADSfull has an $O(1 + O(\delta \log^{1.5} n))$-approximation for graphs $(\delta\cdot \opt(G))$-close to treewidth $\Tw$ via vertex deletion where $w\sqrt{\log w} = O(\log_{\ell} n)$.
\end{corollary}
\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lem:annotated-dom-set-stable})
  and structural lifting with constant $c=1$ (Lemma~\ref{lem:annotated-dom-set-lifting}).

  We use our $(O(\log^{1.5} n), O(\sqrt{\log \Tw}))$-approximate editing algorithm
  (Section~\ref{section:positive_treewidth}) and an exact polynomial-time algorithm for
  the problem of interest \cite{borradaile_et_al:LIPIcs:2017:6919} given the tree-decomposition of width $O(w\sqrt{\log w})$ of the edited graph. Note that the algorithm of~\cite{borradaile_et_al:LIPIcs:2017:6919} is presented for \LDS; however, by slightly modifying the dynamic programming approach it works for the annotated version as well.
  Thus $\alpha=O(\log^{1.5} n)$ and $c = 1$,
  resulting in an approximation factor of $(1 + O(\log^{1.5} n) \delta)$.
  Moreover, since the edited graph has treewidth $O(w\sqrt{\log w}) = O(\log n)$, the exact algorithm runs in polynomial-time.
\end{proof}

\paragraph{Smarter $\text{Vertex}^*$ Deletion.}
The idea of applying edit operations on annotated problems can also be used for non-annotated problems.
More precisely,  for several optimization problems that fail to satisfy the required conditions of the standard structural rounding under vertex deletion, we can still apply our structural rounding framework with a more careful choice of the subproblem that we need to solve on the edited graph. An exemplary problem in this category is \CDSfull (\CDS). Note that \CDSfull is not stable under vertex deletion and the standard structural rounding framework fails to work for this problem. Besides the stability issue, it is also non-trivial how to handle the connectivity constraint under vertex or edge deletions.
However, in what follows we show that if we instead solve a {\em slightly different problem} (i.e. annotated variant of \CDSfull) on the edited graph, then we can guarantee an improved approximation factor for \CDS on the graphs close to a structural class.

Let $G=(V,E)$ be an input graph that is $(\delta\cdot\opt(G))$-close to the class $\mC$ and let $X\subset V$ be a set of vertices so that $G\setminus X \in \mC$.
For a subset of vertices $X$, $\neighb_G(X)$ is defined to be the set of all neighbors of $X$ excluding the set $X$ itself; $\neighb_{G}(X) := \set{u \;|\; uv\in E(G), v\in X \text{ and } u\notin X}$\footnote{We drop the $G$ in $\neighb_G$ when it is clear from the context.}.
Let $G'= G[V\setminus X]$ be the resulting graph after removing the edit set $X$. The problem that we have to solve on $G'$ is an {\em annotated} variant of \CDS which is defined as follows:

\begin{problem}{\ACDSfull}
\Input & An undirected graph $G = (V, E)$, a subset of vertices $B\subset V$ and $\ell$ vertex-disjoint cliques $K_1 = (V_1, E_1), \cdots, K_\ell = (V_{\ell},E_\ell)$ where for each $i$, $V_i\subset V$.\\
\Prob & Find a minimum size set of vertices $S \subseteq V$ s.t. $S$ dominates all vertices in $B$ and $S$ induces a connected subgraph in $G\cup (\bigcup_{i\in [\ell]} K_i)$.
\end{problem}

To specify the instance of \ACDSfull that we need to solve on the edited graph $G'$, we construct an auxiliary graph $\bar{G} = (\neighb_G(X), \bar{E})$ as follows: $uv\in \bar{E}$ if there exists a $uv$-path in $G$ whose intermediate vertices are all in $X$.

First, we show that \CDS is stable under $\text{vertex}^*$ deletion with constant $c'=0$: the size of an optimal solution of $\ACDS(G', B', K_1,\cdots, K_\ell)$ is not more than the size of an optimal solution of $\CDS(G)$ where $\set{K_1,\cdots, K_{\ell}}$ are the connected components of $\bar{G}$. Note that due to the transitivity of connectivity for each $i\in [\ell]$, $K_i$ is a clique.

\begin{lemma}\label{lem:cds-stable}
\CDSfull is stable under $\text{vertex}^*$ deletion with $c' =0$.
\end{lemma}
\begin{proof}
Let $\opt$ be an optimal solution of $\CDS(G)$. Here, we show that $\opt\setminus X$ is a feasible solution of $\ACDS(G' = G[V\setminus X], B' = V\setminus \neighb_G(X), K_1, \cdots, K_\ell)$ where $K_1, \cdots, K_\ell$ are connected the components of $\bar{G}$ as constructed above. This in particular implies that
\[\opt(G', B', K_1, \cdots, K_\ell) \leq |\opt\setminus X| \leq |\opt| = \opt(G).\]

Since $\opt$ dominates $V$, it is straightforward to verify that $\opt\setminus X$ dominates $B'$ in $G'$. Next, we show that $\opt\setminus X$ is connected in $G'$ when for each $i$, all edges between the vertices of $K_i$ are added to $G'$. Suppose that there exists a pair of vertices $u,v \in \opt\setminus X$  that are not connected in $G'$. However, since $\opt$ is connected, there exists a $uv$-path $P_{uv}$ in $\opt$.
If $P_{uv}$ does not contain any vertices in $X$, then $P_{uv}$ is contained in $\opt\setminus X$ as well and it is a contradiction.
Now consider all occurrences of the vertices of $X$ in $P_{uv}$. We show that each of them can be replaced by an edge in one of the $K_i$s: for each subpath $v_0, x_1, \cdots, x_{q}, v_1$ of $P_{uv}$ where $x_i\in X$ for all $i\in [q]$ and $v_0,v_1\in \neighb_G(X)$, $v_0v_1$ belongs to the same connected component of $\bar{G}$ . Hence, given $P_{uv}$, we can construct a path $P'_{uv}$ in $G'\cup (\bigcup_{i\in [\ell]} K_i)$. Thus, $\opt\setminus X$ is a feasible solution of $\ACDS(G', B', K_1, \cdots, K_\ell)$.
\end{proof}

Next, we show that a solution of the \ACDSfull  instance we solve on the edited graph can be structurally lifted to a solution for \CDSfull on the original graph with constant $c=3$.
\begin{lemma}\label{lem:cds-lifting}
\CDSfull can be structurally lifted under $\text{vertex}^*$ deletion with constant $c = 3$.
\end{lemma}
\begin{proof}
Let $\opt$ be an optimal solution of $\ACDS(G' = G[V\setminus X], B' = V\setminus \neighb_G(X), K_1, \cdots, K_\ell)$ where $K_1, \cdots, K_\ell$ are the connected components of $\bar{G}$ as constructed above.
Here, we show that $\opt\cup X \cup Y$ is a feasible solution of $\CDS(G)$ where $Y$ is a subset of $V\setminus X$ such that $|Y| \leq 2|X|$.
First, it is easy to see that since $X$ dominates $\neighb_G(X) \cup X$ in $G$, $\opt\cup X$ is a dominating set of $G$.
Next, we show that in polynomial time we can find a subset of vertices $Y$ of size at most $2|X|$ such that $\opt\cup X\cup Y$ is a connected dominating set in $G$.

Note that if the subgraph induced by the vertex set $\opt$ on $G'\cup (\bigcup_{i\in [\ell]}K_i)$ contains an edge $uv$ which is not in $E(G')$, the edge can be replaced by a $uv$-path in $G$ whose intermediate vertices are all in $X$. Hence, we can replace all such edges in $\opt$ by including a subset of vertices $X' \subseteq X$ and the set $\opt \cup X'$ remains connected in $G$. At this point, if $X = X'$, we are done: $\opt\cup X$ is a connected dominating set in $G$. Suppose this is not the case and let $X_1:= X\setminus X'$ and $Y_1:= \neighb_{G}(X_1)\setminus \neighb_{G}(X')$. Since $G$ is connected, there exists a path from $X_1$ to $\opt \cup X'$. Moreover, we claim that there exists a path of length at most $4$ from $X_1$ to $\opt\cup X'$. Recall that $\opt\cup X'$ dominates $V\setminus (X_1 \cup Y_1)$. Hence, the shortest path from of $X_1$ to $\opt\cup X'$ has length at most $4$.
We add the vertices on the shortest path which are in $X \setminus X'$ to $X'$ and the vertices in $V \setminus (X \cup \opt \cup Y)$ to $Y$, and update the sets $X_1$ and $Y_1$ accordingly.
Thus we reduce the size of $X_1$ and as we repeat this process it eventually becomes zero. At this point $X = X'$ and $\opt \cup X \cup Y$ is a connected dominating set in $G$. Since, we pick up at most three vertices per each $x\in X_1$ and at least one is in $X$, the set $X \cup Y$ has size at most $3|X|$.
\end{proof}

\begin{corollary}\label{cor:conected-dom-set-vertex-treewidth}
\CDSfull has $O(1 + O(\delta \log^{1.5} n))$-approximation for graphs $(\delta\cdot \opt(G))$-close to treewidth $\Tw$ via vertex deletion where $w$ is a fixed constant.
\end{corollary}
\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lem:cds-stable})
  and structural lifting with constant $c=3$ (Lemma~\ref{lem:cds-lifting}).

  We use our $(O(\log^{1.5} n), O(\sqrt{\log \Tw}))$-approximate editing algorithm
  (Section~\ref{section:positive_treewidth}) and an exact polynomial-time algorithm for
  \ACDS given the tree-decomposition of width $O(w\sqrt{\log w})$ of the edited graph.
  The FPT algorithm modifies the $\Tw^{O(\Tw)}\cdot n^{O(1)}$ dynamic-programming approach
  of \DS such that it incorporates the annotated sets and cliques $K_1, \cdots, K_\ell$ which then
  runs in $(\Tw + \ell)^{O(\Tw)}\cdot n^{O(1)} = n^{O(\Tw)}$.
  Thus $\Tw = O(1)$, $\alpha=O(\log^{1.5} n)$ and $c = 3$, resulting in an algorithm that runs in
  polynomial time and constructs a $(1 + O(\log^{1.5} n) \delta)$-approximate solution.
\end{proof}

\subsection{Edge Deletion}
\begin{lemma}\label{lemma:IS-edge-stable}
  For $\ell \geq 1$,
  ($\ell$-)\ISfull is stable under edge deletion with constant $c'= 0$.
\end{lemma}
\begin{proof}
  Given $G$ and any set $X \subseteq E(G)$ with $|X| \leq \gamma$, let $G' = G[E\setminus X]$.
  For any ($\ell$-)independent set $Y \subseteq V(G)$, $Y' = Y$ is also an ($\ell$-)independent set in $G'$.
  Then $\opt(G') \geq |Y'| = |Y|$, and so for optimal $Y$, $\opt(G') \geq \opt(G)$.
\end{proof}

\begin{lemma}\label{lemma:IS-edge-lift}
  For $\ell \geq 1$, ($\ell$-)\ISfull can be structurally lifted with respect to edge deletion with constant $c=1$.
\end{lemma}
\begin{proof}
  Given a graph $G$ and $X \subseteq E(G)$, let $G' = G[E\setminus X]$.
  Let $Y' \subseteq V(G')$ be an ($\ell$-)independent set in $G'$,
  and consider the same vertex set $Y'$ in $G$.
  Assume that the edit set is a single edge, $X = \{(u,v)\}$.
  We claim there exists a subset of $Y'$ with size at least $|Y'| - 1$
  which is still an ($\ell$-)independent set in $G$.

  For convenience, we let $d(\cdot, \cdot) := d_G(\cdot, \cdot)$ for the remainder of this proof.  Suppose there are four distinct nodes $a,b,f,g \in Y'$ such that
  $d(a,b)\leq \ell$ and $d(f,g) \leq \ell$ in $G$.
  Since these nodes are in $Y'$, we know $d_{G'}(a,b), d_{G'}(f,g) \geq \ell+1$,
  hence, any shortest path from $a$ to $b$ in $G$ must use the edge $(u,v)$ in order to have length $\leq \ell$.
  \WLOG we can assume the $a$-$b$ path goes from $a$ to $u$ to $v$ to $b$, and so
  $d(a,u) + 1 + d(v,b) \leq \ell$.
  Similarly we can assume the $f$-$g$ path goes from $f$ to $v$ to $u$ to $g$, and so
  $d(f,v) + 1 + d(u,g) \leq \ell$.
  We now argue that the shortest paths in $G$ from $a$ to $u$, $v$ to $b$, $f$ to $v$, and $u$ to $g$ do not use the edge $(u,v)$ and are therefore also paths in $G'$. Suppose
  not and consider \WLOG the case when a shortest path from $a$ to $u$ contains $(u,v)$.
  Then concatenating the subpath from $a$ to $v$ with
  a shortest path from $v$ to $b$ gives an $a,b$-path of length $d(a,u) - 1 + d(v,b) < \ell$, which does not use the edge $(u,v)$ (and is thus a path in $G'$, contradicting $(\ell-)$independence of $Y'$).

  Now consider the paths ($a$ to $u$ to $g$) and ($f$ to $v$ to $b$).
  Let $\ell_A = d(a,u) + d(u,g)$ and $\ell_F = d(f,v) + d(v,b)$,
  and note that
  $\ell_A+\ell_F = d(a,u) + d(v,b) + d(f,v) + d(u,g),$
  which is $\leq 2\ell - 2$.
  So at least one of $\ell_A$ or $\ell_F$ must be $\leq \ell-1$, a contradiction.

  Three cases remain: (1) $Y'$ contains exactly two vertices connected by a path of length $\leq \ell$ in $G$; (2) $Y'$ contains three distinct vertices pair-wise connected by paths of length $\leq \ell$ in $G$; or (3) $Y'$ contains one vertex, $a$, connected to two or more other vertices of $Y'$ by paths of length $\leq \ell$ in $G$.
  In the first case, $Y'$ contains $a,b$ with $d(a,b) \leq \ell$; then removing either endpoint from $Y'$ yields an $(\ell-)$independent set of size $|Y'|-1$ in $G$.

  We now show the second case cannot occur. Suppose that $d(b,c), d(a,b), d(a,c) \leq \ell$ for $a,b,c \in Y'$. Note that each vertex is within distance $\ell/2$ of at least one of the vertices $u$ or $v$. By the pigeonhole principle, some two of $a,b,c$ must be within $\ell/2$ of the same endpoint of $(u,v)$; say vertices $a$ and $b$ are within $\ell/2$ of $u$ \WLOG; this implies $d_{G'}(a,b) \leq \ell$, a contradiction.

  Finally, in the third case, $Y'$ contains a node $a$ and a subset $S$ so that $|S| \geq 2$,
  $d(a,s) \leq \ell$ for all $s \in S$ and $d(s_1, s_2) > \ell$ for all $s_1 \neq s_2$ in $S$. Further, we know no other pair of nodes in $Y'$ is at distance at most $\ell$ in $G$ (since then we would have two disjoint pairs at distance at most $\ell$, a case we already handled). In this setting, $Y'\setminus \{a\}$ is an $(\ell-)$independent set of size $|Y'|-1$ in $G$.
  This proves that adding a single edge to $G'$ will reduce the size of the ($\ell$-)independent set $Y'$ by no more than one, so by induction the lemma holds.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:edge-edits-approx}]
  \ISfull has a $(1/(3\Tr+1) - 3\delta)$-approximation for graphs
  $(\delta \cdot \opt(G))$-close to degeneracy~$\Tr$ via edge deletions.
\end{corollary}

\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=0$ (Lemma~\ref{lemma:IS-stable})
  and structural lifting with constant $c=1$ (Lemma~\ref{lemma:IS-stable-lift}).
  We use our $(3,3)$-approximate editing algorithm
  (Corollary~\ref{cor:edge-edit})
  and the $1/(\Tr+1)$-approximation algorithm for independent set described in the proof of Corollary~\ref{cor:appendix-is-vertex-edit-approximation}.
  Thus $\alpha=\beta=3$ and $\rho(\beta \Tr) = 1/(\beta \Tr + 1)$,
  resulting in an approximation factor of $1/(3 \Tr+1) - 3 \delta$.
\end{proof}

\begin{lemma}\label{lemma:ED-stable}
The problems \DSmaybefull and \EDSmaybefull are stable under edge deletion with constant $c' = 1$.
\end{lemma}

\begin{proof}
Given $G$ and any set $X \subseteq E(G)$ with $|X| \leq \gamma$, let $G' = G[E\setminus X]$, and let $Y$ be a minimum (\DSradius-)dominating set on $G$. Each vertex $v$ may be (\DSradius-)dominated by multiple vertices on multiple paths, which we refer to as $v$'s \textit{dominating paths}.

Consider all vertices for which a specific edge $(u,v)$ is on all of their dominating paths in $G$. We refer to each of these vertices as $(u,v)$-dependent. Note that if we traverse all dominating paths from each $(u,v)$-dependent vertex, $(u,v)$ is traversed in the same direction each time. Assume \WLOG $(u,v)$ is traversed with $u$ before $v$, implying $u$ is not $(u,v)$-dependent but $v$ may be. Now if $(u,v)$ is deleted, then $Y \cup {\{v\}}$ is a (\DSradius-)dominating set on the new graph. Therefore for each edge $(u,v)$ in $X$ we must add at most one vertex to the (\DSradius-)dominating set.  Thus if $Y'$ is a minimum (\DSradius-)dominating set on $G'$ then $|Y'| \leq |Y| + \gamma$ and \DSmaybe is stable under edge deletion with constant $c' = 1$.

Now let $Z$ be a minimum edge (\DSradius-)dominating set on $G$.
The proof for \EDSmaybe follows similarly as in the above case when a deleted edge $(u,v)$ is not in $Z$ (though an edge incident to $v$ would be picked to become part of the dominating set instead of $v$ itself). However if $(u,v)$ is in the minimum edge (\DSradius-)dominating set then it is possible that there are edges which are strictly $(u,v)$-dependent through only $u$ or $v$ and no single edge is within distance \DSradius~ of both. In this case we add an edge adjacent to $u$ and an edge adjacent to $v$ to $Z$, which also increases $Z$'s size by one with the deletion of $(u,v)$.
Thus if $Z'$ is a minimum edge (\DSradius-)dominating set on $G'$ then $|Z'| \leq |Z| + \gamma$ and
 \EDSmaybefull is stable under edge deletion with constant $c'=1$.
\end{proof}

\begin{lemma}\label{lemma:ED-sl}
 \DSmaybefull and \EDSmaybefull can be structurally lifted with respect to edge deletion with constants $c = 0$ and $c = 1$ respectively.
\end{lemma}

\begin{proof}

Given $G$ and any set $X \subseteq E(G)$ with $|X| \leq \gamma$, let $G' = G[E\setminus X]$.
A (\DSradius-)dominating set in $G'$ is also a (\DSradius-)dominating set in $G$.
Therefore, a solution $S'$ in $G'$ yields a solution $S$ in $G$ such that $\cost_{\DSmaybe}(S') = \cost_{\DSmaybe}(S)$.

An edge (\DSradius-)dominating set $Y'$ in $G'$ may not be an edge (\DSradius-)dominating set in $G$, as there may be edges in $X$ which are not (\DSradius-)dominated by $Y'$. However  $Y' \cup X$ is an edge (\DSradius-)dominating set in $G$ and $|Y' \cup X| \leq |Y'| + |X|$.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:edge-edits-approx}]
  \DSfull has an $O((1+\delta) \Tr)$-approximation for graphs
  $(\delta \cdot \opt(G))$-close to degeneracy~$r$ via edge deletions.
\end{corollary}

\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=1$ (Lemma~\ref{lemma:ED-stable})
  and structural lifting with constant $c=0$ (Lemma~\ref{lemma:ED-sl}).
  We use our $(5,5)$-approximate editing algorithm
  (Section~\ref{section:positive_degeneracy_LP_edge})
  and a known $O(\Tr)$-approximation algorithm for \DS
  \cite{bansal2017tight}.
  Thus $\alpha=\beta=5$ and $\rho(\beta \Tr) = O(\beta \Tr)$,
  resulting in an approximation factor of $O((1+ \delta) \Tr)$.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:edge-edits-approx}]\label{cor:edge-deletion-approx-treewidth}
  \DSmaybefull and \EDSmaybefull have
  $(1 + O(\delta \log n\log\log n))$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to treewidth~$w$ via edge deletions where $w\log w = O(\log_{\ell} n)$.
\end{corollary}

\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=1$ (Lemma~\ref{lemma:ED-stable})
  and structural lifting with constant $c=0$ for \DSmaybe and constant $c=1$ for \EDSmaybe (Lemma~\ref{lemma:ED-sl}).
  For treewidth $\Tw$, we use the
  $(O(\log n\log\log n), O(\log \Tw))$-approximate editing algorithm
  of Bansal \etal~\cite{bansal2017lp}
  and an exact algorithm for \DSmaybe and \EDSmaybe~\cite{borradaile_et_al:LIPIcs:2017:6919} given a tree-decomposition of width $O(w\log w)$ of the edited graph.

  Thus $\alpha=O(\log n\log\log n)$ and $c' = 1$ for \DS and $c'=c=1$ for \EDS,
  resulting in an approximation factor of $1 + O(\log n\log\log n) \delta$.
  Note that since the edited graph has treewidth $O(w\log w) = O(\log_{\ell} n)$, the exact algorithm runs in polynomial-time.

\end{proof}

\begin{lemma}\label{lemma:MC-stable}
The problem \MCfull is stable under edge deletion with constant $c' = 1$.
\end{lemma}
\begin{proof}
Given $G$ and any set $X \subseteq E(G)$ with $|X| \leq \gamma$, let $G' = G[E\setminus X]$, and let $Y$ be a maximum cut in $G$. Then, $Y': = Y\setminus X$ is a cut in $G'$ of size at least $|Y| - |X|$; hence, $c' =1$.
\end{proof}

\begin{lemma}\label{lemma:MC-sl}
 \MCfull can be structurally lifted with respect to edge deletion with constant $c = 0$.
\end{lemma}
\begin{proof}
Given $G$ and any set $X \subseteq E(G)$ with $|X| \leq \gamma$, let $G' = G[E\setminus X]$.
A cut $Y\subseteq E(G')$ is trivially a valid cut in $G$ and consequently $c=0$.
\end{proof}

\begin{corollary}[Restatement of Theorem~\ref{thm:edge-edits-approx}]
  \MCfull has
  $(1 - O(\delta \log n\log\log n))$-approximations for graphs
  $(\delta \cdot \opt(G))$-close to treewidth~$w$ via edge deletions where $w\log w = O(\log n)$.
\end{corollary}

\begin{proof}
  We apply Theorem~\ref{thm:general-edit-sr} using
  stability with constant $c'=1$ (Lemma~\ref{lemma:MC-stable})
  and structural lifting with constant $c=0$ for \MC (Lemma~\ref{lemma:MC-sl}).
  For treewidth $\Tw$, we use the
  $(O(\log n\log\log n), O(\log \Tw))$-approximate editing algorithm
  of Bansal~\etal~\cite{bansal2017lp}
  and an exact algorithm for \MC given a tree-decomposition of width $O(w\log w)$ of the edited graph.

  Thus $\alpha=O(\log n\log\log n)$ and $c' = 1$ for \MC ,
  resulting in an approximation factor of $1 + O(\log n\log\log  n) \delta$.
  Note that since the edited graph has treewidth $O(w\log w) = O(\log n)$, the exact algorithm runs in polynomial-time.
\end{proof}
\fi


text:
\section*{Appendix A: Notation}

\begin{tabular}{c c}
   Example & Description \\ \hline
   $z$ & Scalar \\
   $\z$ & Vector \\
   $Z$ & Continuous random variable \\
   $K$ & Discrete random variable \\
   $\Z$  & Continuous random vector \\
   $p(\z)$ & Continuous PDF \\
   $P(k) $ & Discrete PMF \\
   $H[K]$ & Discrete entropy \\
   $h[Z]$ & Differential entropy \\
   $\E[Z]$ & Expectation \\
   $\KL[q_{\Z \mid \x} \mm p_{\Z}]$ & Kullback-Leibler divergence \\
   $\TV[q, p]$ & Total variation distance \\
\end{tabular}

\section*{Appendix B: Computational complexity of reverse channel coding}
Existing algorithms for lossy compression without quantization communicate a sample by simulating a large number of random variables $Z_n \sim p$ and then identifying an index $N^*$ such that $Z_{N^*}$ is distributed according to $q$, at least approximately in a total variation sense \cite[e.g.,][]{cuff2008,havasi2018miracle}. Here we show that no polynomial time algorithm exists which achieves this, assuming $RP \neq NP$, where $RP$ is the class of randomized polynomial time algorithms.

Our result depends on the results of \citet[Theorem 13]{long2010rbm}, who showed that simulating \textit{restricted Boltzmann machines} (RBMs) \cite{smolensky1987rbm} approximately is computationally hard. For completeness, we repeat it in slightly weakened but simpler form here:

\newtheorem{theorem}{Theorem}

\begin{theorem}
If $RP \neq NP$, then there is no
polynomial-time algorithm with the following property:
Given as input $\bm{\theta} = (\A, \ba, \bb)$ such that $\A$ is an $M \times M$
matrix, the algorithm outputs an efficiently evaluatable representation of a distribution whose total variation distance from an RBM with parameters $\bm{\theta}$ is at most $\tfrac{1}{12}$.
\end{theorem}

Here, an \textit{efficiently evaluatable representation} of a distribution $q$ is defined as a Boolean function
\begin{align}
    f: \{0, 1\}^N \rightarrow \{0, 1\}^M
\end{align}
with the following two properties. First, $f(\bm{B}) \sim q$ if $\bm{B}$ is a random vector of uniformly random bits. Second, $N$ and the function's computational complexity are bounded by a polynomial in $M$.

One might hope that having access to samples from a similar distribution would help to efficiently simulate an RBM. The following lemma shows that additional samples quickly become unhelpful as the Kullback-Leibler divergence between the two distributions increases.

\newtheorem{lemma_appendix}{Lemma}
\begin{lemma_appendix}
Consider an algorithm which receives a description of an arbitrary probability distribution $q$ as input and is also given access to an unlimited number of i.i.d. random variables $\Z_n \sim p$. It outputs $\Z \sim \tilde q$ such that its distribution is approximately $q$ in the sense that $\TV[\tilde q, q] \leq 1/12$. If $RP \neq NP$, then there is no such algorithm whose time complexity is polynomial in $\KL[q \mm p]$.
\end{lemma_appendix}
\begin{proof}
Let $\z \in \{0, 1\}^M$ be a binary vector and let
\begin{align}
    q(\z) = \frac{1}{Z} \sum_{\h \in \{0, 1\}^M} \exp( \ba^\T \z + \h^\T \A \z + \bb^\T\h)
\end{align}
be the probability distribution of an RBM with normalization constant~$Z$ and parameters $\ba, \bb \in \reals^M$ and $\A \in \reals^{M \times M}$. Further, let $p(\z) = 2^{-M}$ be the uniform distribution. Then
\begin{align}
    \KL[q \mm p] = \sum_{\z \in \{0, 1\}^M} q(\z) \log_2 \frac{q(\z)}{2^{-M}} = M - H[q] \leq M.
\end{align}
If there is an algorithm which generates an approximate sample from an RBM's distribution $q$ in a number of steps which is polynomial in $\KL[q \mm p]$, then its computational complexity is also bounded by a polynomial in $M$. In that time the algorithm can take into account at most $N$ random variables $\Z_n$ where $N$ is polynomial in $M$, that is, $N = \psi(M)$ for some polynomial $\psi$. Since the input random variables are independent and identical, we can assume without loss of generality that the algorithm simply uses the first $N$ random variables. The $N$ random variables correspond to an input of $M \psi(M)$ uniformly random bits. Note that $M \psi(M)$ is still polynomial in $M$.

However, Theorem~1 states that there is no such polynomial time algorithm if $RP \neq NP$.
\end{proof}

\section*{Appendix C: Generalizations of universal quantization}
\begin{figure}[h!]
    \centering
    \includegraphics[width=0.4\textwidth]{figures/voronoi_noise.png}
    \caption{A visualization of an example of the generalized uniform noise channel which can be implemented efficiently. Blue dots represent a lattice and black lines indicate corresponding Voronoi cells. The black dot corresponds to the coefficients $\y$ and the orange dots are realizations of the random variable $\y + \U$.}
    \label{fig:lattice}
\end{figure}
While the approach discussed in the main text is statistically and computationally efficient, it only allows us to communicate samples from a simple uniform distribution. We briefly discuss two possible avenues for generalizing this approach.

One such generalization to lattice quantizers was already discussed by \citet{ziv1985universal}. Let $\Lambda$ be a lattice and $Q_\Lambda(\y)$ be the nearest neighbor of $\y$ in the lattice. Further let $\V$ be a Voronoi cell of the lattice and $\U \sim U(\V)$ be a random vector which is uniformly distributed over the Voronoi cell. Then \cite[Theorem 4.1.1]{zamir2014book}
\begin{align}
    Q_\Lambda(\y - \U) + \U \sim \y + \U.
\end{align}
An example is visualized in Figure~\ref{fig:lattice}. For certain lattices and in high dimensional spaces, $\U$ will be distributed approximately like a Gaussian~\cite{zamir2014book}. This means universal quantization could be used to approximately simulate an additive white Gaussian noise channel.

Another possibility to obtain Gaussian noise would be the following. Let $S$ be a positive random variable independent of $Y$ and $U \sim U([-0.5, 0.5))$. We assume that $S$ like $U$ is known to both the encoder and the decoder. It follows that
\begin{align}
    (\lfloor y/S - U \rceil + U) \cdot S \sim y + SU'
\end{align}
for another uniform random variable $U'$. If $G \sim \Gamma(\sfrac{3}{2}, \sfrac{1}{2})$ and $S = 2\sigma\sqrt{G}$, then $SU'$ has a Gaussian distribution with variance $\sigma^2$ \cite{qin2003scalemixture}. More generally, this approach allows us to implement any noise which can be represented as a uniform scale mixture. However, the average number of bits required for transmitting $K = \lfloor y/S - U \rceil$ can be shown to be (Appendix~B)
\begin{align}
    H[K \mid U, S] = I[Y, (Z, S)] \geq I[Y, Z],
\end{align}
where $Z = Y + SU'$. This means we require more bits than we would like to if all we want to transmit is $Z$. However, if we consider $(Z, S)$ to be the message, then again we are using only as many bits as we transmit information.

\section*{Appendix D: Differentiability of soft-rounding}
For $\alpha > 0$, we defined a soft rounding function as
\begin{align}
    s_\alpha(y) = \floor{y} + \frac{1}{2} \frac{\tanh(\alpha r)}{\tanh(\alpha / 2)} + \frac{1}{2}, \quad \text{where} \quad
    r = y - \floor{y} - \frac{1}{2}.
\end{align}
The soft-rounding function is differentiable everywhere. First, we show that the derivative exists at $0$. The right derivative of $s_\alpha$ at $0$ exists and is given by
\begin{align}
    \lim_{\varepsilon \downarrow 0} \frac{s_\alpha(\varepsilon) - s_\alpha(0)}{\varepsilon}
&= \lim_{\varepsilon \downarrow 0} \frac{1}{\varepsilon} \left( \floor{\varepsilon} - \frac{1}{2} \frac{\tanh(\alpha (\varepsilon - \floor{\varepsilon} - \frac{1}{2}))}{\tanh(\alpha / 2)} - \frac{1}{2} \frac{\tanh(-\alpha/2)}{\tanh(\alpha / 2)} \right) \\
&= \lim_{\varepsilon \downarrow 0} \frac{1}{\varepsilon} \left(\frac{1}{2} \frac{\tanh(\alpha (\varepsilon - \frac{1}{2}))}{\tanh(\alpha / 2)} - \frac{1}{2} \frac{\tanh(-\alpha/2)}{\tanh(\alpha / 2)} \right) \\
&= \lim_{\varepsilon \downarrow 0} \frac{\tanh(\alpha (\varepsilon - \frac{1}{2})) - \tanh(-\alpha/2)}{2\varepsilon\tanh(\alpha / 2)} \\
&= \frac{1}{2\tanh(\alpha / 2)} \lim_{\varepsilon \downarrow 0} \frac{\tanh(\alpha\varepsilon -\alpha/2) - \tanh(-\alpha/2)}{\varepsilon} \\
&= \frac{1}{2\tanh(\alpha / 2)} \left. \frac{\partial}{\partial x}\tanh\left(\alpha x - \alpha/2 \right) \right|_{x=0} \\
&= \frac{\alpha}{2} \frac{\tanh'\left(-\alpha/2\right)}{\tanh(\alpha / 2)}.
\end{align}
Similarly, the left derivative at $0$ exists and is given by
\begin{align}
    \lim_{\varepsilon \uparrow 0} \frac{s_\alpha(\varepsilon) - s_\alpha(0)}{\varepsilon}
&= \lim_{\varepsilon \uparrow 0} \frac{1}{\varepsilon} \left( \floor{\varepsilon} + \frac{1}{2} \frac{\tanh(\alpha (\varepsilon - \floor{\varepsilon} - \frac{1}{2}))}{\tanh(\alpha / 2)} - \frac{1}{2} \frac{\tanh(-\alpha/2)}{\tanh(\alpha / 2)} \right) \\
&= \lim_{\varepsilon \uparrow 0} \frac{1}{\varepsilon} \left( -1 + \frac{1}{2} \frac{\tanh(\alpha (\varepsilon + \frac{1}{2}))}{\tanh(\alpha / 2)} - \frac{1}{2} \frac{\tanh(-\alpha/2)}{\tanh(\alpha / 2)} \right) \\
&= \lim_{\varepsilon \uparrow 0} \frac{ -2\tanh(\alpha/2) + \tanh(\alpha (\varepsilon + \frac{1}{2})) + \tanh(\alpha/2) }{ 2 \varepsilon \tanh(\alpha / 2) } \\
&= \frac{1}{2\tan(\alpha/2)} \lim_{\varepsilon \uparrow 0} \frac{ \tanh(\alpha \varepsilon - \alpha/2) - \tanh(\alpha/2) }{ \varepsilon } \\
&= \frac{\alpha}{2} \frac{\tanh'\left(-\alpha/2\right)}{\tanh(\alpha / 2)}.
\end{align}
Since the left and right derivatives are equal, $s_\alpha$ is differentiable at $0$. Since $s_\alpha(y + 1) = s_\alpha(y) + 1$, the derivative also exists for other integers and it is easy to see that $s_\alpha$ is differentiable for $y \notin \integers$. Hence, $s_\alpha$ is differentiable everywhere.

\section*{Appendix E: Adapting density models}
\label{sec:adapters}
For the rate term we need to model the density of $f(\x) + \U$. When $\y = f(\x)$ is assumed to have independent components, we only need to model individual components $Y + U$.
Following \citet{balle2018variational}, we parameterize the model through the cumulative distribution $c_Y$ of $Y$, as we have
\begin{equation}
    p_{Y+U}(y)=c_Y(y+0.5)-c_Y(y-0.5).
\end{equation}
We can generalize this to model the density of $s(Y)+U$, where $s: \reals \to \reals$ is an invertible function. Since $c_{s(Y)} = c_Y(s^{-1}(y))$, we have
\begin{equation}
p_{s(Y)+U}(y)=c_Y(s^{-1}(y)+0.5)-c_Y(s^{-1}(y)-0.5).
\end{equation}
This means we can easily adjust a model for the density of $f(\X)$ to model the density of $s_{\alpha}(f(\X)) + \U$. In addition to being a suitable density, creating an explicit dependency on $\alpha$ has the added advantage of automatically adapting the density if we choose to change $\alpha$ during training.

\newpage
\section*{Appendix F: Additional experimental results}
\begin{figure}[!h]
    \centering
    \begin{tikzpicture}
        \node at (0, 0)
            {\includegraphics[width=6cm]{figures/linear_train_test_gap_dct_psnr.pdf}};
        \node at (-2.8, 2.55) {\textsf{\textbf{A}}};
        \node at (6, 0)
            {\includegraphics[width=6cm]{figures/linear_train_test_gap_ortho_mse.pdf}};
        \node at (3.2, 2.55) {\textsf{\textbf{B}}};
        \node at (-0.25, -6.2)
            {\includegraphics[width=6cm]{figures/linear_train_test_gap_ortho_msssim.pdf}};
        \node at (-2.8, -3.35) {\textsf{\textbf{C}}};
    \end{tikzpicture}
    \caption{Additional results for the linear model evaluated on the Kodak dataset \cite{kodak}.
        \textbf{A}: The linear model as described in the main text but instead of a random orthogonal initialization, the linear transforms are initialized to the ones used by JPEG/JFIF \cite{itu1992jpeg}. That is, a YCC color transformation followed by a DCT for the encoder and corresponding inverses for the decoder. \textbf{B}: The linear model orthogonally initialized as in the main text but evaluated in terms of MSE instead of PSNR. \textbf{C}: The same linear model (orthogonally initialized, trained with respect to MSE) evaluated in terms of MS-SSIM.}
    \label{fig:linear_model}
\end{figure}

\begin{figure}[!h]
    \centering
    \begin{tikzpicture}
        \node at (0, 0)
            {\includegraphics[width=6cm]{figures/hyperprior_train_test_gap_mse_v3.pdf}};
        \node at (-2.8, 2.55) {\textsf{\textbf{A}}};
        \node at (6, 0)
            {\includegraphics[width=6cm]{figures/hyperprior_train_test_gap_msssim.pdf}};
        \node at (3.2, 2.55) {\textsf{\textbf{B}}};
        \node at (-0.25, -6.2)
            {\includegraphics[width=6cm]{figures/hyperprior_ablate_suppl_v3.pdf}};
        \node at (-2.8, -3.35) {\textsf{\textbf{C}}};
    \end{tikzpicture}
    \caption{Additional results for the hyperprior model evaluated on the Kodak dataset \cite{kodak}.
        \textbf{A}: The hyperprior model from the main text but evaluated in terms of MSE instead of PSNR. \textbf{B}: The same model evaluated in terms of MS-SSIM. \textbf{C}: The effect of expected gradients shown for the full bitrate range.}
    \label{fig:hyperprior_model}
\end{figure}

\newpage

\section*{Appendix G: Qualitative results}
Below we include reconstructions of images from the Kodak dataset \cite{kodak} for the three approaches \textbf{UN + UQ}, \textbf{UN + Q}, and \textbf{UN + UQ + SR} trained with the same trade-off parameter $\lambda$. We chose a low bit-rate to make the differences more easily visible.

For the linear model (Figures~\ref{fig:qualitative_linear_kodim03}-\ref{fig:qualitative_linear_kodim23}), reconstructions using \textbf{UN + Q} and \textbf{UN + UQ + SR} have visible blocking artefacts as would be expected given their similarity to JPEG/JFIF \cite{itu1992jpeg}. \textbf{UN + UQ} masks the blocking artefacts almost completely at the expense of introducing grain.

For the hyperprior model (Figures~\ref{fig:qualitative_hyper_kodim02}-\ref{fig:qualitative_hyper_kodim21}), we noticed a tendency of \textbf{UN + Q} to produce grid artefacts which we did not observe using \textbf{UN + UQ + SR}.

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_linear_4/kodim03.png} \\
\textbf{UN + UQ}, bpp: 0.762 (113\%), PSNR: 32.79 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_linear_4/kodim03.png} \\
\textbf{UN + Q}, bpp: 0.672 (100\%), PSNR: 34.33 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_linear_4/kodim03.png} \\
\textbf{UN + UQ + SR}, bpp: 0.562 (83\%), PSNR: 33.60 \\
    \end{tabular}
    \caption{Linear model, kodim03}
    \label{fig:qualitative_linear_kodim03}
\end{figure}

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_linear_4/kodim16.png} \\
\textbf{UN + UQ}, bpp: 0.836 (111\%), PSNR: 32.22 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_linear_4/kodim16.png} \\
\textbf{UN + Q}, bpp: 0.750 (100\%), PSNR: 33.09 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_linear_4/kodim16.png} \\
\textbf{UN + UQ + SR}, bpp: 0.623 (83\%), PSNR: 32.54 \\
\end{tabular}
    \caption{Linear model, kodim16}
    \label{fig:qualitative_linear_kodim16}
\end{figure}

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
    \includegraphics[width=0.8\linewidth]{visuals/UN_UQ_linear_4/kodim23.png} \\
\textbf{UN + UQ}, bpp: 0.778 (115\%), PSNR: 33.05 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_linear_4/kodim23.png} \\
\textbf{UN + Q}, bpp: 0.674 (100\%), PSNR: 34.71 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_linear_4/kodim23.png} \\
\textbf{UN + UQ + SR}, bpp: 0.572 (84\%), PSNR: 33.98 \\
\end{tabular}
    \caption{Linear model, kodim23}
    \label{fig:qualitative_linear_kodim23}
\end{figure}

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_hyper_1/kodim02.png} \\
\textbf{UN + UQ}, bpp: 0.091 (143\%), PSNR: 29.36 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_hyper_1/kodim02.png} \\
\textbf{UN + Q}, bpp: 0.063 (100\%), PSNR: 28.78 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_hyper_1/kodim02.png} \\
\textbf{UN + UQ + SR}, bpp: 0.059 (93\%), PSNR: 29.55 \\
\end{tabular}
    \caption{Hyperprior model, kodim02}
    \label{fig:qualitative_hyper_kodim02}
\end{figure}

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_hyper_1/kodim15.png} \\
\textbf{UN + UQ}, bpp: 0.099 (137\%), PSNR: 29.31 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_hyper_1/kodim15.png} \\
\textbf{UN + Q}, bpp: 0.073 (100\%), PSNR: 28.82 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_hyper_1/kodim15.png} \\
\textbf{UN + UQ + SR}, bpp: 0.072 (99\%), PSNR: 29.56 \\
\end{tabular}
    \caption{Hyperprior model, kodim15}
\end{figure}

\begin{figure}[h!]
\vspace{-2cm}
    \centering
    \begin{tabular}{c}
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_hyper_1/kodim21.png} \\
\textbf{UN + UQ}, bpp: 0.156 (130\%), PSNR: 27.11 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_Q_hyper_1/kodim21.png} \\
\textbf{UN + Q}, bpp: 0.120 (100\%), PSNR: 26.75 \\
\includegraphics[width=0.8\linewidth]{visuals/UN_UQ_SR_hyper_1/kodim21.png} \\
\textbf{UN + UQ + SR}, bpp: 0.123 (102\%), PSNR: 27.08 \\
    \end{tabular}
    \caption{Hyperprior model, kodim21}
    \label{fig:qualitative_hyper_kodim21}
\end{figure}

config: arxiv


text:
\begin{document}
\maketitle

\begin{abstract}
We present improved sampling complexity bounds for stable and robust sparse recovery in compressed sensing. Our unified analysis based on  $\ell^1$ minimization encompasses the case where (i) the measurements are block-structured samples in order to reflect the structured acquisition that is often encountered in applications; (ii) \replace{where}{} the signal has an arbitrary structured sparsity, by results depending on its support $S$.  Within this framework and under a random sign assumption, the number of measurements needed by $\ell^1$ minimization can be shown to be of the same order than the one required by an oracle least-squares estimator. Moreover, these bounds can be minimized by adapting the variable density sampling to a given prior on the signal support and to the coherence of the measurements. We illustrate both numerically and analytically that our results can be successfully applied to recover Haar wavelet coefficients that are sparse in levels from random Fourier measurements in dimension one and two, which can be of particular interest in {imaging problems}. Finally, a preliminary numerical investigation shows the potential of this theory for devising adaptive sampling strategies in sparse polynomial approximation.
\end{abstract}

\section{Introduction}
\input{src/introduction}

\input{src/setting}

\input{src/main_random_signs}

\input{src/lambda_depending_results}

\input{src/optimal_drawing_strategy}

\input{src/applications}
\input{src/applications_blocks}
\input{src/applications_fct_interp}

\input{src/conclusion}

\input{src/acknowledge}

\appendix

\input{src/proofs}

\input{src/stability}

\input{src/bernstein_ineq}

\input{src/aux_lemmas_extended}

\input{src/proof_proba}

\input{src/appendix_for_applications}

\small
\bibliographystyle{alpha}
\bibliography{mybib}

\end{document}


TITLE: Congruence of constructed circle chords
QUESTION [6 upvotes]: My uncle gave me the following puzzle, hoping there was a mathematical proof to his conjecture.
Let $A$, $B$, and $C$ be points on a circle of some fixed radius. The radius for $C$ bisects the chord $AB$.
Let $P$ be any point on the segment $AC$. Construct a second circle of the same radius which passes through $P$ and $C$. Let $Q$ be the point of intersection of this new circle and the line $BC$.
(See image below.)

My Uncle's Conjecture: $|AB| = |PQ|$.
I have created a proof which uses the Inscribed Angle Theorem a few times. The gist of it is below. Reference the following diagram.

Let $O$ be the center of the original circle, and let $\alpha = \angle COA$.
Notice that also $\alpha = \angle COB$.
By the Inscribed Angle Theorem, we have $\angle CBA = \alpha/2$.
By symmetry, $\angle CAB = \alpha/2$.
Hence $\angle ACB = 180^\circ - \alpha$.
Next, let $R$ be the center of the constructed circle, and label $\beta = \angle CQP$ and $\gamma = \angle CPQ$.
Then $\beta + \gamma = \alpha$.
Also, we have $\angle CRP = 2\beta$, and $\angle CRQ = 2\gamma$ by the same Inscribed Angle Theorem as before.
Thus $\angle PRQ = 2\beta + 2\gamma = 2\alpha$.
Now, by SAS, $\Delta AOB \cong \Delta PRQ$.
In particular, $|AB| = |PQ|$.

So, my question: Does this Theorem have a name or appear in the literature anywhere?

REPLY [3 votes]: In a somewhat more general form, this is the extended law of sines, which says that for a triangle $\triangle ABC$ with circumradius $r$,
$\frac{BC}{\sin A} = \frac{AC}{\sin B} = \frac{AB}{\sin C} = 2r.$ Equivalently, this could be rearranged to say that $$AB = 2r \sin C.$$
Here, because both $2r$ and $\sin C$ are equal for $\triangle ABC$ and $\triangle PQC$, we get $AB = PQ$.
I admit that this straddles the line between "a more general form of your theorem" and "a short proof of your theorem using the extended law of sines", but I think this makes it unlikely that this theorem would show up somewhere with a name: it is too close to the law of sines to be properly its own thing.
On the other hand, if Euclid (who did not deal in trigonometric functions) has any propositions that come close to the law of sines, they would probably resemble your result very closely. But I haven't been able to find any.

Note: capital $R$ is conventional for the circumradius of a circle, but you already have a point with that name, so I use lowercase $r$ instead.


TITLE: Region of ellipse and greens theorem
QUESTION [0 upvotes]: Let γ be the ellipse $x^2 + 4y^
2 = 4$, oriented anticlockwise. Compute $\int_c(4y − 3x)dx + (x − 4y)dy$
I used green theorem with P and Q. and got $$-3\int\int_\ dxdy$$
The answer is $-6\pi,$ so how do I get $2\pi$ from the double integral? Or am I just tackling the problem all wrong?

REPLY [1 votes]: The double integral will give you the area of the ellipse.
Your ellipse is
$$\left( \frac{x}{2}\right)^2+\left(\frac{y}{1}\right)^2 =1 $$ with $a=2$ and $b=1$ and has area $\pi a b= 2 \pi$


TITLE: How Can I Evaluate This Kind of Integral?
QUESTION [1 upvotes]: How Can I Evaluate this kind of integral?
 $$\int_{e^e}^{+∞} lnx dx$$
Your help is very much appreciated

REPLY [2 votes]: The integral itself can be evaluated as follows:
$\int lnxdx=$[integration by parts]$=xlnx-\int xdlnx=xlnx-\int x\frac{1}{x}dx=xlnx-\int dx=x(lnx-1)$
However it does not have a finite limit at infinity. The integral is divergent.


TITLE: Determine f ' (0) Using the First Principles Definition of the Derivative
QUESTION [0 upvotes]: Determine $f'(0)$ Using the First Principles Definition of the Derivative.
$$f: \mathbb R \to \mathbb R\\
x \mapsto  \begin{cases}x^2\sin(\frac{1}{x}); & x \neq 0\\
    0; & x = 0.\end{cases}
$$
My workings:
$$\begin{align}
f'(a) &= \lim_{h\to 0} \frac{f(0+h) - f(0)}{h}\\
&= \lim_{h\to 0} \frac{f(0 + h) - 0}{h}\\
&= \lim_{h\to 0} \frac{f(h)}{h}\\
&= \lim_{h\to 0} \frac{h^2\sin(\frac{1}{h})}{h}\\
&= \lim_{h\to 0} h\sin(\frac{1}{h}) = 0  &\text{By the squeeze theorem.}
\end{align}$$
Please post your solution and full workings below.
Thank you.

REPLY [1 votes]: Your solution is correct, I would just add a line or two about how you know that
$$\lim_{h\to 0} \left[h\sin\left(\frac1h\right)\right]=0$$


TITLE: Norm of a Vector in a Number Field (or Order in a Number Field)
QUESTION [3 upvotes]: I am looking for a measurement, which gives a length of a vector in a number Field? Is there any way or definition for that.
For the Maximal order, What if, I tried to define a map from Maximal order to a Lattice. Is there any way to define a isomorphism from a order of a number field to a lattice. Please give me a example or a reference.

REPLY [9 votes]: A standard way to measure the size (= complexity) of vectors with coordinates in $\overline{\mathbb Q}$ is through the theory of Weil height functions. You can find the definition and properties of the Weil height
$$ H : \mathbb P^n(\overline{\mathbb Q}) \longrightarrow [1,\infty) $$
in many places, such as [1] and [2]. Since you are asking about vectors, rather than points in projective space, you probably want to use the embedding
$$ \overline{\mathbb Q}{}^n \longrightarrow \mathbb P^n(\overline{\mathbb Q}),\qquad
(a_1,\ldots,a_n) \longmapsto [1,a_1,\ldots,a_n] $$
and then take the height.
Among the many nice properties of $H$ is the fact that for any given number field $K$, the number of points in $\mathbb P^n(K)$ with height $H(P)\le C$ is finite. There's even an estimate for the number of such points as $C\to\infty$ due to Schanuel.

Fundamentals of Diophantine Geometry, S. Lang, Springer, 1983.
The Arithmetic of Elliptic Curves, J.H. Silverman, Springer, 2009.

Addendum to Answer OP's Comment: Let $A$ be a matrix with entries in a number field $K$, and let
$\boldsymbol{a}_1,\ldots,\boldsymbol{a}_n$ be its column vectors. We define the absolute value of a vector to be the max of the absolute values of its coordinates. Then the
following should be more-or-less correct, although one has to be a bit
careful about the normalizations of the absolute values.
$$
\begin{aligned}
  H(\det A) &= \prod_{v\in M_K} \max\bigl\{ \|\det A\|_v, 1 \bigr\}\qquad\text{(definition of $H$)} \\
  &\le \prod_{v\in M_K} \max\bigl\{ \|\boldsymbol{a}_1\|_v\cdot\|\boldsymbol{a}_2\|_v\cdots\|\boldsymbol{a}_n\|_v, 1 \bigr\}
    \qquad\text{(Hadamard)} \\
  &\le \prod_{v\in M_K} \prod_{i=1}^n \max\bigl\{ \|\boldsymbol{a}_i\|_v, 1 \bigr\}  \\
  &= \prod_{i=1}^n H( \boldsymbol{a}_i)\qquad\text{(definition of $H$)}.
\end{aligned}
$$


TITLE: Simpler way to define convex functions
QUESTION [0 upvotes]: I find the standard way of defining convex and concave functions slightly tricky. For me, it is the introduction of the new variable $0<λ<1$. However, I understand it intuitively. I was wondering if this definition is equivalent.

Let $f:[a,b] \rightarrow \mathbb{R}$ be a real function. We say $f$ is convex if for all $m,n \in [a,b]$ and for all $x \in (m,n)$ we have $$f(x) \leq \frac{x-m}{n-m}(f(n) - f(m)) + f(m) $$ If the inequality is reversed, we say $f$ is concave .

REPLY [0 votes]: If you require $n>m$ (which may be implicit in your reference to $x\in (m,n)$), then it looks like you've got equivalence between the standard definition and your new one, $\lambda=(x-m)/(n-m)$.  Caveat: I'm not sure your technique is any simpler.


TITLE: Minimum number of elements in $S_A$, given $|A|=n$
QUESTION [1 upvotes]: Problem:
Suppose $A$ is a set of integers with $A=\{a_1,a_2,...a_n\}$. Define $S_A=\{r+s:r,s\in A\}$.
For example, if $A=\{1,3\}$ then $S_A=\{2,4,6\}$.
Show that, $$|S_A|\geq2n-1$$
My attempt:
I tried to use induction, but could not prove the inductive step. The step was, if I add another element $a_{n+1}$ to $A$, atleast $2$ new elements get added to $S_A$.

REPLY [0 votes]: I presume there is a second part of the question  too.
Prove that  there are exactly $2n-1$ elements iff they are in an A.P.


TITLE: For $n \geq 3$ be an integer, consider $S=\sum\limits_{\substack{i=1 \\ (i,n)=1}}^n i$, then $n \mid S$.
QUESTION [0 upvotes]: Let $n \geq 3$ be an integer. Consider $S=\sum\limits_{\substack{i=1 \\ (i,n)=1}}^n i$. I want to show that $n \mid S$.

How do I approach? I am not sure if this can be proved in general, I only checked for some particular values of $n$. I need help to prove it or a counter example to disprove it.

REPLY [4 votes]: If $n$ and $i$, are coprime, $n$, and $n-i$ are coprime too.
For every term $i$ in the sum, there will be the term $n-i$ too, so that the sum will be a multiple of $n$.
Further note: You can see that the sum will be equal to $\dfrac{\varphi(n)}{2}\cdot{n}$, because there are $\varphi(n)$ terms in the sum, and $\varphi(n)/2$ pairs that add up to $n$.
Further explanation: In the situation where $n-i = i$, we get $n = 2i$, which means that $i$ isn't coprime with $n$.


TITLE: Adomian - Example from the book Solving Frontier Problems in Physic
QUESTION [2 upvotes]: Adomian`s Solving Frontier Problems in Physics: The Decomposition Method book, page 16,
example
I don`t understand how u = $\sum_{m=0}^\infty (L^{-1} k x^p)^m u_0$
could be written.
When I take 2 fold nested integrals of $kx^p$ s I can not come to this equation.
For that reason I can not find the $\phi$1 as stated in the example too. When I try to solve I find some other factors in the denominator.
Thank you
Help is highly appreciated.

REPLY [0 votes]: As for your first question: If you agree that $u_{m+1}=L^{-1}k x^pu_m$ for every $m\ge0$, then it follows by induction that $u_m = (L^{-1}kx^p)^m u_0$. Therefore $u:=\sum_{m=0} u_m=\sum_{m=0} (L^{-1}kx^p)^m u_0$.


TITLE: A question about $\sum_i^n (A+BX_i)$
QUESTION [0 upvotes]: $$\sum_{i=1}^n (A+BX_i)= nA +B\sum_{i=1}^n X_i$$
Not sure how to express this question, as english is not my first language.
I know why the A receives an n, but my question is, why does B receive none? B and $X_i$ are separate so shouldn't B receive an N as well?
It is probably aa stupid question, but I couldn't contain my curiosity.

REPLY [0 votes]: I will rather explain why the $n$ appears.
The initial expression is
$$\sum_{i=1}^n(A+BX_i)$$
and you can factor out the constant matrices as follows:
$$\sum_{i=1}^n(A+BX_i)=\sum_{i=1}^nA+\sum_{i=1}^nBX_i=A\sum_{i=1}^n1+B\sum_{i=1}^nX_i$$
and obviously,
$$\sum_{i=1}^n1=n.$$


TITLE: The algebraic interior of a convex set is not empty if the affine hull is the whole space
QUESTION [2 upvotes]: Definitions. Let $X$ be a subset of a linear space $S.$

The affine hull of $X$ is the intersection of all affine spaces (translations of subspaces) that contain $X.$ It is easy to prove that the affine hull of $C$ takes the form $t + H$ where $t \in C$ and $H$ is a vector subspace.
The algebraic interior (relative to the vector space $S$) of $X$ is the set of points $x \in X$ such that for every point $y \in S,$ there is a $\delta = \delta_x > 0$ obeying $x + [0, \delta]y \subset X.$ If $X$ is a convex set (meaning that $x,y \in X$ implies $[x,y] =x + [0,1](y-x) \subset X$) then the algebraic interior is the set of $x \in X$ such that for every $y \in S,$ there exists a $\delta > 0$ such that $x + \delta y \in X.$

Prove or disprove: Let $C$ be a convex subset of $S.$ If the affine hull of $C$ is $S,$ then $C$ has non empty algebraic interior (the reciprocal is easily shown to be true).

In the question: An example of a convex set with empty interior and whose convex hull is the whole space they asked a similar question except there they are considering the usual (topological) interior. More explicitly, if $S$ is a topological vector space (TVS), then the topological interior $X$ is contained in the algebraic interior. In particular, the algebraic interior of $X$ contains the union of $\mathop{\mathrm{int}}\limits_{\tau} (X)$ as $\tau$ runs through all topologies that make $S$ a TVS. That question asks whether the affine hull of $X$ being the whole $S$ is sufficient so that every topology $\tau$ will have $\mathop{\mathrm{int}}\limits_{\tau} (X) \neq \varnothing.$ This question will be answered positively if for some topology $\tau,$ we have $\mathop{\mathrm{int}}\limits_{\tau} (X) \neq \varnothing$ (the possibility that every topological interior is empty and yet the algebraic interior is not empty is open).

REPLY [3 votes]: I'm going to disprove the claim by providing a counter-example.

Let $S=\{(x_1,x_2,\ldots)\in\Bbb R^\infty: x_n=0\text{ for almost all }n\in\Bbb N\}$. This is a linear space.
Let $C=\{x\in S:x_n\geq 0\text{ for all }n\in\Bbb N\}$.
Let $x\in S$ be any vector. Then $x=u-v$ for some $u,v\in C$ ($u$ and $v$ can be chosen as a positive and negative part of $x$, respectively). Moreover $0\in C$. Therefore $x\in\mathrm{aff}\,C$. This shows that $\mathrm{aff}\,C=S$.
Fix arbitrary $x=(x_1,x_2,\ldots,x_n,0,0,\ldots)\in C$. Let $y\in S$ be $y=-e_{n+1} = (0,0,\ldots,0,-1,0,0,\ldots)$ (minus one on the position $n+1$). Observe that for all $\delta>0$ we have $x+\delta y\notin C$. Therefore $x$ isn't an interior point. This shows that the interior of $C$ is empty.


TITLE: $F_{p^n}=\mathbb{Z}_p(\alpha)$, determine whether $\alpha$ is the generator of multiplicative group $F_{p^n}^*=F_{p^n}\backslash \{0\}$.
QUESTION [0 upvotes]: $F_{p^n}=\mathbb{Z}_p(\alpha)$, determine  whether $\alpha$ is the generator of multiplicative group  $F_{p^n}^*=F_{p^n}\backslash \{0\}$.

My try: Since $\alpha$ is the root of a irreducible polynomial of degree $n$, the order of the multiplicative group is $p^n-1$. Also the multiplicative froup is cyclic. Hence if we want to prove $\alpha $ is a generator, we need to prove its order is $ord(\alpha) =p^n-1 $. I am stucked at this step.

REPLY [1 votes]: A generator of the field need not be a generator of the multiplicative group.  Consider $n=3$. Then there are $p^3-p$ choices for $\alpha$, but there are fewer generators of the cyclic group of order $p^3-1$. In particular, $m^{th}$ roots of unity provide counterexamples, where $m=p^2+p+1$.


TITLE: If $G$ is finite abelian and there exists an element of order $> 2$ then $|Aut(G)|$ is even
QUESTION [0 upvotes]: I would appreciate if you could please evaluate my proof and point out any mistakes I made.
Proof:
Since $G$ is abelian, $Inn(G) \cong \{1\}$, thus $Aut(G) = Out(G)$. But the only automorphisms possible are permutations of the elements of $G$. In addition, every automorphism must preserve the identity. Suppose $|G|=n > 2$. Therefore, $|Aut(G)|=\frac{(n-1)!}{2!}$, where $(n-1)!$ is even since all factorials $>1$ are even.

REPLY [2 votes]: Unfortunately, your attempt to a proof is completely wrong. You can't just count permutations of $G$ that fix $1$, because they aren't generally automorphisms. Only some permutations fixing $1$ are.

The map $\iota\colon G\to G$ defined by $\iota(x)=x^{-1}$ is an automorphism of $G$ if and only if $G$ is abelian.
Clearly $\iota\circ\iota=\mathit{id}_G$ is the identity.
Let $x\in G$ have order $n>2$. Then $\iota(x)=x^{n-1}\ne x$ and so $\iota\ne\mathit{id}_G$.
Therefore $\iota$ has order $2$. So $\operatorname{Aut}(G)$ has a subgroup of order $2$.
Note that the finiteness of $G$ is irrelevant.


TITLE: Rotation Graph, Maximum and Minimum Slope
QUESTION [1 upvotes]: I apologize for the last question, it is my first post so I will try to edit this better. The problem is:
The graph of $f(x) = -7x + e^{3x-50x^2}$ is rotated counterclockwise about the origin through an acute angle $\theta$. What is the largest value of $\theta$ for which the rotated graph is still the graph of a function? What about if the graph is rotated clockwise?

First derivative: $-7+e^{3x-50x^2}(3-100x)$
Second Derivative: $10000e^{-50x^2+3x}x^2 - 600e^{-50x^2+3x}x-91e^{-50x^2+3x}$
Setting second derivative equal to $0$: $x_1= -7/100$, $x_2=13/100$
The interval from negative infinity to $-7/100$ is positive, the interval from $-7/100$ to $13/100$ is negative and the interval from $13/100$ to positive infinity is positive.
I evaluated the first derivative with the value $-7/100$ and got: $-7+10/e^{91/200}$ or the decimal representation of $-0.65552$)
I evaluated the first derivative with the value $13/100$ and got: $-7-10/e^{91/200}$ or the decimal representation of $-13.34447$)

REPLY [0 votes]: Everything you have written is correct up to this point. We have a maximum slope of $$m=f'\left(-\frac{7}{100}\right)=-7+10e^{-\frac{91}{200}}\approx-0.65552.$$
Now, we want to convert this slope into an angle, so that we can rotate it. To do this, we solve for $\alpha$ is $\tan\alpha=m$. Doing this gives us $\alpha\approx -33.2^\circ$. Therefore, we can rotate $\alpha$ counter-clockwise up to $\sim123.2^\circ$, since any more than that would give us a vertical slope. So, this would be $\theta$ (however, the problem says that $\theta$ is acute? Double-check that).
Going the other way, we have a minimum slope of $$m=f'\left(\frac{13}{100}\right)=-7-10e^{-\frac{91}{200}}\approx-13.34448.$$
We solve for $\alpha$ in $\tan\alpha=m$. Doing this gives us $\alpha\approx -85.7^\circ$. We can rotate $\alpha$ clockwise up to $\sim4.3^\circ$, since any more than that would give us a vertical slope. So $\theta\approx 4.3^\circ$.


TITLE: GI-hard graph problem not known to be $NP$-complete
QUESTION [15 upvotes]: Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI <_p^m X$).

Is there a natural $GI$-hard graph problem that is neither $GI$-equivalent nor known to be $NP$-complete?

REPLY [0 votes]: A simpler problem could be WEIGHTED_HYPERGRAPH_ISOMORPHISM. You are given two hypergraphs $G_1$ and $G_2$ on $n$ vertices with weighted hyper-edges, decide if there is a vertex permutation $pi$ turning $G_1$ into $G_2$.


TITLE: Calculus: Bending moment given by $M=Wx(l-x)/2$. Find maximum bending moment
QUESTION [0 upvotes]: I have been given the equation $M=Wx\frac{l-x}{2}$

$M$ is the Bending moment
$W$ is the Weight per unit length
$L$ is the Length
$x$ is the distance of load from one end.

I have found the derivative $f(x) = \frac{Wl}{2} - Wx$
I am unsure where to go from here. The examples which I have found online don't give three unknowns.
From what I understand I need to make this equation equal zero and then solve for x to determine my maximum but how would I solve for $x$ with 3 unknowns?

REPLY [0 votes]: You took the derivative and now you have to set it equal to zero. That allows you to solve it for $x$. It follows that $W$ is independent here for your solution, $x$ will depend on $l$ only.
Alternatively your formula is of quadratic nature, a parabola that opens down. So you can find the desired value of $x$ by using the well known formula $-b/(2a)$ from your algebra class to find the same result. Side note, there is only one unknown which is the $x$. The other letters are assumed fixed parameters. Either way, you should find $x=l/2$ but I want you to verify that.


TITLE: Limit without delhospital
QUESTION [0 upvotes]: How can i calculate the limit $\lim_{x \to \infty}\frac{\ln x}{x}$ without the use of delhospital rule. I have tried using the fact that $\ln x \leq x-1$ but i couldnt solve this, any help?

REPLY [0 votes]: Since as you say, $\ln x\le x-1$, we know that for $x>0,$ $\ln\sqrt x\le \sqrt x-1$, that is, $\frac{\ln x}x\le \frac1{2x}(\sqrt x-1).$ All that is left is using $0\le \frac{\ln x}x\le \frac1{2x}(\sqrt x-1)$ and the squeeze theorem.