A unified view of graph regularity via matrix decompositions
From MaRDI portal
Publication:6074704
DOI10.1002/rsa.21053zbMath1522.05464arXiv1911.11868OpenAlexW3206623791MaRDI QIDQ6074704
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.11868
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limits of kernel operators and the spectral regularity lemma
- A short proof of Gowers' lower bound for the regularity lemma
- Szemerédi's lemma for the analyst
- Quick approximation to matrices and applications
- Lower bounds of tower type for Szemerédi's uniformity lemma
- A tight lower bound for Szemerédi's regularity lemma
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- Extremal results in sparse pseudorandom graphs
- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
- Szemerédi's Regularity Lemma for Matrices and Sparse Graphs
- Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
- Approximating the cut-norm via Grothendieck's inequality
- Spectral Algorithms
- Szemerédi’s Regularity Lemma for Sparse Graphs
- A sparse regular approximation lemma
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- Approximating Non-Uniform Sparsest Cut via Generalized Spectra
- Quasi-random graphs
- Efficient testing of large graphs
This page was built for publication: A unified view of graph regularity via matrix decompositions
