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 .