**A Cryptographic Proof of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds**

*Maciej Skorski*

**Abstract: **In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic technique called \emph{low-complexity approximations}. In short, both problems
reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where distinguishers are combinations of simple rectangle-indicators.
In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density $d$ and any approximation parameter $\epsilon$ the partition size
\begin{itemize}
\item a tower of 2's of height $O\left( d_{}\epsilon^{-2} \right)$ for a variant of Strong Regularity
\item a power of 2 with exponent $O\left(d\epsilon^{-2} \right)$ for Weak Regularity
\end{itemize}
The novelty in our proof is as follows: (a) a simple approach which yields both strong and weaker variant, and (b)
improvements for sparse graphs.

At an abstract level, our proof can be seen a refinement and simplification of the ``analytic'' proof given by Lovasz and Szegedy.

**Category / Keywords: **regularity lemmas, boosting, low-complexity approximations, convex optimization, computational indistingusiability

**Date: **received 5 Oct 2016, last revised 29 Dec 2016

**Contact author: **maciej skorski at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Some typos corrected

**Version: **20161229:194747 (All versions of this report)

**Short URL: **ia.cr/2016/965

[ Cryptology ePrint archive ]