Cover Image

Notes on the Linear Algebraic View of Regularity Lemmas

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodwin, Greg, Le, Tuong
Format:	Preprint
Published:	2025
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

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

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

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

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

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)

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

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

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

A Note on Generic Tangle Algorithms
by: Elbracht, Christian, et al.
Published: (2020)

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
by: Babatunde, Abiola, et al.
Published: (2026)

Approximate Counting in Local Lemma Regimes
by: Mann, Ryan L., et al.
Published: (2025)

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

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

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

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

On the occupancy fraction of the antiferromagnetic Ising model
by: Davies, Ewan, et al.
Published: (2024)

An Algebraic Approach to the Longest Path Problem
by: Khazali, Omar Al -
Published: (2023)

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

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

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

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

On The Maximum Linear Arrangement Problem for Trees
by: Alemany-Puig, Lluís, et al.
Published: (2023)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
by: Paschalidis, Phevos, et al.
Published: (2023)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
by: Bourneuf, Romain, et al.
Published: (2025)

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
by: Tate, Reuben, et al.
Published: (2025)

Testing H-freeness on sparse graphs, the case of bounded expansion
by: Humeau, Samuel, et al.
Published: (2025)

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

Liar's vertex-edge domination in unit disk graph
by: Bhattacharya, Debojyoti, et al.
Published: (2025)

Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
by: Jones, Mark, et al.
Published: (2025)

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

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
by: Biedl, Therese
Published: (2025)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
by: Daga, Mohit
Published: (2025)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
by: Gharan, Shayan Oveis, et al.
Published: (2025)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

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

A Combinatorial Characterization of Constant Mixing Time
by: Lau, Lap Chi, et al.
Published: (2025)