Regularity Lemmas and Combinatorial Algorithms

DOI10.1109/FOCS.2009.76MaRDI QIDQ5171230zbMATH OpenFDO

Authors N. Bansal, Ryan Williams

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2009.76

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Recommendations

• Regularity lemmas and combinatorial algorithms
• On regularity lemmas and their algorithmic applications
• The Algorithmic Aspects of the Regularity Lemma
• scientific article; zbMATH DE number 1256685
• scientific article; zbMATH DE number 1512671
• An Algorithmic Regularity Lemma for Hypergraphs
• An algorithmic hypergraph regularity lemma
• An Algorithmic Hypergraph Regularity Lemma
• Some combinatorial-algebraic problems from complexity theory
• Algorithmic regularity for polynomials and applications

Cited in

(17)

• Pushdown reachability with constant treewidth
• Bounds for graph regularity and removal lemmas
• Linear-space data structures for range mode query in arrays
• A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs
• Grothendieck-type inequalities in combinatorial optimization
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• scientific article; zbMATH DE number 1512671 (Why is no real title available?)
• Fast matrix multiplication and its algebraic neighbourhood
• Tighter connections between Formula-SAT and shaving logs
• Algorithms for metric learning via contrastive embeddings
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Efficient arithmetic regularity and removal lemmas for induced bipartite patterns
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Fine-grained hardness for edit distance to a fixed sequence

This page was built for publication: Regularity Lemmas and Combinatorial Algorithms

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