Quantum and approximation algorithms for maximum witnesses of Boolean matrix products

DOI10.1007/978-3-030-67899-9_35MaRDI QIDQ831754zbMATH OpenOpenAlexFDO

Authors Mirosław Kowaluk, Andrzej Lingas

Publication date 24 March 2022

Full work available at URL https://arxiv.org/abs/2004.14064

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Fast rectangular matrix multiplication and applications
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Faster multi-witnesses for Boolean matrix multiplication
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Multiplying matrices faster than coppersmith-winograd
• On minimum witnesses for Boolean matrix multiplication
• Powers of tensors and fast matrix multiplication
• Rectangular matrix multiplication revisited

Cited in

(2)

• Matrix product states and the quantum max-flow/min-cut conjectures
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more

This page was built for publication: Quantum and approximation algorithms for maximum witnesses of Boolean matrix products

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