# [Resource Topic] 2016/965: A Cryptographic Proof of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds

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.

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.