Quantum and approximation algorithms for maximum witnesses of Boolean matrix products

DOI10.1007/978-3-030-67899-9_35OpenAlexW3127716543MaRDI QIDQ831754FDOQ831754

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Powers of tensors and fast matrix multiplication
• Multiplying matrices faster than coppersmith-winograd
• A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication
• Fast rectangular matrix multiplication and applications
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Rectangular matrix multiplication revisited
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding heaviest H -subgraphs in real weighted graphs, with applications
• On minimum witnesses for Boolean matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• Faster multi-witnesses for Boolean matrix multiplication

Cited In (3)

• Matrix product states and the quantum max-flow/min-cut conjectures
• Improving quantum query complexity of Boolean matrix multiplication using graph collision
• 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)