An algorithmic regularity lemma for L_p regular sparse matrices

DOI10.1137/16M1086558MaRDI QIDQ5371027zbMATH OpenWikidataFDO

Authors Silouanos Brazitikos, Thodoris Karageorgos

Publication date 24 October 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

sparse matricesregularity lemmasparse graphsalgorithmic regularity lemma

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Classical Banach spaces in the general theory (46B25)

Abstract: We prove an algorithmic regularity lemma for $L_p$ regular matrices $(1<pleqinfty),$ a class of sparse $0,1$ matrices which obey a natural pseudorandomness condition. This extends a result of Coja-Oghlan, Cooper and Frieze who treated the case of $L_{infty}$ regular matrices. We also present applications of this result for tensors and MAX-CSP instances.

Recommendations

• Szemerédi's regularity Lemma for matrices and sparse graphs
• A unified view of graph regularity via matrix decompositions
• Szemerédi’s Regularity Lemma for Sparse Graphs
• An efficient sparse regularity concept
• $L_p$ regular sparse hypergraphs

Cites work

• scientific article; zbMATH DE number 1944144 (Why is no real title available?)
• $L_p$ regular sparse hypergraphs
• A concentration inequality for product spaces
• A noncommutative martingale convexity inequality
• Additive combinatorics
• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An efficient sparse regularity concept
• Approximating the cut-norm via Grothendieck's inequality
• Gadgets, Approximation, and Linear Programming
• Grothendieck’s Theorem, past and present
• Quick approximation to matrices and applications
• Some optimal inapproximability results
• Szemerédi's regularity lemma via martingales
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The phase transition in inhomogeneous random graphs
• \(L_p\) regular sparse hypergraphs: box norms

Cited in

(1)

• A unified view of graph regularity via matrix decompositions

This page was built for publication: An algorithmic regularity lemma for \(L_p\) regular sparse matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371027)