Improved Merlin-Arthur protocols for central problems in fine-grained complexity
From MaRDI portal
(Redirected from Publication:6174820)
Cites work
- 3SUM, 3XOR, triangles
- A fast method for interpolation using preconditioning
- A short note on Merlin-Arthur protocols for subset sum
- Algebrization: a new barrier in complexity theory
- An axiomatic approach to algebrization
- An equivalence class for orthogonal vectors
- Average-case fine-grained hardness
- Completeness for first-order properties on sparse structures with algorithmic applications
- Computing Partitions with Applications to the Knapsack Problem
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Constant-round interactive proofs for delegating computation
- Dense subset sum may be the hardest
- Deterministic APSP, Orthogonal Vectors, and More
- Fast polynomial factorization and modular composition
- Faster algorithms for all-pairs bounded min-cuts
- Faster all-pairs shortest paths via circuit complexity
- Finding a Minimum Circuit in a Graph
- Finding four-node subgraphs in triangle time
- Finding, minimizing, and counting weighted subgraphs
- How proofs are prepared at Camelot (extended abstract)
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 3759550 (Why is no real title available?)
- scientific article; zbMATH DE number 3539809 (Why is no real title available?)
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- scientific article; zbMATH DE number 7650137 (Why is no real title available?)
- scientific article; zbMATH DE number 7758324 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Listing triangles
- More applications of the polynomial method to algorithm design
- Multiplying matrices faster than coppersmith-winograd
- Necklaces, convolutions, and \(X+Y\)
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On a class of \(O(n^ 2)\) problems in computational geometry
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- On problems equivalent to \((\min,+)\)-convolution
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- Powers of tensors and fast matrix multiplication
- Proofs of Work from worst-case assumptions
- Public-key cryptography in the fine-grained setting
- Relativized isomorphisms of NP-complete sets
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- 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 landscape of communication complexity classes
- Tight hardness for shortest cycles and paths in sparse graphs
- Tight hardness results for maximum weight rectangles
- Towards polynomial lower bounds for dynamic problems
- Worst-Case to Average-Case Reductions for Subclasses of P
Cited in
(3)- Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonal
- An enumerative perspective on connectivity
- New algorithms for pigeonhole equal subset sum
This page was built for publication: Improved Merlin-Arthur protocols for central problems in fine-grained complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174820)
