An algorithmic regularity lemma for L_p regular sparse matrices

DOI10.1137/16M1086558zbMATH Open1372.05120arXiv1607.07204WikidataQ125056326 ScholiaQ125056326MaRDI QIDQ5371027FDOQ5371027

Authors: Silouanos Brazitikos, Thodoris Karageorgos 

Publication date: 24 October 2017

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

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.

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

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

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)

Cites Work

• The phase transition in inhomogeneous random graphs
• Additive combinatorics
• Gadgets, Approximation, and Linear Programming
• Grothendieck’s Theorem, past and present
• Some optimal inapproximability results
• A noncommutative martingale convexity inequality
• An efficient sparse regularity concept
• Quick approximation to matrices and applications
• Szemerédi's regularity lemma via martingales
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• A concentration inequality for product spaces
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Approximating the cut-norm via Grothendieck's inequality
• Title not available (Why is that?)
• $L_p$ regular sparse hypergraphs
• \(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)