text:
\section{Introduction}

Szemer\'edi's regularity lemma \cite{Sz76} is one of the most powerful tools in graph theory. Szemer\'edi \cite{Sz75} used an early version in the proof of his celebrated theorem on long arithmetic progressions in dense subsets of the integers. Roughly speaking, the regularity lemma says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost every pair of parts is random-like.

To state Szemer\'edi's regularity lemma requires some terminology. Let $G$ be a graph, and $X$ and $Y$ be (not necessarily disjoint) vertex subsets. Let $e(X,Y)$ denote the number of pairs vertices $(x,y) \in X \times Y$ that are edges of $G$. The {\it edge density} $d(X,Y)= e(X,Y) / (|X||Y|)$ between $X$ and $Y$ is the fraction of pairs in $X \times Y$ that are edges. The pair $(X,Y)$ is {\it $\epsilon$-regular} if for all $X' \subseteq X$ and $Y' \subseteq Y$ with $|X'| \geq \epsilon|X|$ and $|Y'| \geq \epsilon |Y|$, we have $|d(X',Y')-d(X,Y)|<\epsilon$. Qualitatively, a pair of parts is $\epsilon$-regular with small $\epsilon$ if the edge densities between pairs of large subsets are all roughly the same. A vertex partition $V=V_1 \cup \ldots \cup V_k$ is {\it equitable} if the parts have size as equal as possible, that is we have $||V_i|-|V_j|| \leq 1$ for all $i,j$. An equitable vertex partition with $k$ parts is {\it $\epsilon$-regular} if all but $\epsilon k^2$ pairs of parts $(V_i,V_j)$ are $\epsilon$-regular. The regularity lemma states that for every $\epsilon>0$ there is a (least) integer $K(\epsilon)$ such that every graph has an $\epsilon$-regular equitable vertex partition into at most $K(\epsilon)$ parts.

Arguably the main drawback of Szemer\'edi's regularity lemma is that the proof gives an enormous upper bound $K(\epsilon)$ on the number of parts, namely an exponential tower of twos of height $O(\epsilon^{-5})$. That such a huge bound is indeed necessary was an open problem for many years until Gowers \cite{Gow97} proved a lower bound on $K(\epsilon)$ which is an exponential tower of twos of height $\Omega(\epsilon^{-1/16})$. Further results by Conlon and Fox \cite{CF12} determine the dependence on the number of irregular pairs and a simpler proof of Gowers' result was obtained by Moshkovitz and Shapira \cite{MS15}. The first two authors \cite{FL} determine the tower height up to a constant factor in a version of the regularity lemma (see Section \ref{sec:equitable} for details). In this version, we show in Section \ref{sec:equitable} that the requirement that the partition is equitable has a negligible effect on the number of parts (up to changing the regularity parameter a little bit).

Due to the many applications of the regularity lemma, there has been a great deal of research on developing algorithmic versions of the regularity lemma and its applications (see the survey by Koml\'os and Simonovits \cite{KoSi}). We would like
to be able to find an $\epsilon$-regular partition of a graph on $n$ vertices in time polynomial in $n$. Szemer\'edi's original proof of the regularity lemma was not algorithmic. The reason for this is that it needs to be able to check if a pair of parts is $\epsilon$-regular, and if not, to use subsets of the parts that realize this. This is problematic because it is shown in \cite{ADLRY} that determining whether a given pair of parts is $\epsilon$-regular is co-NP-complete. They use this to show that checking whether a given partition is $\epsilon$-regular is co-NP-complete.

However, Alon, Duke, Lefmann, R\"odl, and Yuster \cite{ADLRY} show how to find, if a given pair of vertex subsets of size $n$ are not $\epsilon$-regular, a pair of subsets which realize that the pair is not $\epsilon^4/16$-regular. The running time is $O_\epsilon(n^{\omega+o(1)})$, where $\omega < 2.373$ is the matrix multiplication exponent (multiplying two $n \times n$ matrices in $n^{\omega+o(1)}$ time) \cite{CW90,LeGall14}. Here we use the subscript $\epsilon$ to mean that the hidden constants depend on $\epsilon$. Finding a pair of subsets of vertices that detect irregularity is the key bottleneck for the algorithmic proof of the regularity lemma. It was shown \cite{ADLRY} that one can find an $\epsilon$-regular partition with the number of parts at most an exponential tower of height $O(\epsilon^{-20})$ in an $n$-vertex graph in time $O_\epsilon(n^{\omega+o(1)})$. Thus, the following surprising fact holds: while checking whether a given partition is $\epsilon$-regular is co-NP-complete, finding an $\epsilon$-regular partition can be done in polynomial time.

Frieze and Kannan \cite{FK99} later found a simple algorithmic proof of the regularity lemma based on a spectral approach. Using expander graphs, Kohayakawa, R\"odl, and Thoma \cite{KRT} gave a faster algorithmic regularity lemma with optimal running time of $O_\epsilon(n^2)$. Alon and Naor \cite{AN06} develop an algorithm which approximates the cut norm of a graph within a factor $0.56$ using Grothendieck's inequality and apply this to find a polynomial time algorithm which finds, for a given pair of vertex subsets of order $n$ which is not $\epsilon$-regular, a pair of subsets which realize that the pair is not $\epsilon^3/2$-regular. They further observe that their approach gives an improvement on the tower height in the algorithmic regularity lemma to $O(\epsilon^{-7})$.

However, due to the tower-type dependence for the number of parts on the regularity parameter, these are not practical algorithms. While most graphs have a small regularity partition, the previous algorithmic proofs would not necessarily find it and would only guarantee to find a regular partition with a tower-type number of parts. Addressing this issue, Fischer, Matsliah, and Shapira \cite{EMS10} give a probabilistic algorithm which runs in constant time (depending on $\epsilon$ and $k$) which with high probability finds, in a graph which has an $\epsilon/2$-regular partition with $k$ parts, an $\epsilon$-regular partition with at most $k$ parts (implicitely defined). Tao \cite{Taoeps2} gives a probabilistic algorithm which with high probability in constant time (depending on $\epsilon$) produces an $\epsilon$-regular partition. The algorithm takes a random sample of vertices (the exact number of which is also random) and outputs the common refinement of the neighborhoods of these vertices.

Still, it is desirable to have a fast {\it deterministic} algorithm for finding a regularity partition, which we obtain here. We give several deterministic approximation algorithms for these co-NP-complete problems.

\begin{theorem} \label{thm:partition}
There exists an $O_{\epsilon,\alpha, k}(n^2)$ time algorithm, which, given $0<\epsilon,\alpha<1$ and $k$, and a graph $G$ on $n$ vertices that admits an equitable $\epsilon$-regular partition with $k$ parts, outputs an equitable $(1+\alpha)\epsilon$-regular partition of $G$ into $k$ parts.
\end{theorem}

In other words, if a graph has a regular partition with few parts, then we can quickly find a regular partition (losing very slightly on the regularity) with the same number of parts. In particular, we obtain an algorithmic regularity lemma which is optimal in terms of the number of parts as it is exactly the same as in the non-algorithmic version (with a very slight loss on the regularity parameter).

We also give an approximation algorithm for checking whether a given pair of vertex subsets is $\epsilon$-regular, in the sense that if the pair is not $\epsilon$-regular, then we can algorithmically find a pair of vertex subsets that witness that its failure to be $(1-\alpha)\epsilon$-regular. We will formulate this in terms of regularity of bipartite graphs. We say that bipartite graph $G$ with bipartition $(X,Y)$ is $\epsilon$-regular if the pair $(X,Y)$ is $\epsilon$-regular.

\begin{theorem}\label{thm:pair}
There exists an $O_{\epsilon,\alpha}(n^2)$ time algorithm, which, given $\epsilon,\alpha>0$, and a bipartite graph $G$ between vertex sets $X$ and $Y$, each of size at most $n$, outputs one of the following:
\begin{enumerate}
\item Correctly states that $G$ is $\epsilon$-regular;
\item Finds a pair of vertex subsets $U \subseteq X$ and $W \subseteq Y$ which realize that $G$ is not $(1-\alpha)\epsilon$-regular, i.e., $|U| \ge (1 - \alpha)\epsilon |X|$, $|W| \ge (1-\alpha)\epsilon |Y|$, and $|d(U,W) - d(X,Y)| > (1-\alpha)\epsilon$.
\end{enumerate}
\end{theorem}

Using this result, by checking the regularity of each pair of parts in a partition, we have the following corollary.

\begin{corollary}\label{cor:distinguish}
Given $\epsilon,\alpha>0$, we can distinguish in time $O_{\epsilon,\alpha}(n^2)$ between an $\epsilon$-regular partition and a partition which is not $(1-\alpha)\epsilon$-regular.
\qed
\end{corollary}

\begin{remark}
In Theorems \ref{thm:partition} and \ref{thm:pair} and Corollary \ref{cor:distinguish}, the dependence of the running time on the parameters $\epsilon,\alpha,k$ may be improved at the cost of worsening the dependence on $n$ from $n^2$ to $n^{\omega+o(1)}$. This is because we use the recent algorithmic version of the Frieze--Kannan weak regularity lemma due to Dellamonica, Kalyanasundaram, Martin, R\"odl, and Shapira \cite{DKMRS12}, \cite{DKMRS15}. In the more recent paper \cite{DKMRS15}, they develop an $O_\epsilon(n^2)$ algorithm for finding a weak $\epsilon$-regular partition, but it has a double exponential in $1/\epsilon$ constant factor dependence. The older paper \cite{DKMRS12} has the advantage of not having this poor dependence on the regularity parameter. See Section \ref{sec:algo-weak-reg} for more information.
\end{remark}

Counting the number of copies of a graph $H$ in another graph $G$ is a famous problem in algorithmic graph theory. For example, a special case of this problem is to determine the clique number, the size of the largest clique, in a graph. This is a well-known NP-complete problem. In fact, H\r{a}stad \cite{Has} and Zuckerman \cite{Zuck} proved that it is NP-hard  to approximate the clique number of a $n$-vertex graph within a factor $n^{1-\epsilon}$ for any $\epsilon>0$.

There is a fast {\it probabilistic} algorithm for approximating up to $\epsilon$ the fraction of $k$-tuples which make a copy of $H$. The algorithm takes $s=10\epsilon^{-2}$ samples of $k$-tuples of vertices uniformly at random from $G$ and outputs the fraction of them that make a copy of $H$. The number of copies of $H$ is a binomial random variable with standard deviation at most $s^{1/2}/2$, and hence the fraction of $k$-tuples which make a copy of $H$ in this random sample is likely within $\epsilon$ of the fraction of $k$-tuples which makes copies of $H$. However, this algorithm has no guarantee of success. It is therefore desirable to have a {\it deterministic}  algorithm for counting copies which gives an approximation for the subgraph count with complete certainty.

The algorithmic regularity lemma is useful for deterministically approximating the number of copies of any fixed graph in a graph. Indeed, the counting lemma shows that if $k$ parts $V_1,\ldots,V_k$ are pairwise regular, then the number of copies of a graph $H$ with $k$ vertices with the copy of the $i$th vertex in $V_i$ is close to what is expected in a random graph with the same edge densities between the pairs of parts. Adding up over all $k$-tuples of parts in an $\epsilon$-regular partition and noting that almost all $k$-tuples of parts have all its pairs $\epsilon$-regular, we get an algorithm which runs in time $O_{\epsilon,k}(n^2)$ which computes the number of copies of a graph $H$ on $k$ vertices in a graph on $n$ vertices up to an additive error of $\epsilon n^k$. The major drawback with this result is the tower-type dependence on $\epsilon$ and $k$, which comes from the number of parts in the regularity lemma.

Duke, Lefmann, and R\"odl \cite{DLR} gave a faster approximation algorithm for the number of copies of $H$ in a graph $G$. They first develop a weak regularity lemma which has an exponential dependence instead of a tower-type
dependence. This gives an algorithm which runs in time $2^{(k/\epsilon)^{O(1)}}n^{\omega + o(1)}$ which computes the number of copies of a graph $H$ on $k$ vertices in a graph on $n$ vertices up to an additive error of $\epsilon n^k$.

In Section \ref{sec:counts}, we will use the algorithmic version of the Frieze--Kannan weak regularity lemma \cite{DKMRS12} to get the following even faster approximation algorithm for the subgraph counting problem. It improves the previous exponential dependence on the error parameter to a polynomial dependence. Here $v(H)$ and $e(H)$ denote the number of vertices and and edges in $H$, respectively.

\begin{theorem}\label{thm:countingalgthm}
Let $H$ be a graph, and let $\epsilon>0$ be given. There is a deterministic algorithm that runs in time $O_H(\epsilon^{-O(1)} n^{\omega+o(1)} + \epsilon^{- O(e(H))} n)$, and finds the number of copies of $H$ in $G$ up to an error of at most $\epsilon n^{v(H)}$.
\end{theorem}

For example, we can count the number of cliques of order $1000$ in an $n$-vertex graph up to an additive error $n^{1000-10^{-6}}$ in time $O(n^{2.4})$.

\medskip

In the final section of the paper, we turn our attention to a regularity lemma for permutations. Cooper \cite{Coo06} proved a permutation regularity lemma which was later refined by Hoppen, Kohayakawa, and Sampaio \cite{HKS12}. In Section \ref{sec:perm-reg}, we give a new short proof of the permutation regularity lemma, improving the number of parts from tower-type to single exponential, and further extend it to an interval regularity lemma for graphs and matrices.

\section{Equitable partitions with small irregularity}
\label{sec:equitable}

Let $G$ be a graph, and $X$ and $Y$ be (not necessarily disjoint) vertex subsets.
The \emph{irregularity} of the pair $X,Y$ is defined as
\[
\irreg(X,Y) =
\max_{U \subseteq X, W \subseteq Y}\bigl |e(U,W)-|U||W|d(X,Y)\bigr|.
\]
The \emph{irregularity} of a partition $\mathcal{P}$ of the vertex set of $G$ is defined to be
\[\irreg(\mathcal{P})=\sum_{X,Y \in \mathcal{P}}\irreg(X,Y).
\]
One version of Szemer\'edi's regularity lemma \cite[Lemma 2.2]{LS07} states that given any $\epsilon$, one can find an $M(\epsilon)$ such that any graph $G$ has a partition into at most $M(\epsilon)$ parts with irregularity at most $\epsilon |V|^2$. The proof of the regularity lemma gives $M(\epsilon) \le \tower(O(\epsilon^{-2}))$, and we now know that this is essentially tight \cite{Gow97},\cite{CF12},\cite{FL}, in the sense that $M(\epsilon) = \tower(\Theta(\epsilon^{-2}))$ \cite{FL}. Here the tower function is defined by $\tower(1)=2$ and $\tower(k+1)=2^{\tower(k)}$.

We say that a partition is \emph{equitable} if any two parts differ in size by at most one. It is a convenient property to have in a regularity partition. The main result of this section shows that for any vertex partition, one can refine it a bit further to obtain a partition which is close to an equitable partition whose irregularity is not substantially larger.

\begin{theorem} \label{thm:mainequi}
	Let $0 < \alpha < 1/2$, and $m$ be a positive integer, and let $G$ be a graph on $n \ge 10^8 m\alpha^{-5}$ vertices.
	If $\mathcal{P}$ is a vertex partition of $G$ into $m$ parts, then there is an equitable vertex partition $\mathcal{Q}$ of $G$ into at most $4m/\alpha$ parts such that $\irreg(\mathcal{Q}) \leq  \irreg(\mathcal{P}) + \alpha n^2$.
\end{theorem}

Let $M_{eq}(\epsilon)$ be the smallest $M$ such that, for any graph $G = (V,E)$, there is an equitable partition into at most $M$ parts with total irregularity is at most $\epsilon |V|^2$. We have $M_{eq}(\epsilon) \geq M(\epsilon)$ trivially. As a consequence of Theorem \ref{thm:mainequi}, we show directly that adding the condition that the partition is equitable has a very small effect on the size of the smallest partition with small irregularity.

\begin{theorem} \label{thm:equinotmuchmore}
Let $0<\epsilon <1$ and  $0<\alpha < 1/2$. We have $M_{eq}(\epsilon+\alpha) \leq  \alpha^{-O(1)}M(\epsilon)$.
\end{theorem}

In particular, taking $\alpha$ small but not too small, such as $\alpha=2^{-1/\epsilon}$, we see that the tower height in Szemer\'edi's regularity lemma is not significantly affected by adding the equitability requirement.

Note that Theorem~\ref{thm:mainequi} also applies to graphs $G$ whose number of parts in the regularity partition is not  as large as the worst case $M(\epsilon)$. To prove Theorem \ref{thm:mainequi}, we randomly divide each part of the partition $\mathcal{P}$ into parts of (essentially) equal size (apart from a small remaining subset), and then arbitrarily partition the relatively few remaining vertices into parts of equal size to obtain an equitable partition. We show that this works with high probability.

As a first step, the following lemma shows that with high probability, a pair of random subsets $X',Y'$ of a pair of parts $X,Y$ induces roughly the same subgraph density as $X$ and $Y$.

\begin{lemma}
\label{lem:random-subsets-preserve-density}
Let $X$ and $Y$ be vertex subsets of a graph $G$. Let $X' \subseteq X$ and $Y' \subseteq Y$ be picked uniformly at random with $|X'| = |Y'|=k$. Then
\[
\mathbb{P}\left( | d(X',Y')-d(X,Y)| < \delta \right) \ge 1 - 2e^{-\delta^2k/4}.
\]
\end{lemma}

\begin{proof}
Consider picking the vertices of $X'$ and $Y'$ one at the time, starting with the ones in $X'$. Let $Z_0,\ldots,Z_{2k}$ be the martingale where $Z_i$ is the expected value of $e(X',Y')$ conditioned on knowing the first $i$ vertices already chosen (this is sometimes referred to as the vertex-exposure martingale). We have $|Z_{i}-Z_{i-1}| \leq k$ as the choice of each vertex in $X'$ and $Y'$ changes the final $e(X',Y')$ by at most $k$.
By the Azuma--Hoeffding inequality (see Chapter 7 of Alon and Spencer \cite{AlSp}),
\[
\mathbb{P}\left( |Z_{2k}-Z_0| \geq t \right) \leq 2 e^{-t^2/(4k^3)}.
\]
We have $Z_0= k^2 d(X,Y)$ and $Z_{2k}=e(X',Y')$.
Set $t=\delta k^2$, we obtain
\[
\mathbb{P}\left( | e(X',Y')- k^2 d(X,Y) | \geq \delta k^2 \right) \leq 2e^{-\delta^2 k / 4}.
\]
Noting that $e(X',Y') = k^2d(X',Y')$, the lemma follows.
\end{proof}

The next lemma show that the irregularity parameter remains roughly the same when restricted to a random, much smaller, subset of vertices. Recall that the cut metric $d_\square$ between two graphs $G$ and $H$ on the same vertex set $V = V(G) = V(H)$ is defined by
\[
d_\square(G,H) := \max_{U,W \subseteq V} \frac{|e_G(U,W) - e_H(U,W)|}{|V|^2}.
\]
When $G$ and $H$ are bipartite graphs on $V = X \cup Y$, we define the cut metric as
\[
d_\square(G,H) := \max_{U \subseteq X, W \subseteq Y} \frac{|e_G(U,W) - e_H(U,W)|}{|X||Y|}.
\]
We also use the same notation for edge-weighted graphs, where $e(U,W)$ denotes the sum of weights of all edges in $U \times W$.

\begin{lemma}\label{lem:random-subsets-preserve-irreg}
Let $X,Y$ be vertex subsets of a graph $G$. Let $X' \subseteq X$ and $Y' \subseteq Y$ be picked uniformly at random with $|X'|=|Y'|=k$. Then with probability at least $1 - 6e^{-\sqrt{k}/10}$,
\begin{equation}
	\label{eq:irreg-diff}
	\left| \frac{\irreg(X',Y')}{k^2}-\frac{\irreg(X,Y)}{|X||Y|} \right| \le \frac{9}{k^{1/4}},
\end{equation}
\end{lemma}

\begin{proof}
We use the so-called First Sampling Lemma \cite[Theorem 2.10]{BCLSV08} (we quote the statement from \cite[Lemma 10.5]{Lov}): if $G$ and $H$ are weighted graphs with $V(G) = V(H)$ and edge weights in $[0,1]$, and $S \subseteq V(G)$ is chosen uniformly at random with $|S| = k$, then with probability at least $1 - 4 e^{-\sqrt{k}/10}$,
\[
\left| d_\square(G[S], H[S]) - d_\square(G, H) \right| \le \frac{8}{k^{1/4}}.
\]
Let $G[X,Y]$ denote the bipartite (weighted) graph with vertex sets $X$ and $Y$, and whose edges are induced from $G$. A bipartite version of this sampling lemma holds true, that with probability at least $1 - 4 e^{-\sqrt{k}/10}$,
\begin{equation}
\label{eq:sampling-lemma}
\left| d_\square(G[X',Y'], H[X',Y']) - d_\square(G[X,Y], H[X,Y]) \right| \le \frac{8}{k^{1/4}},
\end{equation}
and its proof is nearly identical to the first version stated above. Note that
\[
\irreg(X, Y) = |X||Y| d_\square(G[X,Y], d(X, Y)),
\]
where the second argument denotes the complete graph with loops with all edge weights equal to $d(X,Y)$. Similarly,
\[
\irreg(X',Y') = k^2 d_\square(G[X',Y'], d(X', Y')).
\]
By letting $H$ in \eqref{eq:sampling-lemma} be the complete graph with loops and all edge weights $d(X, Y)$, we obtain that with probability at least $1 - 4 e^{-\sqrt{k}/10}$,
\[
\left| \frac{\irreg(X',Y')}{k^2}-\frac{\irreg(X,Y)}{|X||Y|} \right|  \le \frac{8}{k^{1/4}} + |d(X, Y) - d(X', Y')|.
\]
We then apply Lemma~\ref{lem:random-subsets-preserve-density} with $\delta = 1/k^{1/4}$ to reach the desired conclusion.
\end{proof}

As a corollary of Lemma~\ref{lem:random-subsets-preserve-density}, and noting that the LHS of \eqref{eq:irreg-diff} is at most 1, we have
\begin{equation} \label{eq:irreg-subset-upper-bound}
	\mathbb{E} \left( \frac{\irreg(X',Y')}{k^2} \right)
	\le \frac{\irreg(X,Y)}{|X||Y|} + \frac{9}{k^{1/4}} + 6e^{-\sqrt{k}/10}
	\le \frac{\irreg(X,Y)}{|X||Y|} + \frac{20}{k^{1/4}}.
\end{equation}

\begin{proof}[Proof of Theorem \ref{thm:mainequi}]
We shall omit floors and ceilings for the sake of clarity of presentation. Let $k = \alpha n/(4m)$. Let $V_1,\ldots,V_m$ be the parts of $\mathcal{P}$. Uniformly at random partition each $V_i$ into parts of size $k$, with possibly one remainder part of size less than $k$. Call $\mathcal{P}'$ be the resulting partition.

By \eqref{eq:irreg-subset-upper-bound},\footnote{It is easy to modify the proof to address the case when $X'$ and $Y'$ are within the same part of $\mathcal{P}$.}
\begin{align*}
	\mathbb{E}\Biggl(\sum_{\substack{X',Y' \in \mathcal{P}' \\ |X'| = |Y'| = k}} \irreg(X',Y')\Biggr)
	&\le
	\sum_{X,Y \in \mathcal{P}} \left(\irreg(X,Y) + \frac{20}{k^{1/4}}|X||Y| \right)
	\\
	&\le \irreg(\mathcal{P}) + \frac{20n^2}{k^{1/4}}.
\end{align*}
So there exists some such partition $\mathcal{P}'$ such that
\begin{equation} \label{eq:irreg-sum}
	\sum_{\substack{X',Y' \in \mathcal{P}' \\ |X'| = |Y'| = k}} \irreg(X',Y')
	\le \irreg(\mathcal{P}) + \frac{20n^2}{k^{1/4}}.
\end{equation}
Fix $\mathcal{P}'$ to be this partition.

Let $S$ be the union of the parts of $\mathcal{P}'$ of size less than $k$.
There is at most one such part of $\mathcal{P}'$ for each $V_i$, so $|S| < mk$.
Arbitrarily partition $S$ into sets of size $k$, and let $\mathcal{Q}$ be the equitable vertex partition consisting of these parts of $S$ along with the parts of $\mathcal{P}'$ of size $k$.

Parts arising from $S$ contributes at most $2|S|n < 2mkn$ to $\irreg(\mathcal{Q})$, whereas the other contributions to $\irreg(\mathcal{Q})$ are bounded by \eqref{eq:irreg-sum}. Thus
\[
\irreg(\mathcal{Q}) \le \irreg(\mathcal{P}) + \frac{20n^2}{k^{1/4}} + 2mkn
\le \irreg(\mathcal{P}) + \alpha n^2,
\]
where the last step follows from
\[
\frac{20}{k^{1/4}} = \frac{20(4m)^{1/4}}{(\alpha n)^{1/4}} \le \frac{20(4m)^{1/4}}{(\alpha \cdot 10^{8} m\alpha^{-5})^{1/4}} < \frac{\alpha}{2}
\]
and
\[
\frac{2mk}{n} = \frac{2m}{n}\frac{\alpha n}{4m} \le \frac{\alpha}{2}.
\]
Therefore $\mathcal{Q}$ is the required equipartition.
\end{proof}

As a consequence of Theorem \ref{thm:mainequi}, we can prove Theorem \ref{thm:equinotmuchmore}.

\begin{proof}[Proof of Theorem \ref{thm:equinotmuchmore}]
Let $G$ be a graph with a partition $\mathcal{P}$ of the vertex set into $m \le  M(\epsilon)$ parts with irregularity at most $\epsilon n^2$. If $n < 10^{8} m \alpha^{-5}$, then we just partition the vertices into singleton sets, which has zero irregualarity, using at most $10^{8} m \alpha^{-5} \le 10^{8} \alpha^{-5} M(\epsilon)$ parts.
Otherwise apply Theorem~\ref{thm:mainequi}  to obtain a partition with irregularity at most $(\epsilon+\alpha)n^2$, and at most $4m/\alpha \le 4\alpha^{-1} M(\epsilon)$ parts.
\end{proof}

\section{Algorithmic weak regularity}
\label{sec:algo-weak-reg}

In this section, we review some results concerning algorithmic versions of the Frieze--Kannan weak regularity lemma. We will be applying these results in subsequent sections.

Given any edge-weighted graph $G$ and any partition $\mathcal{P} \colon V = V_1 \cup V_2 \cup \dots \cup V_t$ of the vertex set of $G$ into $t$ parts, let $G_\mathcal{P}$ denote the weighted graph with vertex set $V$ obtained by giving weight $d_{ij} := d(V_i,V_j) = e(V_i,V_j)/(|V_i||V_j|)$ to all pairs of vertices in $V_i \times V_j$, for every $1 \le i \le j \le t$. We say $\mathcal{P}$ is an \emph{$\epsilon$-regular Frieze--Kannan} (or \emph{$\epsilon$-FK-regular}) partition if $d_\square(G,G_\mathcal{P})\le \epsilon$. In other words, $\mathcal{P}$ is an $\epsilon$-regular Frieze--Kannan partition if
\begin{equation} \label{eq:FK-pair}
\left\lvert e(S,T) - \sum_{i,j=1}^t d_{ij} |S \cap V_i||T \cap V_j| \right\rvert \le \epsilon |V|^2.
\end{equation}
for all $S,T \subseteq V$. We say that sets $S$ and $T$ \emph{witness} that $\mathcal{P}$ is not $\epsilon$-FK-regular if the above inequality is violated.

Frieze and Kannan~\cite{FK99a} proved the following regularity lemma.

\begin{theorem}[Frieze--Kannan]
Let $\epsilon > 0$. Every graph has an $\epsilon$-regular Frieze--Kannan partition with at most $2^{2/\epsilon^2}$ parts.
\qed
\end{theorem}

We apply efficient deterministic algorithms for generating Frieze--Kannan regular partitions. Such algorithms were recently given in \cite{DKMRS12,DKMRS15} by Dellamonica et al. Specifically, in \cite{DKMRS12}, the authors gave an $\epsilon^{-6} n^{\omega+o(1)}$ time algorithm to generate an equitable $\epsilon$-regular Frieze--Kannan partition of a graph on $n$ vertices into at most $2^{O(\epsilon^{-7})}$ parts. Recall that $\omega < 2.373$ is the matrix multiplication exponent. In \cite{DKMRS15} a different algorithm was given which improved the dependence of the running time on $n$ from $O_\epsilon(n^{\omega+o(1)})$ to $O_\epsilon(n^2)$, while sacrificing the dependence of $\epsilon$. Namely, it was shown that there is a deterministic algorithm that finds, in $O(2^{2^{\epsilon^{-O(1)}}} n^2)$ time, an $\epsilon$-regular Frieze--Kannan partition into at most $2^{\epsilon^{-O(1)}}$ parts. It remains an open problem to improve the dependence on $\epsilon$ in the running time.

The proof of the Frieze--Kannan regularity lemma and its algorithmic versions, roughly speaking, run as follows:
\begin{itemize}
	\item Given a partition (starting with the trivial partition with one part), either it is $\epsilon$-FK-regular (in which case we are done), or we can exhibit some pair of subsets $S,T$ of vertices that witness the irregularity by violating \eqref{eq:FK-pair} (in the algorithmic versions, one may only be guaranteed to find $S$ and $T$ that violate \eqref{eq:FK-pair} for some smaller value of $\epsilon$).
	\item Refine the partition by using $S$ and $T$ to split each part into at most four parts, thereby increasing the total number of parts by a small factor.
	\item Repeat. Use a mean-square-density increment argument to upper bound the number of possible iterations.
\end{itemize}

\begin{remark}
As in the case of the usual regularity lemma, it is possible to obtain an equitable partition in the Frieze--Kannan regularity lemma, increasing the number of parts by a factor of at most 4. We will not need this for our algorithm, however.
\end{remark}

For example, in the algorithmic version \cite{DKMRS12}, the first step (also the key step) is given as the following result \cite[Corollary 3.1]{DKMRS12}.

\begin{theorem}\label{thm:DKMRS12-pair}
There is an $n^{\omega+o(1)}$-time algorithm which, given $\epsilon > 0$, an $n$-vertex graph $G$ and a partition $\mathcal{P}$ of $V (G)$, does one of the following:
\begin{enumerate}
\item Correctly states that $\mathcal{P}$ is $\epsilon$-FK-regular;
\item Finds sets $S$, $T$ which witness the fact that $\mathcal{P}$ is not $\epsilon^3 /1000$-FK-regular. \qed
\end{enumerate}
\end{theorem}

In \cite{DKMRS15}, an alternative theorem is given for finding an irregular pair. The statement below is a consequence of \cite[Theorem 8.1]{DKMRS15}.

\begin{theorem}\label{thm:DKMRS15-pair}
There is an $O(2^k n^2)$-time algorithm which, given $\epsilon > 0$, an $n$-vertex graph $G$ and a partition $\mathcal{P}$ of $V (G)$ into $k$ parts, does one of the following:
\begin{enumerate}
\item Correctly states that $\mathcal{P}$ is $\epsilon$-FK-regular.
\item Finds sets $S$, $T$ which witness the fact that $\mathcal{P}$ is not $\epsilon^{O(1)}$-FK-regular.  \qed
\end{enumerate}
\end{theorem}

\medskip

There is a variant of the weak regularity lemma, where the final output is not a partition of $V$ into $2^{\epsilon^{-O(1)}}$ parts, but rather an approximation of the graphs as a sum of $\epsilon^{-O(1)}$ complete bipartite graphs each assigned some weight. Below by \emph{weighted graph} we mean a graph with edge-weights. For $S,T \subseteq V$, by $K_{S,T}$ we mean the weighted graph where an edge $\{s,t\}$ has weight 1 if $s \in S$ and $t \in T$ (and weight 2 if $s,t \in S \cap T$) and weight zero otherwise. For any $c \in \mathbb{R}$, by $c G$ we mean the weighted graph obtained from $G$ by multiplying every edge-weight by $c$. For a pair of weighted graphs $G_1,G_2$ on the same set of vertices, we will use the notation $G_1+G_2$ to denote the graph on the same vertex set with edge weights summed (and weight $0$ corresponding to not having an edge). Additionally, we write $c$ to mean the constant graph with all edge-weights equal to $c$.

\begin{theorem}[Frieze--Kannan] \label{thm:FK-overlay}
Let $\epsilon > 0$. Let $G$ be any weighted graph with $[-1,1]$-valued edge weights. There exists some $k \le O(\epsilon^{-2})$, subsets $S_1, \dots, S_k, T_1, \dots, T_k \subseteq V$, and $c_1, \dots, c_k \in [-1,1]$, so that
\[
d_\square(G, d(G) + c_1K_{S_1, T_1} + \dots + c_k K_{S_k,T_k}) \le \epsilon.
\]
\qed
\end{theorem}

See \cite[Lemma 4.1]{LS07} for a proof (given there in a more general setting of arbitrary Hilbert spaces). Roughly speaking, to find the appropriate $S_i, T_i, c_i$, in the second step of the above outline of the proof of the weak regularity lemma, instead of using $S$ and $T$ to refine the existing partition, we subtract $c K_{S,T}$ from the remaining weighted graph (starting with $G$), where $c$ is the density between $S$ and $T$ in the remaining weighted graph. We record the corresponding $S_i, T_i, c_i$ in step $i$ of this iteration. We can bound the number of iterations by observing that the $L^2$ norm of $G - d(G) - c_1K_{S_1,T_1} - \dots - c_iK_{S_i,T_i}$ must decrease by a certain amount at each step.

As for the algorithmic version, using Theorems~\ref{thm:DKMRS12-pair} and \ref{thm:DKMRS15-pair} (or minor modifications thereof), we can efficiently approximate $G$ as a weighted sum of $\epsilon^{-O(1)}$ complete bipartite graphs.

\begin{corollary} \label{cor:reg-sum}
There exists a
$\min\{ \epsilon^{-O(1)}n^{\omega+o(1)}, O(2^{2^{\epsilon^{-O(1)}}}n^2) \}$
time algorithm which, given $\epsilon > 0$ and an $n$-vertex graph $G$, outputs subsets $S_1, \dots, S_k, T_1, \dots, T_k \subseteq V(G)$ and real numbers $c_1, \dots, c_k$, for some $k \le \epsilon^{-O(1)}$, such that
\[
d_\square(G, d(G) + c_1K_{S_1, T_1} + \dots + c_k K_{S_k,T_k}) \le \epsilon.
\]
\qed
\end{corollary}

We will use a variation for bipartite graphs.

\begin{corollary} \label{cor:reg-sum-bip}
There exists a
$\min\{ \epsilon^{-O(1)}n^{\omega+o(1)}, O(2^{2^{\epsilon^{-O(1)}}}n^2) \}$
time algorithm which, given $\epsilon > 0$ and a bipartite graph $G$ between vertex sets $X$ and $Y$ each with at most $n$ vertices, outputs subsets $S_1, \dots, S_k \subseteq X$ and $T_1, \dots, T_k \subseteq Y$ and real numbers $c_1, \dots, c_k$, for some $k \le \epsilon^{-O(1)}$, such that
\[
d_\square(G, d(X,Y) + c_1K_{S_1, T_1} + \dots + c_k K_{S_k,T_k}) \le \epsilon,
\]
where the constant $d(X,Y)$ here denotes the weighted complete bipartite graph $d(X,Y) K_{X,Y}$.
\qed
\end{corollary}

\section{Approximation algorithm for subgraph counts}
\label{sec:counts}

Suppose that we are given a graph $G$ on $n$ vertices, and we would like to find the number of copies of a small graph $H$ on $k$ vertices that are contained in $G$. We would like to count them up to an error at most $\epsilon n^k$. In this section, we will provide a deterministic algorithm that can do so. Specifically, we prove Theorem~\ref{thm:countingalgthm}, reproduced below for convenience.

\begin{theorem*}
Let $H$ be a graph, and let $\epsilon>0$ be given. There is a deterministic algorithm that runs in time $O_H(\epsilon^{-O(1)} n^{\omega+o(1)} + \epsilon^{- O(e(H))} n)$, that finds the number of copies of $H$ in $G$ up to an error of at most $\epsilon n^{v(H)}$.
\end{theorem*}

It will be cleaner to work instead with $\hom(H, G)$, the number of graph homomorphisms from $H$ to $G$. This quantity differs from the number of (labeled) copies of $H$ in $G$ by a negligible $O(n^{v(H)-1})$ additive error (the hidden constants here and onward may depend on $H$). We extend the definition of $\hom(H,G)$ to edge-weighted graphs $G$: if the edge $xy$ in $G$ has weight $G(x,y)$, then we define
\[
\hom(H,G)=\sum_{f:V(H) \rightarrow V(G)} \prod_{\{u,v\} \in E(H)}G(f(u),f(v)).
\]
Note that here $G(x,y)$ is defined on all pairs, with $G(x,y)=0$ if there is no edge between $x$ and $y$.

The idea is to apply a weak regularity lemma in the form of Corollary~\ref{cor:reg-sum}. A weakly regular approximation also gives an approximation of $H$-count, via a standard counting lemma (see \cite[Lemma 10.22]{Lov}):

\begin{lemma}[Counting lemma]\label{lem:counting}
Given any graph $H$ and any two weighted graphs $G_1$ and $G_2$ on the same set $V$ of $n$ vertices, we have
\[
|\hom(H, G_1) - \hom(H, G_2)| \le e(H) d_\square(G_1, G_2) n^{v(H)}.
\]
\qed
\end{lemma}

Here is the algorithm. Apply Corollary~\ref{cor:reg-sum} to find any approximation
\[
G' = d(G) + c_1K_{S_1, T_1} +\dots + c_k K_{S_k,T_k}
\]
of $G$ with $d_\square(G,G') \le \epsilon/e(H)$ and $k \le \epsilon^{-O(1)}$. By the counting lemma, it suffices to compute
\begin{equation} \label{eq:hom-expand}
\hom(H,G') = \hom(H, d(G) + c_1K_{S_1, T_1} +\dots + c_k K_{S_k,T_k}),
\end{equation}
which can be done in $O_H(k^{e(H)}n)$ time, as follows. We can expand the right-hand side of \eqref{eq:hom-expand} via the distributive property, writing
\begin{equation} \label{eq:hom-expand-distr}
\hom(H,G') = \sum_{\varphi \colon E(H) \to \{0, \dots, k\}} \hom^\varphi(H, (d(G), c_1K_{S_1,T_1},\dots, c_kK_{S_k,T_k}))
\end{equation}
where for each assignment $\varphi \colon E(H) \to \{0, \dots, k\}$ of edges of $H$ to the components of $G'$ we write $\hom^\varphi(H, (G_0, G_1, \dots, G_k))$ to mean the homomorphism count obtained where the image of each edge $e \in E(H)$ is restricted to $G_{\varphi(e)}$, i.e.,
\[
\hom^\varphi(H, (G_0, G_1, \dots, G_k))
= \sum_{f \colon V(H) \to [n]} \prod_{uv \in E(H)} G_{\varphi(uv)}(f(u),f(v)).
\]
Here by $G_i(x,y)$ we mean the edge-weight of $(x,y)$ in $G_i$.

There are $(k+1)^{e(H)}$ possible maps $\varphi$. We claim that each term on the right-hand side of \eqref{eq:hom-expand-distr}, corresponding to some $\varphi$, can be exactly computed in $O_H(n)$ time. Taking out constant factor, it remains to compute the value of $\hom^\varphi(H, (1, K_{S_1, T_1},\dots, K_{S_k,T_k}))$. We further decompose each $K_{S_i,T_i}$ (viewed as an adjacency matrix) as a sum $1_{S_i \times T_i} + 1_{T_i \times S_i}$ and apply the distributive property once again to expand the quantity as a sum of $2^{e(H)}$ terms. Each term counts the number of maps $f \colon V(G) \to [n]$ such that, for every $v \in V(H)$, $f(v) \in \bigcap_{e \in E(H)} R_{\varphi(e)}$ for some choice of $R_{\varphi(e)} = S_{\varphi(e)}$ or $T_{\phi(e)}$. The size of such an intersection can be computed in $O_H(n)$ time, and we can compute this term (one of $2^{e(H)}$ terms) by multiplying over all $v \in V(H)$.
There are $2^{e(H)}$ choices for which summand in $1_{S_i \times T_i} + 1_{T_i \times S_i}$ to take in the expansion over all $i$, and by summing over all $2^{e(H)}$ choices, we can evaluate $\hom^\varphi(H, (1, K_{S_1, T_1},\dots, K_{S_k,T_k}))$. By summing over all $\varphi$ in~\eqref{eq:hom-expand-distr}, we see that $\hom(H,G')$ can be exactly computed in $O_H(k^{e(H)} n)$ time, thereby providing the desired approximation to $\hom(H,G)$.

As for the running time, it took $\epsilon^{-O(1)}n^{\omega+o(1)}$ time to find the approximation $G'$, and it took $O_H(k^{e(H)}n) = O_H(\epsilon^{-O(e(H))}n)$ time to compute $\hom(H, G')$, giving the claimed total running time.

\section{Finding an irregular pair}

In this section, we prove Theorem~\ref{thm:pair}, reproduced below for convenience.

\begin{theorem*}
There exists an $O_{\epsilon,\alpha}(n^2)$ time algorithm, which, given $\epsilon,\alpha>0$, and a bipartite graph $G$ between vertex sets $X$ and $Y$, each of size at most $n$, outputs one of the following:
\begin{enumerate}
\item Correctly states that $G$ is $\epsilon$-regular;
\item Finds a pair of vertex subsets $U \subseteq X$ and $W \subseteq Y$ which realize that $G$ is not $(1-\alpha)\epsilon$-regular, i.e., $|U| \ge (1 - \alpha)\epsilon |X|$, $|W| \ge (1-\alpha)\epsilon |Y|$, and $|d(U,W) - d(X,Y)| > (1-\alpha)\epsilon$.
\end{enumerate}
\end{theorem*}

We can assume that $\alpha<1/2$ since for larger $\alpha$ we can just apply the algorithm with a lower value of $\alpha$. We shall give an $O(2^{2^{(\alpha\epsilon)^{-O(1)}}} n^2)$-time algorithm. Using Corollary~\ref{cor:reg-sum-bip}, we approximate $G$ by $G' = d(G) + c_1K_{S_1,T_1} + \dots c_k K_{S_k,T_k}$ so that $k = (\alpha\epsilon)^{-O(1)}$ and $d_\square(G,G') \le \alpha\epsilon^3/4$. Here $S_1, \dots, S_k \subseteq X$ and $T_1, \dots, T_k \subseteq Y$.  We shall assume that $k$ is small compared to $|X|$ and $|Y|$, namely,
\begin{equation} \label{eq:k-small}
	100 \cdot k2^k \le \alpha \epsilon^3 \min\{|X|,|Y|\},
\end{equation}
for otherwise  we can accomplish the task by a complete search (say when $|X| \le |Y|$) over all subsets of $X$ in $2^{O(|X|)} = 2^{O(\alpha^{-1}\epsilon^{-3}k2^k)} = 2^{2^{(\alpha\epsilon)^{-O(1)}}}$ time, which is enough.

We say that a sequence of numbers $u, u_1, \dots, u_k, w, w_1, \dots, w_k$ is \emph{feasible} if there exists a function $\mu \colon \colon X \cup Y \to [0,1]$ (we write $\mu(S) = \sum_{x \in S} \mu(x)$ from now on) such that  the following quantities
\[
\frac{|\mu(X) - u|}{|X|}, \frac{|\mu(Y) - w|}{|Y|},
 \frac{|\mu(S_i) - u_i|}{|X|}, \frac{|\mu(T_i) - t_i|}{|Y|}, \text{ for all } 1 \le i \le k,
\]
are each at most $\alpha \epsilon^3 / (100 k)$. One can think of $\mu$ as representing subsets $U \subseteq X$ and $W \subseteq Y$ with $[0,1]$-valued weights attached to its elements. One can determine via a linear program if a given sequence is feasible (see Lemma~\ref{lem:feasible-LP} below).

Here is the algorithm. We perform a complete search through all sequences $u, u_1, \dots, u_k, w, w_1, \dots, w_k$ of nonnegative integers at most $n$, where $u$ and each $u_i$ are divisible by $\lfloor \alpha \epsilon^3 |X| / (100 k) \rfloor$, and $w$ and each $w_i$ are divisible by $\lfloor \alpha \epsilon^3 |Y| / (100 k) \rfloor$. For each such sequence, we check if it is feasible, and if so then we check whether the inequalities
\begin{equation} \label{eq:surrogate-reg}
\left| \sum_{i=1}^k c_i u_i w_i \right| > (1 - \alpha/2)\epsilon u w, \quad
u \ge (1-\alpha/2)\epsilon |X|, \quad  \text{and }
w \ge (1-\alpha/2)\epsilon |Y|
\end{equation}
hold. If they never hold for any feasible sequence, then we state that $G$ is $\epsilon$-regular. On the other hand, if they hold for some feasible sequence, then we can convert $f$ into actual sets $U$ and $W$ (as we shall explain) that witness that $G$ is not $(1-\alpha)\epsilon$-regular.

Next we prove the correctness of the algorithm if the output is that $G$ is $\epsilon$-regular.

Consider the partition of $X$ given by the common refinement by $S_1, \dots, S_k$. For any index set $I \subseteq [k]$, let $S_I = (\bigcap_{i \in I} S_i) \cap (\bigcap_{i \notin I} (X \setminus S_i))$ denote the part in the common refinement indexed by $I$. We can compute the sizes $|S_I|$ for all $I \subseteq [k]$ in $O(2^k n)$ time. With this information at hand:

\begin{lemma} \label{lem:feasible-LP}
There exists a $2^{O(k)}$ time algorithm that determines whether a given sequence $u$, $u_1, \dots, u_k$, $w$, $w_1, \dots, w_k$ is feasible.
\end{lemma}

\begin{proof}
It suffices to show that one can determine in the required time whether there exists $\mu \colon X \to [0,1]$ such that $|\mu(X) -u| \le a$ and $|\mu(S_i) - u_i| \le a_i$, for each $i$. Here $a = a_i = \lfloor \alpha\epsilon^3n/(100k)\rfloor$ is the required bound (though it could be chosen arbitrarily for the purpose of this lemma). The situation for $Y$ is analogous.

For the purpose of satisfying the inequalities $|\mu(X) -u| \le a$ and $|\mu(S_i) - u_i| \le a_i$, one only needs to know the sum of values of $\mu$ on parts in the partition of $X$ induced by the common refinement of $S_1, \dots, S_k$.

For each $I \subseteq [k]$, the variable $x_I$ is supposed to correspond to the value of $\mu(S_I)$. Then $\mu$ exists if and only if there exists $(x_I)_{I \subseteq [k]} \in \mathbb{R}^{2^k}$ satisfying the following inequalities:
\begin{align*}
	-a \le \left(\sum_{I \subseteq [k]} x_I\right) - u \le a, & \\
	-a_i \le \left(\sum_{I \ni i} x_I \right) - u_i \le a_i &\qquad \text{ for all } i \in [k], \\
	\text{and}\qquad
	0 \le x_I \le |S_I| &\qquad \text{ for all } I \subseteq [k].
\end{align*}
This is a linear program in $2^k + 1$ variables, which can be solved in $2^{O(k)}$ time. The original sequence is feasible if and only if the above system of linear inequalities has some solution in $(x_I)$.
\end{proof}

Suppose the algorithm does not find any feasible sequence satisfying \eqref{eq:surrogate-reg}. We claim that $G$ is $\epsilon$-regular. Assume otherwise. Then there exist $U \subseteq X$ and $W \subseteq Y$ such that $|U| \ge \epsilon|X|$, $|W| \ge \epsilon|Y|$, and $|d(U,W) - d(X,Y)| > \epsilon$. Since
$d_\square(G, G') \le \alpha\epsilon^3/4$, we have
$|e_G(U,W) - e_{G'}(U,W)| \le (\alpha \epsilon^3/4) |X||Y|$. Thus
\begin{align*}
|e_{G'}(U,W) - d_G(X,Y)|U||W||
&\ge |e_G(U,W) - d_G(X,Y)|U||W|| - |e_G(U,W) - e_{G'}(U,W)| \\
&\ge |d_G(U,W) - d_G(X,Y)||U||W| - \tfrac14 \alpha \epsilon^3 |X||Y| \\
&\ge \epsilon |U||W| - \tfrac14 \alpha \epsilon |U||W| \\
&\ge (1 - \tfrac14\alpha) \epsilon|U||W|.
\end{align*}
On the other hand, since $G' = d_G(X,Y) + c_1 K_{S_1, T_1} + \dots + c_k K_{S_k,T_k}$, we have
\[
e_{G'}(U,W) - d_G(X,Y)|U||W|
= \sum_{i=1}^k c_i |U \cap S_i| |W \cap T_i|.
\]
So
\[
\left|\sum_{i=1}^k c_i |U \cap S_i| |W \cap T_i|\right| \ge (1 - \tfrac14\alpha) \epsilon|U||W|.
\]
Let $u$ and $u_i$ be $|U|$ and $|U \cap S_i|$, each respectively rounded to the nearest integer multiple of $\lfloor \alpha \epsilon^3 |X| /(100k)\rfloor$, for all $1 \le i \le k$. Similarly let $w, w_i$ be $|W|$ and $|W \cap S_i|$, each respectively rounded to the nearest integer multiple of $\lfloor \alpha \epsilon^3 |Y| /(100k)\rfloor$, for all $1 \le i \le k$. The sequence $u, u_1, \dots, u_k, w, w_1, \dots, w_k$ is feasible as witnessed by $\mu = 1_{U \cup W}$. We claim that \eqref{eq:surrogate-reg} holds. Indeed, we have
\[
u \ge |U| - \tfrac{1}{100} \alpha\epsilon^3 |X| \ge (1 - \tfrac{1}{100} \alpha\epsilon^2)\epsilon |X|,
\]
and
\[
w \ge |W| - \tfrac{1}{100} \alpha\epsilon^3 |Y|
\ge (1 - \tfrac{1}{100} \alpha\epsilon^2)\epsilon |Y|.
\]
Furthermore, we have
\begin{align*}
\left| \sum_{i=1}^k c_i u_i w_i \right|
&\ge \left|\sum_{i=1}^k c_i |U \cap S_i| |W \cap T_i|\right| - \tfrac3{100} \alpha\epsilon^3 |X||Y|
\\
&\ge (1 - \tfrac14\alpha) \epsilon|U||W| - \tfrac3{100} \alpha\epsilon^3 |X||Y|
\\
&\ge (1 - \tfrac14\alpha - \tfrac3{100} \alpha) \epsilon|U||W|
\\
&\ge (1 - \tfrac14 \alpha - \tfrac{3}{100}\alpha) \epsilon ( 1 + \tfrac{1}{100} \alpha\epsilon^2)^{-2} uw
\\
&> (1 - \tfrac12 \alpha) \epsilon uw.
\end{align*}
The first inequality above follows from the fact that for each $i$, \[|u_i-|U \cap S_i|| \le \frac{\alpha \epsilon^3 |X|}{100k},\] \[|u_i-|U \cap S_i|| \le \frac{\alpha \epsilon^3 |Y|}{100k},\] and thus \[\left|u_iw_i-|U \cap S_i||W \cap T_i|\right| \le \frac{3\alpha\epsilon^3 |X||Y|}{100k}.\] The penultimate inequality follows from $u \le |U| + \tfrac1{100} \alpha \epsilon^3 |X| \le (1 + \tfrac1{100} \alpha\epsilon^2)|U|$ and similarly with $w$.
So we have a feasible sequence satisfying \eqref{eq:surrogate-reg}, which is a contradiction.

\medskip

Now suppose instead that the algorithm does find some feasible sequence that satisfies \eqref{eq:surrogate-reg}. By adjusting $\mu$, we may assume that $\mu$ takes $\{0,1\}$-value on all but at most one element in each part in the common refinement partition of $X$ by $S_1, \dots, S_k$, and likewise in $Y$ by $T_1, \dots, T_k$. Let $U \subseteq X$ and $W \subseteq Y$ denote the elements where $\mu$ is positive, we have
\[
	||U| - u| \le \frac{\alpha\epsilon^3}{100k}|X| + 2^k \le \frac{\alpha\epsilon^3}{50k}|X|
\]
Here the extra $2^k$ term account for rounding up non-integral values of $\mu$. We used the assumption \eqref{eq:k-small} to bound $2^k$.
It thus follows from above, and \eqref{eq:surrogate-reg} that
\begin{align*}
|U| &\ge (1 - \tfrac12 \alpha - \tfrac{1}{50k}\alpha\epsilon^2)\epsilon |X| \ge (1 - \alpha)\epsilon|X|.
\end{align*}
In particular, this means that
\[
	||U| - u| \le \frac{\alpha\epsilon^3}{50k}|X| \le \frac{\alpha\epsilon^2}{(1-\alpha)50k}|U|.
\]
Similarly, we have
\[|W| \ge (1 - \tfrac12 \alpha - \tfrac{1}{50k}\alpha\epsilon^2)\epsilon |Y| \ge (1 - \alpha)\epsilon|Y|,\]
and we have
\[
	||U \cap S_i| - u_i| \le \frac{\alpha\epsilon^2}{(1-\alpha)50k}|U|,
	\quad \text{for all }1 \le i \le k,
\]
and
\[
	||W| - w|\le \frac{\alpha\epsilon^2}{(1-\alpha)50k}|W|,
	\quad \text{ and } \quad
	||W \cap T_i| - w_i|
	\le \frac{\alpha\epsilon^2}{(1-\alpha)50k}|W|,
	\quad \text{for all }1 \le i \le k.
\]
and
\begin{align*}
|d_G(U,W) - d_G(X,Y)|
&\ge |d_{G'}(U,W) - d_G(X,Y)| - |d_{G}(U,W) - d_{G'}(U,W)|
\\
&\ge \frac{1}{|U||W|}\left|\sum_{i=1}^k c_i |U \cap S_i||W \cap T_i| \right|
- \frac{|X||Y|}{|U||W|}d_\square(G,G')
\\
&\ge \frac{1}{|U||W|}\left(\left|\sum_{i=1}^k c_i u_i w_i\right| - \frac{3}{(1-\alpha)50}\alpha\epsilon^2|U||W| )\right) - \frac{1}{4}\alpha\epsilon^3 \frac{|X||Y|}{|U||W|}
\\
&\ge \frac{1}{|U||W|}\left(\left(1-\frac{\alpha}{2}\right)\epsilon u w - \frac{3}{(1-\alpha)50}\alpha\epsilon^2 |U||W| )\right) - \frac{1}{4}\alpha\epsilon
\\&
\ge (1-\alpha)\epsilon.
\end{align*}
Hence the pair $(U,W)$ witnesses that $G$ is not $(1-\alpha)\epsilon$-regular.

\medskip

We will need the following easy corollary of Theorem~\ref{thm:pair} for the next section.

\begin{corollary} \label{cor:check-partition-regular}
There exists an $O_{\epsilon,\alpha,k}(n^2)$ time algorithm, which, given $\epsilon,\alpha,k>0$, a graph $G$ on $n$ vertices, and a partition $\mathcal{P}$ of the vertex set of $G$ into $k$ parts, does one of the following:
\begin{enumerate}
\item Correctly states that $\mathcal{P}$ is $(1+\alpha)\epsilon$-regular;
\item Correctly states that $\mathcal{P}$ is not $\epsilon$-regular.
\end{enumerate}
\end{corollary}

Note that sometimes both options are correct. The algorithm that we give runs in $O(k^2 2^{2^{(\alpha\epsilon)^{-O(1)}}}n^2)$ time.

\begin{proof}
Let $\mathcal{P}$ be the partition of $V$ into $V_1, \dots, V_k$. Apply the algorithm in Theorem~\ref{thm:pair} to each pair $V_i, V_j$ so that it either correctly states that $(V_i, V_j)$ is $(1+\alpha)\epsilon$-regular or that it is not $\epsilon$-regular. If at least a $(1-\epsilon)$-fraction of pairs are seen to be $(1+\alpha)\epsilon$-regular, then we know that $\mathcal{P}$ is $(1+\alpha)\epsilon$-regular, otherwise, more than an $\epsilon$-fraction of pairs fail to be $\epsilon$-regular, so that $\mathcal{P}$ is not $\epsilon$-regular.
\end{proof}

\section{Approximating regularity}

In this section, we prove Theorem~\ref{thm:partition}, reproduced below for convenience.

\begin{theorem*}
There exists an $O_{\epsilon,\alpha, k}(n^2)$ time algorithm, which, given $0<\epsilon,\alpha<1$ and $k$, and a graph $G$ on $n$ vertices that admits an equitable $\epsilon$-regular partition with $k$ parts, outputs an equitable $(1+\alpha)\epsilon$-regular partition of $G$ into $k$ parts.
\end{theorem*}

Here is the algorithm, which runs in $O(2^{2^{(k/(\alpha\epsilon))^{O(1)}}}n^2)$ time. Using Corollary~\ref{cor:reg-sum}, we find $S_1, \dots, S_s,$ $T_1, \dots, T_s \subseteq V$, with $s \le (k/\alpha\epsilon)^{O(1)}$, such that $d_\square(G,G') \le \alpha\epsilon/(10k^2)$, where
\[
G' = d(G) + c_1 K_{S_1, T_1} + \dots c_k K_{S_s,T_s}.
\]
Let $\mathcal{Q}$ denote the partition of $V(G)$ given by the common refinement of the sets $S_1, \dots, S_s, T_1, \dots, T_s$. Let $\mathcal{Q}$ have $r \le 4^s$ parts, with sizes $q_1, \dots, q_r$. We shall search over all tuples $(q_{i,j})_{1 \le i \le r, 1 \le j \le k}$ of nonnegative integers satisfying all of the following requirements:
\begin{itemize}
	\item $q_i = q_{i,1} + \dots q_{i,k}$ for each $1 \le i \le r$;
	\item each $q_{i,j}$ with $j < k$ is divisible by $\lfloor \alpha\epsilon n/(25rk) \rfloor$ (no divisibility requirements for $q_{i,k}$); and
	\item the sums $\sum_{i=1}^r q_{i,j}$ for different values of $j$ differ from $n/k$ by at most $\alpha\epsilon n/(50k)$.
\end{itemize}
For each eligible tuple $(q_{i,j})$, consider a partition $\mathcal{P}: V = V_1 \cup \dots \cup V_k$ where $Q_i \cap V_j = q_{i,j}$ (there are many such partitions; pick an arbitrary one). Apply Corollary~\ref{cor:check-partition-regular} to certify that either $\mathcal{P}$ is $(1+3\alpha/4)\epsilon$-regular or not $(1+\alpha/2)\epsilon$-regular. It turns out that the latter option cannot always be true for all $\mathcal{P}$ searched, as we assume that $G$ admits some $\epsilon$-regular partition with $k$ parts (we will justify this claim). From this search, we find a $(1+3\alpha/4)\epsilon$-regular partition $\mathcal{P}$ which is almost equitable in the sense that its parts have sizes differing from $n/k$ by at most $\alpha\epsilon n/(50k)$. We modify $\mathcal{P}$ by moving a minimum number of vertices to make it equitable. We claim that the resulting partition is $(1+\alpha)\epsilon$-regular.

\medskip

We next analyze the running time of this algorithm. Corollary~\ref{cor:reg-sum} takes  $O(2^{2^{(k/(\alpha\epsilon))^{O(1)}}}n^2)$ time to find the cut norm decomposition. The number of tuples $(q_{i,j})$ is at most $(25rk\alpha^{-1}\epsilon^{-1})^{kr} \le 2^{2^{(k/(\alpha\epsilon))^{O(1)}}}$. For each $(q_{i,j})$, the algorithm in Corollary~\ref{cor:check-partition-regular} takes $O(k^2 2^{2^{(\alpha\epsilon)^{-O(1)}}}n^2)$ time. Therefore, the entire algorithm takes $O(2^{2^{(k/(\alpha\epsilon))^{O(1)}}}n^2)= O_{\alpha,\epsilon,k}(n^2)$ time.

Now we verify correctness. We shall prove the following claims, which together imply the result. Indeed, (1) shows that the algorithm always finds some $(1+3\alpha/4)\epsilon$-regular partition $\mathcal{P}$, and (2) shows that making $\mathcal{P}$ equitable by moving a minimum number of vertices between parts results in a $(1+\alpha)\epsilon$-regular partition.
\begin{enumerate}
	\item If a partition $\mathcal{P}=\{V_1,V_2,...,V_k\}$ of $V$ is $\epsilon$-regular, then we can modify it slightly to obtain $\mathcal{P}'=\{V_1',V_2',...,V_k'\}$ such that $q_{i,j}=|Q_i \cap V_j'|$ form an eligible tuple, and $\mathcal{P}'$ is $(1+\alpha/2)\epsilon$-regular for $G$ (so the search would not pass over this $(q_{i,j})$).
	\item If a partition $\mathcal{P}$ of $V$ is $(1+3\alpha/4)\epsilon$-regular for $G$, then by modifying $\mathcal{P}$ by adding or deleting at most $\alpha\epsilon n/(50k)$ vertices from each part, the resulting partition is $(1+\alpha)\epsilon$-regular.
\end{enumerate}

In order to show these claims, we first establish a few simple lemmas.

\begin{lemma}\label{prevlem1}
Let $X$, $X'$, $Y$ be vertex subsets of a graph with $X \subset X'$ and $|X| \geq (1-\delta)|X'|$. Then $|d(X',Y)-d(X,Y)| \leq \delta$.
\end{lemma}
\begin{proof}
We have the identity $$d(X',Y)-d(X,Y)=\frac{e(X' \setminus X,Y)+e(X,Y)}{|X' \setminus X||Y| +|X||Y|}-\frac{e(X,Y)}{|X||Y|}=\left(d(X' \setminus X,Y)-d(X,Y)\right)\frac{|X' \setminus X|}{|X'|}.$$ The lemma follows from noting that densitites are between $0$ and $1$ and $|X' \setminus X| \leq \delta |X'|$.
\end{proof}

Recall that $A \Delta B := (A \setminus B) \cup (B \setminus A)$ denotes the symmetric difference between $A$ and $B$.

\begin{lemma}\label{prevlem2}
If $U$, $U'$, $W$, $W'$ are vertex subsets of a graph with $|U \Delta U'| \leq \delta |U \cup U'|$ and $|W \Delta W'| \leq \delta |W \cup W'|$, then $|d(U,W)-d(U',W')| \leq 2 \delta$.
\end{lemma}
\begin{proof}
It suffices to prove the lemma in the case $W=W'$ and with the bound $2\delta$ replaced by $\delta$. Indeed, the lemma would then follow by applying this case twice and the triangle inequality. By the triangle inequality and applying Lemma \ref{prevlem1} twice with $X'=U \cup U'$, first with $\delta_1=\frac{|U \cup U'| - |U|}{|U \cup U'|}$ and then with $\delta_2=\frac{|U \cup U'| - |U'|}{|U \cup U'|}$, and finally using $\delta_1+\delta_2 = \frac{|U \Delta U'|}{|U \cup U'|} \leq \delta$, we have
$$|d(U,W)-d(U',W)|\leq |d(U,W)-d(U \cup U',W)|+|d(U \cup U',W)-d(U',W)| \leq \delta_1+\delta_2 \leq \delta.$$
\end{proof}

\begin{lemma}
Suppose $(V_1,V_2)$ is an $\epsilon$-regular pair of vertex subsets of a graph. Suppose we modify them slightly to $V_1'$ and $V_2'$, with $|V_i \Delta V_i'| \le \delta \epsilon |V_i|$ for $i=1,2$. Then $V_1'$ and $V_2'$ are $\epsilon+4\delta$-regular.
\end{lemma}

\begin{proof}

Clearly we may assume that $\epsilon+4\delta \le 1$. Let $U' \subseteq V'_1$ and $W' \subseteq V'_2$ with $|U'| \ge (\epsilon+4\delta)|V'_1|$ and $|W'| \ge (\epsilon+4\delta)|V'_2|$. Let $U = U' \cap V_1$ and $W = W' \cap V_2$.
Then we have
\begin{multline*} |U|=|U'|-|U'\setminus V_1| \ge |U'|-|V_1' \setminus V_1| \ge (\epsilon+4\delta)|V_1'|-\delta \epsilon|V_1| \ge \\(\epsilon+4\delta)(|V_1|-\delta \epsilon |V_1|) - \delta \epsilon|V_1|= \epsilon|V_1|+4\delta |V_1|-(1+\epsilon + 4 \delta)\delta\epsilon|V_1| \ge \epsilon|V_1|. \end{multline*}
Similarly $|W| \ge \epsilon |V_2|$. Thus by the regularity of the pair $(V_1,V_2)$, we have
\[|d(U,W) - d(V_1,V_2)| \le \epsilon.\]
Now, we have that
\[|U \Delta U'| \le \delta \epsilon |V_1| \le \delta|U| \le \delta |U \cup U'|,\]
 and similarly $|W \Delta W'| \le \delta |W \cup W'|$, and thus $|d(U,W)-d(U',W')|\le 2\delta$ by Lemma \ref{prevlem2}. Similarly $|d(V'_1,V'_2) - d(V_1,V_2)| \le 2\delta \epsilon \le 2 \delta$. By the triangle inequality, we have $|d(U',W') - d(V'_i,V'_j)|  \le \epsilon + 4\delta$, showing that $(V'_i,V'_j)$ is $(\epsilon + 4\delta)$-regular.
\end{proof}

As a corollary, we have the following:

\begin{corollary}
Let $0<\epsilon,\delta<1$. Let $G$ be a graph with $n$ vertices. Let $\mathcal{P}$ be a partition of $V(G)$ into $k$ parts, with each part having size at least $n/(2k)$. Suppose that $\mathcal{P}$ is $\epsilon$-regular for $G$. If we modify $\mathcal{P}$ by adding or deleting at most $\delta \epsilon |V|/k$ vertices from each part of $\mathcal{P}$, then the resulting partition is $(\epsilon + 8\delta)$-regular for $G$.
\end{corollary}

\begin{proof}
Indeed, for any part $V_i$ of $\mathcal{P}$, if we let $V_i'$ be its modification, then $|V_i \Delta V_i'| \le \delta \epsilon |V|/k \le 2 \delta \epsilon |V_i|$. This means that if a pair $(V_i,V_j)$ was $\epsilon$-regular, then after the modification it is  $(\epsilon+8\delta)$-regular, and so the proportion of pairs that are not $\epsilon+8\delta$-regular is at most $\epsilon \le \epsilon+8\delta$.
\end{proof}

Now we prove claim (1) above. Let $\mathcal{P}$ be an equitable $\epsilon$-regular partition of $G$. Since $d_\square(G,G') \le \alpha\epsilon/(10k^2)$, $\mathcal{P}$ is $(1 + \alpha/10)\epsilon$-regular for $G'$. In $G'$, edges between the same parts of $\mathcal{Q}$ have equal weights, and we can take $\mathcal{P}'$ such that $|Q_i \cap V_j|$ differs from $|Q_i \cap V'_j|$ by at most $\alpha\epsilon n/(50rk)$ for each $i,j$. This means that $\mathcal{P}'$ can be taken so that $V_j$ and $V_j'$ differ by at most $\alpha \epsilon n/(50k)$ for each $j$, so it follows from the lemma above that $\mathcal{P}'$ is $(1 + 3\alpha/10)\epsilon$-regular for $G'$. Therefore, $\mathcal{P}'$ must be $(1+\alpha/2)\epsilon$-regular for $G$.

The claim (2) follows immediately from the corollary above.

\section{Permutation regularity lemma}
\label{sec:perm-reg}

In this section we give a new proof of a regularity lemma for permutations that requires fewer parts than previous results in literature. To define regular partitions for permutations, it is natural to state it as a special case in a more general setting for matrices.

Let $Y = (y_{ij})$ be a $n \times n$ matrix. We use \emph{interval} to
mean a subset of $[n]$ of consecutive
integers. For any intervals $I, J$ of $[n]$, we write
\[
d_Y(I, J) := \frac{1}{|I||J|} \sum_{i \in I, j \in J} y_{ij}.
\]

\begin{definition}
  Let $Y$ be a $n \times n$ square matrix. Let $I, J
  \subseteq [n]$ be intervals. We say that $(I, J)$ is \emph{interval
    $\epsilon$-regular} for $Y$ if for all subintervals $A \subseteq I$
  and $B \subseteq J$ with $|A| \geq \epsilon |I|$ and $|B| \ge \epsilon
  |J|$ one has
  \[
  |d_Y(A, B) - d_Y(I, J)| \le \epsilon.
  \]
  Let $\mathcal{P}$ be a partition of $[n]$ into $k$ intervals. We say that
  $\mathcal{P}$ is interval \emph{$\epsilon$-regular} for $Y$ if all except at most
  $\epsilon k^2$ pairs of intervals $(I, J)$ of $\mathcal{P}$ are
  interval $\epsilon$-regular for $Y$.
\end{definition}

\begin{definition}
  We say that $\mathcal{P}$ is an \emph{equipartition} of $[n]$ if every
  pair of parts in $\mathcal{P}$
  differ in size by at most one.
\end{definition}

Here is the regularity lemma for interval regular partitions.

\begin{theorem}[Interval regularity lemma] \label{thm:int-reg-matrix} For every $\epsilon > 0$
  and positive integer $m$ there is some $M = m^{O(1)}
  \epsilon^{-O(\epsilon^{-5})} $ with the
  following property. For every $n \in \mathbb{N}$, and $n \times n$ matrix
  $Y = (y_{ij})$ with $[0,1]$-valued entries, there is some integer $k
  \in [m, M]$ so that every equipartition of $[n]$ into $k$
  intervals is interval $\epsilon$-regular for $Y$.
\end{theorem}

\begin{remark}
If $n \le M$, then we can take the partition of $[n]$ into singletons. Otherwise, our proof will show that one can pick $k$ from a small set of choices: one can take $k = mq^i$, where $q = \lceil 16\epsilon^{-3} \rceil$ and $0 \le i < \lceil 4\epsilon^{-5} \rceil$ is some integer.
\end{remark}

Theorem~\ref{thm:int-reg-matrix} has the following immediate
consequence for permutation regularity. Given a permutation $\sigma \colon [n] \to [n]$, associate to it the
$n\times n$
matrix $Y^{\sigma}$ defined by
\[
y_{ij} = \begin{cases} 1 & \text{if } \sigma(i) < j \\
  0 & \text{otherwise}.
\end{cases}
\]
A partition of $[n]$ into
  intervals is said
  to be \emph{$\epsilon$-regular} for $\sigma$ if it is interval $\epsilon$-regular for
  the associated matrix $Y^\sigma$.

\begin{theorem}[Permutation regularity lemma]
  \label{thm:perm-reg-lemma}
  For every $\epsilon > 0$ and positive integer $m$, there exist
  $M = m^{O(1)} \epsilon^{-O(\epsilon^{-5})}$ with the following property. Let $n \neq n_0$ and $\sigma$
  be a permutation of $[n]$. Then for some integer $k \in [m, M]$,
  every equitable partition of $[n]$ into $k$ intervals is
  $\epsilon$-regular for $\sigma$.
  \qed
\end{theorem}

An early form of this permutation regularity lemma was first proved by
Cooper~\cite{Coo06}. The above form was proved in \cite{HKS12} with $M$ being a
tower exponential of height $O(\epsilon^{-5})$. Our version requires a much smaller $M$.

\subsection{Interval regular partitions for functions}

We first prove the interval regularity lemma for functions. It is
somewhat cleaner to work with partitions of the real interval $[0,1]$ into
exactly equal-length subintervals, instead of equitable partitions of $[n]$. The measure theoretic approach has the slight advantage that it allows us to defer divisibility issues of $n$ until the end.

Let $f \colon [0,1]^2 \to [0,1]$ be a measurable function. For any
intervals $I, J \subseteq[0,1]$ we write
\[
d_f(I, J) := \frac{1}{\lambda(I)\lambda(J)} \int_{I \times J} f(x,y)
\, dxdy.
\]
Here $\lambda$ denotes the Lebesgue measure.

\begin{definition}
  Let $f \colon [0,1]^2 \to [0,1]$ be a measurable function. Let $I, J
  \subseteq [0,1]$ be intervals. We say that $(I, J)$ is
  \emph{interval $\epsilon$-regular} for $f$ if for all subintervals $A
  \subseteq I$ and $B \subseteq J$ with $\lambda(A) \ge \epsilon
  \lambda(I)$ and $\lambda(B) \ge \epsilon \lambda(J)$ one has
  \[
  |d_f(A, B) - d_f(I, J)| \le \epsilon.
  \]

  Let $\mathcal{P}$ a partition of $[0,1]$ into $k$ intervals. We say that
  $\mathcal{P}$ is \emph{interval $\epsilon$-regular} for $f$ if all except at most $\epsilon k^2$
  pairs of intervals $(I, J)$ of $\mathcal{P}$ are interval
  $\epsilon$-regular for $f$.
\end{definition}

\begin{theorem} \label{thm:int-reg-function} For every $\epsilon > 0$
  and positive integer $m$ there is some $M =
  m\epsilon^{-O(\epsilon^{-5})}$ with the following property. For
  every measurable function $f \colon [0,1]^2 \to [0,1]$, there is
  some integer $k \in [m, M]$ such that the partition of $[0,1]$
  into $k$ equal-length intervals  $[0, 1/k) \cup [1/k, 2/k) \cup \dots \cup [(k-1)/k,1]$ is interval $\epsilon$-regular for $f$.
\end{theorem}

\begin{remark}
In Theorem~\ref{thm:int-reg-function}, it is possible to take $k = mq^i$, where $q = \lceil 16\epsilon^{-3} \rceil$ and $0 \le i < \lceil 4\epsilon^{-5} \rceil$ is some integer.
\end{remark}

Before proving Theorem~\ref{thm:int-reg-function}, we first prove a
lemma showing that the density $d_f(A, B)$ does not change very much
if $A$ and $B$ are changed only slightly.

\begin{lemma} \label{lem:density-diff}
  Let $f \colon [0,1]^2 \to [0,1]$ be a measurable function. For any
  intervals $A,
  A', B, B' \subseteq [0,1]$ we have
  \[
  |d_f(A, B) - d_f(A', B')| \leq \frac{2 \lambda((A \times B) \Delta
    (A' \times B'))}{\lambda(A)\lambda(B)}.
  \]
\end{lemma}

\begin{proof}
By the triangle inequality,
\begin{align*}
&\lambda(A)\lambda(B) |d_f(A,B) - d_f(A',B')|
\\
&\le
\left| \lambda(A) \lambda(B) d_f(A, B) - \lambda(A') \lambda(B') d_f(A',
  B') \right| + d_f(A',B') |\lambda(A)\lambda(B) -
\lambda(A')\lambda(B')|
\\&\le \left|\int_{A \times B} f\,d\lambda - \int_{A' \times B'}
  f\,d\lambda\right| +   |\lambda(A)\lambda(B) -
\lambda(A')\lambda(B')|
\\&\le 2\lambda((A \times B) \Delta (A' \times B')).
\end{align*}
\end{proof}

The bound in Lemma \ref{lem:density-diff} can be improved by a factor $2$ by following the proof of Lemma \ref{prevlem2}.

\begin{proof}[Proof of Theorem~\ref{thm:int-reg-function}]
  Let $f_k$ denote the function obtained from $f$ by replacing its
  value inside each box $[i/k, (i+1)/k) \times [j/k, (j+1)/k)$ by its
  average inside that box, i.e.,
  \[
  f_k(x,y) := k^2 \int_{\left[ \frac{i}{k}, \frac{i+1}{k} \right) \times \left[ \frac{j}{k}, \frac{j+1}{k} \right)} f \,d\lambda \qquad \text{if
  } (x,y) \in \left[ \frac{i}{k}, \frac{i+1}{k} \right) \times \left[ \frac{j}{k}, \frac{j+1}{k} \right)
  \]
  for $i, j = 0,1, \dots, k-1$ (when $i$ or $j$ equals $k-1$, the
  corresponding interval should be modified to be closed on the
  right). Write
  \[
  \|f\|_2 := \left(\int_{[0,1]^2} |f|^2 \,d\lambda\right)^{1/2}
  \]
  for the $L^2$ norm.

  Let $q = \lceil 16 \epsilon^{-3} \rceil$. Consider the sequence
  $
  f_m, f_{mq}, f_{mq^2}, \dots$.
  Since $0 \leq \|f_k\|_2 \leq 1$
  for all $k$, there exists some $k = mq^i$ for $0 \le i < \ceil{4\epsilon^{-5}}$ such that
  \begin{equation} \label{eq:f_kq-f_k}
    \|f_{kq}\|_2^2 \le \|f_k\|_2^2 + \frac{\epsilon^5}{4}.
  \end{equation}
  We will show that the partition of $[0,1]$ into $k$ equal-length intervals
  is interval $\epsilon$-regular. Indeed, if this were not the case, then there
  exists more than $\epsilon k^2$ irregular pairs of intervals $(I,
  J)$, where $I = [i/k, (i+1)/k)$ and $J = [j/k, (j+1)/k)$ for some
  integers $i$ and $j$. Due
  to the irregularity, there exist subintervals $A \subseteq I$ and $B
  \subseteq J$ such that $\lambda(A) \ge \epsilon \lambda(I)$,
  $\lambda(B) \ge \epsilon \lambda(J)$, and
  \begin{equation} \label{eq:int-reg-func-discrep}
  |d_f(I, J) - d_f(A, B)| > \epsilon.
\end{equation}
Let $A'$ be the smallest interval containing $A$ with both ends
  being multiples of $1/(kq)$. Note that $A' \subseteq I$. Similarly
  define $B'$. We see that $A' \times B'$ contains $A \times B$, and
  the difference in area is at most $4/(k^2q)$. By
  Lemma~\ref{lem:density-diff},
  \[
  |d_f(A, B) - d_f(A', B')| \leq \frac{2 (4/(k^2q))}{(\epsilon/k)^2} =
  \frac{8}{q\epsilon^2} = \frac{8}{\lceil 16 \epsilon^{-3}\rceil \epsilon^2} \le \frac{\epsilon}{2}.
  \]
By \eqref{eq:int-reg-func-discrep} we have
\[
|d_f(I, J) - d_f(A', B')| > \frac{\epsilon}{2}.
\]
Since the endpoints of $I$ and $J$ are multiples of $1/k$ and those of $A'$
and $B'$ are multiples of $1/(kq)$, the function $f_k - f_{kq}$ has average value $d_f(I, J) - d_f(A',
B')$ over the box $A' \times B'$. So the contribution to $\|f_k - f_{kq}\|_2^2$ from $A' \times
B'$ is at least $\lambda(A') \lambda(B') (\epsilon/2)^2 \geq
\epsilon^4/(4k^2)$. As there are more than $\epsilon k^2$ irregular
pairs $(I, J)$, and all the rectangles  $I \times J$ are disjoint, we have
\[
\|f_k - f_{kq}\|_2^2 > \frac{\epsilon^5}{4}.
\]
Note that
\[
\int_{[0,1]^2} (f_k - f_{kq}) f_k  \, d\lambda = 0
\]
since $f_k$ is constant over each box $[i/k, (i+1)/k) \times [j/k,
(j+1)/k)$, and $f_{kq}$ averages to $f_k$ on this box. Thus $f_k$ and
$f_k - f_{kq}$ are orthogonal, so by the Pythagorean theorem,
\[
\|f_{kq}\|_2^2 = \|f_{k} - (f_k - f_{kq})\|_2^2 = \|f_k\|_2^2 + \|f_k
- f_{kq}\|_2^2 > \|f_k\|_2^2 + \frac{\epsilon^5}{4},
\]
which contradicts \eqref{eq:f_kq-f_k}. It follows that the partition
of $[0,1]$ into $k$ equal-length intervals is interval $\epsilon$-regular for $f$.
\end{proof}

\subsection{Dealing with equitable partitions}

Here is a lemma that will be useful for the proof of
Theorem~\ref{thm:int-reg-matrix}. It says that $(I, J)$ being interval
regular is robust under changing $I$ and $J$ by a small amount.

\begin{lemma} \label{thm:int-eps-reg-nudge}
  Let $f \colon [0,1]^2 \to [0,1]$ be a measurable function. Let $I,
  I', J, J' \subseteq [0,1]$. Let $0 < \epsilon \leq 1$. Let $\epsilon' > 0$ be
  a quantity less than each of
  \[
  \epsilon - \frac{4 \lambda( (I \times J)\Delta (I' \times
    J'))}{\epsilon^2 \lambda(I)\lambda(J)}, \quad \frac{\lambda(I)
    \epsilon - \lambda(I \setminus I')}{\lambda(I')}, \quad \frac{\lambda(J)
    \epsilon - \lambda(J \setminus J')}{\lambda(J')}.
  \]
  If $(I', J')$ is interval $\epsilon'$-regular for $f$, then $(I, J)$
  is interval $\epsilon$-regular for $f$.
\end{lemma}

\begin{proof}
  Let $A \subseteq I$ and $B \subseteq J$ be subintervals such that
  $\lambda(A) \ge \epsilon \lambda(I)$ and $\lambda(B) \ge \epsilon
  \lambda(J)$. Let $A' = A \cap I'$ and $B' = B \cap J'$. The second
  and third hypotheses about $\epsilon'$ above imply that $\lambda(A')
  \ge \epsilon' \lambda(I')$ and $\lambda(B')
  \ge \epsilon' \lambda(J')$. Since $(I', J')$ is $\epsilon'$-regular
  for $f$, we have
  \[
  |d_f(A', B') - d_f(I', J')| \leq \epsilon'.
  \]
  By Lemma~\ref{lem:density-diff}, we have
  \[
  |d_f(I, J) - d_f(I', J')| \le \frac{2 \lambda( (I \times J)\Delta (I' \times
    J'))}{\lambda(I)\lambda(J)}
  \]
  and
  \[
  |d_f(A, B) - d_f(A', B')| \le \frac{2 \lambda( (A \times B)\Delta (A' \times
    B'))}{\lambda(A)\lambda(B)}
  \le \frac{2 \lambda( (I \times J)\Delta (I' \times
    J'))}{\epsilon^2 \lambda(I)\lambda(J)}.
  \]
  It follows by the triangle inequality and the first hypotheses on
  $\epsilon'$ that
  \[
  |d_f(A, B) - d_f(I, J)| \leq \epsilon,
  \]
  which proves that $(I,J)$ is $\epsilon$ regular for $f$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:int-reg-matrix}]
  Let $f \colon [0,1]^2 \to [0,1]$ be the function that takes constant value $y_{ij}$ on the rectangle $[(i-1)/n,
  i/n) \times [(j-1)/n, j/n)$, for each $1 \le i, j \le n$. By
  Theorem~\ref{thm:int-reg-function}, there is some $k \in [m, m\epsilon^{-O(\epsilon^{-5})}]$ so that the
  partition of $[0,1]$ into $k$ equal-length intervals
  interval $(\epsilon/2)$-regular.

  Any equitable partition $\mathcal{P}$ of $[n]$ into sets of sizes $c_1, \dots, c_k$, gives rise to a partition $\mathcal{Q}$ of $[0,1]$ into intervals of length $c_1/n, \dots, c_k/n$.   Since $\mathcal{P}$ is an equitable partition, the $i$-th interval $I_i$ of
  $\mathcal{Q}$ differs, in terms of symmetric
  difference, from $[(i-1)/k, i/k)$  by at most $k/n$ in measure. It follows from
  Lemma~\ref{thm:int-eps-reg-nudge} that if $n$ is large enough, say, $n \ge 100k^3 \epsilon^{-3}$, then $(I_i, J_i)$ is interval
  $\epsilon$-regular for $f$ whenever $[(i-1)/k, i/k) \times [(j-1)/k,
  j/k)$ is interval $(\epsilon/2)$-regular for $f$. It follows that $\mathcal{Q}$ is interval $\epsilon$-regular for $f$.

  When $n < 100k^3\epsilon^{-3}$, we can take the partition of $[n]$ into singletons, which is trivially interval $\epsilon$-regular.
\end{proof}

redpajama_set_name: RedPajamaArXiv


These 5 simple tips to lose weight and lose belly involve only changes in habits and can help eliminate up to 2 kg per week. But you must follow these guidelines daily and do not become anxious, climbing the scales every day to see if you have lost weight or gained weight.
The ideal is to weigh only once a week, always at the same time and take into consideration if you are in the menstrual period because this week is normal to be a little more swollen, which reflects in the balance.
Your body has to learn how to sleep, wake up and eat. This will make it work better, will prevent frequent hunger and the night-time churns, which are the most fattening. In addition, resting at least 7 hours a night gives you the courage to keep your appointments, exercise more, and resist temptation.
So try putting an alarm on your cell phone to play every 3 hours so you can eat something and so do not get hungry. Preferring foods with low glycemic index helps you not to get hungry after eating only 1 pear, for example.
You should drink plenty of fluids between meals as this will help reduce hunger and fluid retention because the more water you drink, the more urine your body produces, and the elimination of toxins that are harmful to weight loss.
What comes out: soft drinks, box juice, chocolate and alcoholic beverages.
Liquids should be ingested preferably up to half an hour before and after meals. The recommended amount of water required varies between 1.5 and 2 liters per day.
Take the dog for a stroll in the evening.
To increase energy expenditure, try taking walks of at least 45 minutes, 3 times a week, as this is one of the best physical exercise to lose weight, but also do some resistance exercises like bodybuilding to complement the workout.
Eat at least 3 fruits per day.
Even in small amounts during the day, fruits and vegetables provide plenty of fiber and vitamins and is therefore a source of health and helps to lose weight and lose belly.
The best snacks are: 1 fruit + 5 cookies without filling or 1 skimmed yogurt + 1 whole wheat bread with butter.
Going without food causes your body to save calories by spending less than it should and turning every extra food into a store of fat.
If it seems that weight loss is very difficult, it may be important to see an endocrinologist to see if the thyroid gland is working as it should. In addition, a nutritionist, or medical nutrologist, can be consulted to establish customized dietary rules and thus be simpler to comply with. Added to that, it's great to have someone else on the team, cheering and getting results.
In cases where there is a health problem, such as gastritis, asthma, osteoporosis, or even just a limitation of mobility, the advice and advice of physicians, to reconcile diet with the use of medications and with adequate adaptation to the disease, is fundamental so that it is possible to lose weight improving the quality of life, not the other way around.


This New Testament commentary series reflects this objective of explaining and applying Scripture. Some commentaries are primarily linguistic, others are mostly theological, and some are mainly homiletical. This one is basically explanatory, or expository. It is not linguistically technical but deals with linguistics when that seems helpful to proper interpretation. It is not theologically expansive but focuses on the major doctrines in each text and how they relate to the whole of Scripture. It is not primarily homiletical, although each unit of thought is generally treated as one chapter, with a clear outline and logical flow of thought. Most truths are illustrated and applied with other Scripture.
John MacArthur (b. 1939) is a Calvinist theologian, author, editor, and teacher. He is a popular conference speaker and the president of both The Master's College and The Master's Seminary. He has also served as pastor-teacher of Grace Community Church in Sun Valley, California since 1969. Best known for his expository exegesis of the Bible, Logos has collected more than 3,000 of his sermons in the John MacArthur Sermon Archive and offers the complete MacArthur New Testament Commentary.
MacArthur's pulpit ministry extends around the globe through his media ministry, Grace to You. In addition to producing daily radio programs for nearly 2,000 English and Spanish radio outlets worldwide, Grace to You distributes books, software, and CDs by John MacArthur. He has written hundreds of books and study guides, including the bestselling John MacArthur Essential Bible Study Library and the MacArthur Study Bible. He is also the author of notable titles like Different by Design and Twelve Ordinary Men.
First, the direct statements of Scripture affirm that Jesus is God.
Jesus Christ was already in existence when the heavens and the earth were created; thus, He is not a created being, but existed from all eternity.
Without the spiritual washing of the soul, a cleansing accomplished only by the Holy Spirit (Titus 3:5) through the Word of God (Eph. 5:26), no one can enter God's kingdom.
By calling him to be born again, Jesus challenged this most religious Jew to admit his spiritual bankruptcy and abandon everything he was trusting in for salvation.
Fourth, Jesus Christ does the works that only God can do.


Two things I love, a bold lip and a matte lippie! 2015 seems to be the year of the matte lip and I'm here for all of it!
MAC is by far my fav lippie brand but at $17 each, I'm always willing to try a more economical alternative!
I've gotten 2 of the Loreal Le Matte lippies and I absolutely love them, plus they're less than $10 #winning!!!!
Today I just felt like going bold with a red lip, and it also goes with the skirt I'm wearing!
This one is called Mad For Matte. Not a good name for a bold red, but it's an awesome red for when you want to go full on red!
Have you tried this matte from Loreal yet?
Thanks ☺you should definitely try them! They don't have very many shades, but I'm sure you'll see one that you like!
Oooh now I want to try the Revlon ones!!!!


Over the years as friends come and go! ,I have listened the many guys talk (If not boast & brag about!) this girl and I did this and that girl did that.
At the time! I knew little about what my fellow male friends did and the way they talked it sounded like they did not either. All by relayed messenger (other guy friends "+/-" on the fact/fiction!).
But the thing, that still even to this day! Is how hard, difficult, complex in general! Relationships are these days! It will be a battle of the sexes. Women think/claim they know more than men! Men to the same as well.
The real problem between men and women is too much "EXCREMENT" is going around! But at the same time! There is another problem as well. And that is "TRADITION" How men seen and heard how dad treated mom! And how mom looked & felt after what dad did and their daughters on the same end as well also.
And the next thing in line is! Past relationships on both sides.
When it comes to the past! Let it GO! There is no!!!! Rewinds, instant replays, wayback machines, time tunnels, magical, mystical, cosmic, force that can nor ever will bring it back and change anything!
You learn from it and move on is all any of us can really do.
But! That does not mean to be bitter against any people/animals included!
Believe it or not! Like it or not!
Life itself! Always has! Always will! Be on great big classroom 24/7!
What you learn from it depends on you!
You can either let make you!
Robin Williams' Depression Struggles May Go Back Decades | TIME.


text:
Vicki Davis, Supervisor of Elections in Martin County, said Tuesday afternoon the county saw a steady, but slower-than-typical turnout.
In past years, Martin County saw 48% to 49% voter turnout. Tuesday late afternoon, Davis said the county is experiencing about a 30% turnout with about 4,498 people who voted in-person by 4 p.m.
Davis said with voting polls open until 7 p.m., she expects more people to come to voting locations and vote in the coming hours.
Overall, the county didn't experience any problems at the polls, despite about 20 poll volunteers declining to volunteer because of COVID-19.
Low turnout
Barbara Feldman, 73,of Jensen Beach, voted at the Vince Bocchino Community Center in Langford Park.
The low number of people at the voting center was surprising, she said. "We were the only two in there," Feldman said of she and her husband.
When asked about coronavirus concerts, she said "I almost didn't come for that reason."
She decided to come because her daughter said there wouldn't be large crowds and to "just go."
Feldman said she did feel at ease after seeing the precautions volunteers were taking. All volunteers inside had blue latex gloves on and some were wiping down voting booths with wipes.
Precinct 4 Clerk Jeff Carson said 301 people had voted by 4:45 p.m Tuesday. This location typically averages between 600-800 voters during an election day.
"We were told it would be light because it's basically a Democratic primary only and of course, the virus situation. I'm sure people are concerned."
He's been volunteering at the precinct for eight years.
Asked why the low turnout, Carson said "I think so many people are afraid of coming out." He also said more people may have voted by mail this year.
With about two hours of voting left, Carson said, "If we get another hundred, I'd be shocked"
Other precincts
At just after 4 p.m., only 101 people had voted at the 10th street Community Center Guy Davis Sports Complex.
Deborah Langston, 84, clerk of precinct 8, said the number was "much lower than expected."
She thinks many people voted early, but said she thinks many others are staying home because of coronavirus concerns. Langston doesn't expect large amounts of people to come out before voting closes at 7 p.m. this evening, "it would surprise me" if they did.
Langston has been working this precinct for more than 20 years and said "we've never been this low" in numbers.
Sidney Solomon, 44, is a precinct 8 voter and although he is concerned about the coronavirus, he comes out to every election.
"I was expecting longer lines," he said. He said the reason could be because of the virus, but also it's "just one question" to answer so it doesn't take long.
Asked how he voted, he laughed and said "that's personal," but followed up with "I'm for Biden."
At the Palm City Community Center, about seven people slowly arrived from 10:45 a.m. to 11:15 a.m. Voting signs were out in front of the center guiding residents where to go to vote.
At the Blake library, 2351 S.E. Monterey Road in Stuart, a few people walked in before 9 a.m., but the voting location remained mostly empty.
It's been the same so far throughout the day at many polling places. People are voting, but it's just a few arriving here and there.
Before Tuesday, 13,641 ballots were cast by mail and 3,670 people voted early in person. There are 55,236 Republicans and 28,957 Democrats registered to vote in Martin County, according to Davis' website.
There are 28 precincts in the county. There were no changes in voting locations for the presidential primary.
Precautions against COVID-19
Davis said hand sanitizer was available at all voting locations and at some locations informational boards were put up by the front door educating residents on how to protect themselves against COVID-19.
Supervisors of elections are are telling people that although they have taken every precaution to ensure public safety regarding the health crisis, the supplies they have may not last for the entire 12-hour voting period. They are asking voters who have any concerns about their health and safety, to bring their own hand sanitizer, wear gloves and bring their own black ink pen.
Some polling locations are operating with a minimal staff as workers have called out stating that they will not be able to report to work.
"This is a totally different election from what we've experienced in the past," Davis said.
Polls across Martin County are open until 7 p.m. today for voting in the presidential primary.
Florida dealt election double whammy with busy hurricane season, COVID-19 pandemic Election 2020: Here's everything you need to know about Collier County primaries, candidates Election 2020: Here's everything you need to know about Lee County primaries, candidates Collier County Supervisor of Elections Lee County Supervisor of Elections
► Primary colors: Treasure Coast GOP, Dem registration drop as independents surge
Having trouble viewing our live tweets? If so, click here.

redpajama_set_name: RedPajamaCommonCrawl


The following History of Bastrop, Texas is taken from The New Handbook of Texas published by The Texas State Historical Association in 1996.
BASTROP, TEXAS, is the county seat of Bastrop County, and is located about thirty miles southeast of downtown Austin. The town is at the junction of State highways 71, 21, and 95, and on the Colorado River. The site was first occupied in 1804, when a fort was established at the strategic Colorado River crossing of the Old San Antonio Road and named Puesta del Colorado. The Baron de Bastrop obtained permission from the Spanish to found a German colony and selected the site in 1823, but subsequently failed to establish a settlement. The town was probably named Bastrop by Stephen F. Austin in honor of the baron, a longtime friend and coworker. Austin, interested in developing the upper reaches of his original colony, used this name after the German colonization attempt failed and he obtained permission in 1827 to locate a "Little Colony" of 100 families on the site. By 1830 early pioneers such as Josiah Wilbarger, Reuben Hornsby, James Burleson, Edward Burleson, and Jess Barker had located in the Bastrop area. But Indian depredations continued to slow settlement.
On June 8, 1832, land commissioner José Miguel de Arciniega officially platted the town along conventional Mexican lines, with a square in the center and blocks set aside for public buildings. He also officially named the site Bastrop, but two years later the Coahuila and Texas legislature renamed it Mina in honor of Francisco Xavier Mina, a Mexican martyr and hero.
On January 1, 1835 Juan N. Alamonte reported a population of 1,100 in the area, and at the outbreak of the Texas Revolution the town's population was approximately 400. Bastrop served as a business, commercial, and political center for an area that stretched far beyond Bastrop County; it was the place where settlers rallied for retaliation and forted up for protection when Indian depredations occurred in the vicinity. Until the railroad reached the county in the early 1870s, Bastrop was the only town in the county. In May 1835, Mina citizens became the first to organize a committee of safety to stockpile arms and keep citizens informed of revolutionary developments. The town suffered in the Runaway Scrape of 1836, when residents returned to find it completely destroyed by the Mexican army and Indians. Indians, particularly the Comanches, who hunted in the area every fall, continued to provide a major threat until after annexation to the United States in 1846.
The town was incorporated under the laws of Texas on December 18, 1837, and the name changed back to Bastrop. The community then comprised of a courthouse, a hotel, a stockade, a gunsmith shop, a general store, and a number of residences. With farming, the timber industry provided a mainstay for the local economy from 1836 to 1860. The Lost Pine Forest, the westernmost stand of the eastern pine forest and the only timber available in what was then western Texas, contributed to the economy. In 1839, when Austin became the capital of the republic, Bastrop began supplying the city with lumber. Soon, ox teams were carting Bastrop lumber to San Antonio, along the western frontier, and into Mexico.
Though Protestant services were held in Bastrop as early as 1835, official organization of a Protestant congregation did not occur until three years later, when a Methodist church with fifteen members was begun. The introduction of slaves to the area helped make cotton a major part of the local economy after 1839 and lessened the priority of lumber. A post office was established in 1846, and a one-room log school was in operation the next year. By the 1850s Bastrop was developing rapidly. In 1851 Bastrop Methodists built the county's first church, a weekly newspaper was founded, and the Bastrop Educational Society opened Bastrop Academy. By the following year, the Bastrop Advertiser had begun its long publishing history, the academy had been incorporated as Bastrop Female Academy, and a subscription library had begun. In 1856 Bastrop Military Institute (later Texas Military Institute, Austin) opened.
With the turn of the century, stock raising increased. Bastrop established a public library, and by 1909 had graded schools and two banks. The population in 1910 was 1,707. It hovered around the 2,000 mark through the early twentieth century. In the 1920s the Bastrop area was the scene of oil drilling, and between 1928 and 1935 lumber operations were revived; a Bastrop mill produced thirty million board feet of lumber annually during those years. Although coal was known to exist in large quantities a few miles from Bastrop as early as 1837, and was mined between 1860 and 1870, major lignite extraction began only around 1910 and from then until 1940 was the community's predominant industry.
The population peaked at about 5,000 during World War Il, after the establishment of nearby Camp Swift. When the camp gradually closed after the war, Bastrop shrank to 4,000, then 3,158 in 1950. Industries in 1947 included a pecan-shelling plant, a cedar-chest factory, and a cedar-oil manufacturer. From 1950 through the 1970s Bastrop's population ranged between 2,950 and 4,050. The 1980s brought new challenges for the community as Austin grew eastward. Austin sewage polluted the Colorado, and strip-mining began pressing from the east. In the mid-1980s the town had a population of almost 4,000. In 1990 the population was 4,044. Residents had restored many historic buildings, and commuters from Austin lived in Bastrop. As a consequence of the town's proximity to Austin, land values soared. Bastrop remained a center for agribusiness, its industries included oil-well supply and furniture manufacturing.
Bastrop has become the financial and business center of Bastrop County. Rapid growth has occurred along the Highway 71 Corridor to Austin. With the establishment of the Austin Bergstrom International Airport within 20 minutes of Bastrop, the city is poised for growth and activity in the 2000s. New housing is a reality, while preservation of our historic areas is a top priority. A new Economic Development Park is finished. The growing School District is dedicated to excellence in education. With new businesses, infrastructure and streets, the City looks forward to the 2000s while remembering the Past!


text:
It's Time to Vote for Brian Sims
As The Advocate profiles the out lawyer in its "40 Under 40," he gets our endorsement
By Natalie Hope McDonald· 4/24/2012, 8:32 a.m.
Brian Sims has been making quite a few headlines lately as he runs for state house in the 182nd district in Philly. On this election day, he goes up against longtime incumbent Babette Josephs in a campaign that has inspired much conversation – and controversy – in recent weeks, with both candidates attacking each other with sometimes curious campaign ads, mailers and debate.
Photo by Chris Crisman (courtesy of The Advocate)
Yes, Sims worked with Josephs as treasurer of her campaign a few years ago. Yes, Josephs has been an outspoken advocate for LGBT rights during her tenure. And yes, both candidates have much good work to do – though Josephs has been poised to do that work for years now and we can't help but get the impression that she's cramming for her finals. But as an openly gay man himself, Sims could make history if he's elected – becoming the first out representative in Pennsylvania.
Being openly gay doesn't guarantee anyone's vote in the LGBT community – let alone the general population. A candidate has to earn it. But we've had our eye on Sims ever since he helped transform Equality Pennsylvania – a group that has become a major advocacy watch dog for LGBT issues throughout the commonwealth. He's also worked extensively with the Philadelphia Bar Association and GALLOP. And as a one-time member of the Gay & Lesbian Victory Fund, he's spoken about the policy and legal challenges facing the LGBT community.
Sims is smart, motivated and he lives what he talks about. That recipe isn't always easy to find in most public figures – let alone a politician.
That's why we included him in our "New Who's Who" last year. And we suspect that why The Advocate took a page from our playbook and honored him in their "Forty Under Forty" this month, praising Sims for providing a liberal benchmark in a state that many have associated, unfortunately, for being Santorum Country.
As Sims seeks to unseat Josephs in today's primary, we can't help but imagine what a victory for Sims could mean for LGBT rights in a state that scarcely offers protections based on sexual orientation and gender identity, a state that is shadowed by an amendment that could ban marriage equality entirely if it ever passes. The conservative leadership in Pennsylvania is a strong one, with Gov. Tom Corbett at the helm of a ship intent to sink any hope of LGBT rights progress (he even wants to make voter IDs mandatory, as many will see today as they head to the polls and are asked for a photo ID "voluntarily").
But we like to think that a candidate as bold and motivated as Sims – the son of two Army Lt. Colonels who helped win a Division II Championship in college as one of the only openly gay football captains in the nation – a guy who believes in what he says and does something about it, could be what Pennsylvania needs right now.
We applaud Josephs for her advocacy and the attention she's paid to the LGBT community over the years. It's always seemed genuine. Josephs is, quite frankly, a solid Democrat in a liberal city and we've been fortunate to have her on our side. But there have been some bumps in the road. We wouldn't simply abandon the good she's done in favor of a new kid on the block (who happens to be gay) if not for the bumps – and the major prospects we see in Sims. Whether today is a win or a loss for him, Sims has a future in politics.
The irony here is that if Sims was running for any other seat other than Josephs, we suspect he would have her endorsement. And because we think it's time for Pennsylvania to have its first openly gay legislator as the lives of real people are at stake, when same-sex couples are poised to tie the knot, when hardworking Pennsylvanians are treated differently simply because of their sexual orientation or gender identity, and when the community may feel that its voice is not always being heard loud and clear in Harrisburg, we believe that person should be Brian Sims.
Everything You Need to Know Before the Eagles' NFC Championship Game
City Hacks: Everything You Need to Know About Those Evil Philly Potholes
8 Lesser-Known Abortion Funds to Support Post-Roe


Ain't Nothing But a Bee Sting Baby: Bright lights.
The City is back. All is right in the world.
This show makes my heart happy.
"You have to be prepared for people to hate you.
Average people love to be average because nobody bothers them."


text:
Q: How to export all the information from 3d numpy array to a csv file Kaggle Dataset and code link
I'm trying to solve the above Kaggle problem and I want to export preprocessed csv so that I can build a model on weka, but when I'm trying to save it in csv I'm losing a dimension, I want to retain all the information in that csv.
please help me with the relevant code or any resource.
Thanks
print (scaled_x)

    |x           |y          |z          |label
    |1.485231    |-0.661030  |-1.194153  |0
    |0.888257    |-1.370361  |-0.829636  |0
    |0.691523    |-0.594794  |-0.936247  |0

Fs=20
frame_size = Fs*4 #80
hop_size = Fs*2 #40

def get_frames(df, frame_size, hop_size):
    N_FEATURES = 3
    frames = []
    labels = []
    for i in range(0,len(df )- frame_size, hop_size):
        x = df['x'].values[i: i+frame_size]
        y = df['y'].values[i: i+frame_size]
        z = df['z'].values[i: i+frame_size]

        label = stats.mode(df['label'][i: i+frame_size])[0][0]
        frames.append([x,y,z])
        labels.append(label)

    frames = np.asarray(frames).reshape(-1, frame_size, N_FEATURES)
    labels = np.asarray(labels)

    return frames, labels

x,y = get_frames(scaled_x, frame_size, hop_size)
    x.shape, y.shape

((78728, 80, 3), (78728,))

A: According to the link you posted, the data is times series accelerometer/gyro data sampled at 20 Hz, with a label for each sample. They want to aggregate the time series into frames (with the corresponding label being the most common label during a given frame).
So frame_size is the number of samples in a frame, and hop_size is the amount the sliding window moves forward each iteration. In other words, the frames overlap by 50% since hop_size = frame_size / 2.
Thus at the end you get a 3D array of 78728 frames of length 80, with 3 values (x, y, z) each.
EDIT: To answer your new question about how to export as CSV, you'll need to "flatten" the 3D frame array to a 2D array since that's what a CSV represents. There are multiple different ways to do this but I think the easiest may just be to concatenate the final two dimensions, so that each row is a frame, consisting of 240 values (80 samples of 3 co-ordinates each). Then concatenate the labels as the final column.
x_2d = np.reshape(x, (x.shape[0], -1))
full = np.concatenate([x, y], axis=1)

import pandas as pd
df = pd.DataFrame(full)
df.to_csv("frames.csv")

If you also want proper column names:
columns = []
for i in range(1, x.shape[1] + 1):
    columns.extend([f"{i}_X", f"{i}_Y", f"{i}_Z"])
columns.append("label")
df = pd.DataFrame(full, columns=columns)

redpajama_set_name: RedPajamaStackExchange


text:
Five Facts About Prostate Cancer Every Man Should Know
Last month, singer and songwriter Dan Fogelberg died at the age of 56 after fighting prostate cancer since 2004.
His doctors said if he had been diagnosed earlier, he could have survived.
Fogelberg's death has shined light on a disease the American Cancer Society calls the most common cancer, other than skin cancers, in American men. Prostate cancer is the second-leading cause of cancer death in American men; only lung cancer ranks higher. The nonprofit estimates that about one in six men will be diagnosed with prostate cancer during his lifetime, but just one in 35 will die of it.
With data such as this, every male who has reached 40 should arm himself with the information that can keep him from becoming a statistic. Dr. Arnon Krongard, president of the Krongard Institute and chairman of the Prostate Cancer Mission, believes that knowing the following five facts will put men in a better position to survive this deadly cancer:
1. Prostate cancer kills 500 American men weekly — Krongard likens the disease's mortality rate to "a Jumbo Jet crashing into a mountain." He said the rate skyrockets if you add in the number of prostate cancer deaths from countries around the world.
2. Prostate cancer in the curable stages is not symptomatic — "If you are waiting for symptoms, you are missing a window of opportunity," Krongard said. The American Cancer Society said that men who have reached age 50 and have at least a 10-year life expectancy should begin testing for prostate cancer.
In addition, men who have a father, brother or son with prostate cancer before age 65 should begin testing at age 40. Depending on the results of this initial test, further testing might not be needed until age 45.
3. Prostate cancer can be detected when it is asymptomatic — there are two tests used to diagnose the disease. The PSA blood test measures the level of prostate-specific antigen in the blood. Prostate gland cells manufacture this antigen whether they are normal or cancerous.
Your chance of having prostate cancer increases, however, as your PSA level increases. If your PSA level is 10 or more, you have a more than 50 percent chance of developing prostate cancer.
A second test, the DRE, or digital rectal exam, involves your doctor inserting a gloved finger into the rectum to feel whether there are any bumps or hard areas in your prostate. If there are, you will need further testing to see if cancer is present.
4. Early detection is key to effective management — prostate cancer that is localized in the prostate usually is curable, but once the cancer has spread to lymph nodes, bones or other sites, it no longer is curable.
5. There have been some advances in the cure, especially in the realm of surgery. A recently developed surgical procedure known as laparoscopic radical prostatectomy uses several smaller incisions through which long instruments are inserted to remove the prostate. A small video camera on the end of one of these instruments allows the surgeon to see inside the abdomen.
The advantages to this type of surgery include less blood loss and pain, shorter hospital stays and faster recovery times.
"Patients are exposed to commercial hype that makes it seem as though if you get the right device or drug, that's all that's important," Krongard added.
"It's necessary for patients to know who their doctor is. Does she have the experience, passion and focus to give you the care you need?"
For more information about prostate cancer, click here to visit the Prostate Cancer Mission on the Web.