Welcome to the resource topic for
**2016/965**

**Title:**

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

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2016/965

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .