Cover Image

A Unified View of Graph Regularity via Matrix Decompositions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodwin, Greg, Vempala, Santosh
Format:	Preprint
Published:	2019
Subjects:	Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Notes on the Linear Algebraic View of Regularity Lemmas
by: Bodwin, Greg, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

An Alternate Proof of Near-Optimal Light Spanners
by: Bodwin, Greg
Published: (2023)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

Improved Online Reachability Preservers
by: Bodwin, Greg, et al.
Published: (2024)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
by: Chalermsook, Parinya, et al.
Published: (2025)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order
by: Glover, Charles N.
Published: (2024)

The Localization Method for High-Dimensional Inequalities
by: Kook, Yunbum, et al.
Published: (2025)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Sampling Sphere Packings with Continuum Glauber Dynamics
by: Kuchukova, Aiya, et al.
Published: (2026)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
by: Karamchedu, Mithra, et al.
Published: (2025)

A Maximum Linear Arrangement Problem on Directed Graphs
by: DeVos, Matt, et al.
Published: (2018)

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
by: Bodwin, Greg, et al.
Published: (2022)

Random Generation of Git Graphs
by: Courtiel, Julien, et al.
Published: (2024)

Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
by: Kook, Yunbum, et al.
Published: (2024)

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
by: Kook, Yunbum, et al.
Published: (2023)

The Geometry of Efficient Nonconvex Sampling
by: Vempala, Santosh S., et al.
Published: (2026)

Sparsifying Cayley Graphs on Every Group
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Distance Reconstruction of Sparse Random Graphs
by: Bastide, Paul
Published: (2024)

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
by: Madani, Amirali, et al.
Published: (2025)

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

Graph parameters that are coarsely equivalent to tree-length
by: Dragan, Feodor F.
Published: (2025)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
by: Biedl, Therese, et al.
Published: (2024)

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
by: Chalermsook, Parinya, et al.
Published: (2025)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
by: Gavva, Surya Teja, et al.
Published: (2025)

Characterization of Circular-arc Graphs: II. McConnell Flipping
by: Cao, Yixin, et al.
Published: (2024)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)