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

DOI10.1007/978-3-319-55911-7_42zbMath1462.94047OpenAlexW2601648491MaRDI QIDQ2988852

Maciej Skórski

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_42

zbMATH Keywords

convex optimizationboostingregularity lemmascomputational indistinguishabilitylow-complexity approximations

Mathematics Subject Classification ID

Cryptography (94A60) Extremal set theory (05D05)

Cites Work

• Szemerédi's lemma for the analyst
• Quick approximation to matrices and applications
• A simple algorithm for constructing Szemerédi's regularity partition
• Lower bounds of tower type for Szemerédi's uniformity lemma
• A Uniform Min-Max Theorem with Applications in Cryptography
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• How to Fake Auxiliary Input

This page was built for publication: A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds