Paper 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.

Note: Some typos corrected

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
regularity lemmasboostinglow-complexity approximationsconvex optimizationcomputational indistingusiability
Contact author(s)
maciej skorski @ gmail com
History
2016-12-29: last of 4 revisions
2016-10-05: received
See all versions
Short URL
https://ia.cr/2016/965
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/965,
      author = {Maciej Skorski},
      title = {A Cryptographic Proof of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/965},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/965}},
      url = {https://eprint.iacr.org/2016/965}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.