On the fine-grained complexity of parity problems
From MaRDI portal
Cites work
- 3SUM, 3XOR, triangles
- Algorithms – ESA 2004
- Better approximations for tree sparsity in nearly-linear time
- Counting t-cliques: worst-case to average-case reductions and direct interactive proof systems
- Counting problems in parameterized complexity
- Counting solutions to polynomial systems via reductions
- Efficient algorithms for the maximum subarray problem by distance matrix multiplication
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster all-pairs shortest paths via circuit complexity
- Finding orthogonal vectors in discrete structures
- Finding, minimizing, and counting weighted subgraphs
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Fine-grained reductions from approximate counting to decision
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 1588478 (Why is no real title available?)
- scientific article; zbMATH DE number 1072530 (Why is no real title available?)
- scientific article; zbMATH DE number 1775405 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- scientific article; zbMATH DE number 7650401 (Why is no real title available?)
- Language edit distance and maximum likelihood parsing of stochastic grammars: faster algorithms and connection to fundamental graph problems
- Necklaces, convolutions, and \(X+Y\)
- New hardness results for planar graph problems in p and an algorithm for sparsest cut
- On a class of \(O(n^ 2)\) problems in computational geometry
- On problems as hard as CNF-SAT
- On problems equivalent to \((\min,+)\)-convolution
- Popular conjectures imply strong lower bounds for dynamic problems
- PP is as Hard as the Polynomial-Time Hierarchy
- Public-key cryptography in the fine-grained setting
- Some observations on holographic algorithms
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subcubic equivalences between path, matrix, and triangle problems
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- The complexity of computing the permanent
- The Parameterized Complexity of Counting Problems
- Threesomes, degenerates, and love triangles
- Tight hardness results for maximum weight rectangles
- Towards polynomial lower bounds for dynamic problems
This page was built for publication: On the fine-grained complexity of parity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842578)
