Regularity lemmas and combinatorial algorithms
DOI10.4086/TOC.2012.V008A004zbMATH Open1253.68162OpenAlexW2395349147MaRDI QIDQ2913804FDOQ2913804
Publication date: 27 September 2012
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2012.v008a004
combinatorial algorithmsBoolean matrix multiplicationtriangle removal lemma``four Russiansregularity lemmas for graphsweak regularity lemma
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Multiplying matrices faster than coppersmith-winograd
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Szemerédi's lemma for the analyst
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Title not available (Why is that?)
Cited In (18)
- Faster All-Pairs Shortest Paths via Circuit Complexity
- Fooling views: a new lower bound technique for distributed computations under congestion
- Quantum Complexity of Boolean Matrix Multiplication and Related Problems
- A comparative study of dictionary matching with gaps: limitations, techniques and challenges
- Title not available (Why is that?)
- On hardness of several string indexing problems
- Mind the gap!
- From Circuit Complexity to Faster All-Pairs Shortest Paths
- 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
- 3D rectangulations and geometric matrix multiplication
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Efficient arithmetic regularity and removal lemmas for induced bipartite patterns
- Internal masked prefix sums and its connection to fully internal measurement queries
- 3D Rectangulations and Geometric Matrix Multiplication
- Title not available (Why is that?)
- 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)
