A fast new algorithm for weak graph regularity

DOI10.1017/S0963548319000075zbMath1436.05106arXiv1801.05037OpenAlexW3104055895MaRDI QIDQ5222555

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

Publication date: 6 April 2020

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

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

zbMATH Keywords

regularity methodedge density

Mathematics Subject Classification ID

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

Related Items (1)

Amplification and Derandomization without Slowdown

Cites Work

• Unnamed Item
• Szemerédi's lemma for the analyst
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• Quick approximation to matrices and applications
• Explicit constructions of linear-sized superconcentrators
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• On sets of integers containing k elements in arithmetic progression
• 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
• Erratum: On Regularity Lemmas and their Algorithmic Applications
• An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
• On Regularity Lemmas and their Algorithmic Applications

This page was built for publication: A fast new algorithm for weak graph regularity