An efficient sparse regularity concept

DOI10.1137/080730160MaRDI QIDQ3058542zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Amin Coja-Oghlan, Colin Cooper, Alan Frieze

Publication date 3 December 2010

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

Full work available at URL http://wrap.warwick.ac.uk/43226/1/WRAP_Coja-Oghlan_sparsreg.pdf

zbMATH Keywords

approximation algorithmsmatrix decompositionregularity Lemmacut normrandom discrete structures

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Hypergraphs (05C65)

Recommendations

• An efficient sparse regularity concept
• Quick approximation to matrices and applications
• Computing sparse approximations deterministically
• Approximating sparse binary matrices in the cut-norm
• Approximating the Cut-Norm via Grothendieck's Inequality

Cited in

(15)

• Propagation Connectivity of Random Hypergraphs
• On the complexity of random satisfiability problems with planted solutions
• Regularity properties for sparse regression
• An algorithmic regularity lemma for \(L_p\) regular sparse matrices
• Grothendieck-type inequalities in combinatorial optimization
• Zero-one rounding of singular vectors
• An efficient sparse regularity concept
• A relative Szemerédi theorem
• Quick approximation to matrices and applications
• Extremal results in sparse pseudorandom graphs
• Note on strong refutation algorithms for random \(k\)-SAT formulas
• Approximating sparse binary matrices in the cut-norm
• SPARSE PARTITION REGULARITY
• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• The Geometry of Sparse Analysis Regularization

This page was built for publication: An efficient sparse regularity concept

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