scientific article

DOI10.4086/toc.2012.v008a004zbMath1253.68162OpenAlexW2395349147MaRDI QIDQ2913804

Nikhil Bansal, R. Ryan Williams

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (13)

Unnamed Item ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases ⋮ 3D Rectangulations and Geometric Matrix Multiplication ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Mind the gap! ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ 3D rectangulations and geometric matrix multiplication ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Data structures for categorical path counting queries ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ On hardness of several string indexing problems ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

Cites Work

• Unnamed Item
• Unnamed Item
• Szemerédi's lemma for the analyst
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• 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

This page was built for publication: