scientific article; zbMATH DE number 7378726
From MaRDI portal
Publication:5009621
DOI10.4230/LIPIcs.ESA.2018.56MaRDI QIDQ5009621
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1806.09189
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 3SUM, 3XOR, triangles
- Improving quantum query complexity of Boolean matrix multiplication using graph collision
- Certifying algorithms
- On the deterministic complexity of factoring polynomials over finite fields
- Matrix multiplication via arithmetic progressions
- A note on compressed sensing and the complexity of matrix multiplication
- A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
- General context-free recognition in less than cubic time
- On the exponent of all pairs shortest path problem
- On a class of \(O(n^ 2)\) problems in computational geometry
- Efficiently correcting matrix products
- Subquadratic algorithms for 3SUM
- Gaussian elimination is not optimal
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Modern Computer Algebra
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm
- Powers of tensors and fast matrix multiplication
- Fast Output-Sensitive Matrix Multiplication
- Quantum verification of matrix products
- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
- Threesomes, Degenerates, and Love Triangles
- Error Correction in Fast Matrix Multiplication and Inverse
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Near-optimal linear decision trees for k-SUM and related problems
- Faster all-pairs shortest paths via circuit complexity
- More Applications of the Polynomial Method to Algorithm Design
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Deterministic methods to find primes
- Multiplying matrices faster than coppersmith-winograd
- Compressed matrix multiplication
- On the complexity of \(k\)-SAT
This page was built for publication: