Regularity lemmas and combinatorial algorithms

DOI10.4086/TOC.2012.V008A004MaRDI QIDQ2913804zbMATH OpenOpenAlexFDO

Authors N. Bansal, Ryan Williams

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2012.v008a004

zbMATH Keywords

combinatorial algorithmsBoolean matrix multiplicationtriangle removal lemma``four Russiansregularity lemmas for graphsweak regularity lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Data structures (68P05)

Recommendations

• On regularity lemmas and their algorithmic applications
• scientific article; zbMATH DE number 1256685
• Lower bounds for combinatorial algorithms for Boolean matrix multiplication
• The Algorithmic Aspects of the Regularity Lemma
• A deterministic algorithm for the Frieze-Kannan regularity lemma

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 1979525 (Why is no real title available?)
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Multiplying matrices faster than coppersmith-winograd
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Szemerédi's lemma for the analyst

Cited in

(20)

• Fooling views: a new lower bound technique for distributed computations under congestion
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• On hardness of several string indexing problems
• Faster all-pairs shortest paths via circuit complexity
• Mind the gap!
• Data structures for categorical path counting queries
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Regularity Lemmas and Combinatorial Algorithms
• Lower bounds for combinatorial algorithms for Boolean matrix multiplication
• Faster combinatorial k-clique algorithms
• 3SUM in preprocessed universes: faster and simpler
• 3D rectangulations and geometric matrix multiplication
• 3D rectangulations and geometric matrix multiplication
• Efficient arithmetic regularity and removal lemmas for induced bipartite patterns
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• From circuit complexity to faster all-pairs shortest paths
• Internal masked prefix sums and its connection to fully internal measurement queries
• Quantum complexity of Boolean matrix multiplication and related problems
• scientific article; zbMATH DE number 1512671 (Why is no real title available?)
• Faster combinatorial \(k\)-clique algorithms

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 Q2913804)