On Regularity Lemmas and their Algorithmic Applications

DOI10.1017/S0963548317000049zbMath1371.05286arXiv1604.00733OpenAlexW2405333517WikidataQ105583898 ScholiaQ105583898MaRDI QIDQ5366957

Jacob Fox, László Miklós Lovász, Yufei Zhao

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.00733

zbMATH Keywords

Szemerédi's regularity lemmaweak Frieze-Kannan regularity lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)

Related Items (8)

Fast Property Testing and Metrics for Permutations ⋮ Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth ⋮ Amplification and Derandomization without Slowdown ⋮ Limitations on regularity lemmas for clustering graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Erratum: On Regularity Lemmas and their Algorithmic Applications ⋮ A fast new algorithm for weak graph regularity ⋮ Estimating parameters associated with monotone properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A short proof of Gowers' lower bound for the regularity lemma
• A permutation regularity lemma
• Szemerédi's lemma for the analyst
• Matrix multiplication via arithmetic progressions
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• 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
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A tight lower bound for Szemerédi's regularity lemma
• Bounds for graph regularity and removal lemmas
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• Powers of tensors and fast matrix multiplication
• The Algorithmic Aspects of the Regularity Lemma
• An Optimal Algorithm for Checking Regularity
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
• Approximate Hypergraph Partitioning and Applications
• Approximating the Cut-Norm via Grothendieck's Inequality
• A note on permutation regularity

This page was built for publication: On Regularity Lemmas and their Algorithmic Applications