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 algorithmscut normmatrix decompositionrandom discrete structuresregularity Lemma

Mathematics Subject Classification ID

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

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

(19)

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

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)