Cryptology ePrint Archive: Report 2016/965

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]