Improved Merlin-Arthur protocols for central problems in fine-grained complexity
From MaRDI portal
Publication:6174820
DOI10.1007/s00453-023-01102-6OpenAlexW4321215153MaRDI QIDQ6174820
Ce Jin, Shyan S. Akmal, Unnamed Author, R. Ryan Williams, Lijie Chen
Publication date: 17 August 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-023-01102-6
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 3SUM, 3XOR, triangles
- A short note on Merlin-Arthur protocols for subset sum
- Necklaces, convolutions, and \(X+Y\)
- Relativized isomorphisms of NP-complete sets
- A fast method for interpolation using preconditioning
- The landscape of communication complexity classes
- Proofs of Work from worst-case assumptions
- On a class of \(O(n^ 2)\) problems in computational geometry
- Public-key cryptography in the fine-grained setting
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Finding, Minimizing, and Counting Weighted Subgraphs
- Towards polynomial lower bounds for dynamic problems
- Algebrization
- Fast Polynomial Factorization and Modular Composition
- Powers of tensors and fast matrix multiplication
- Computing Partitions with Applications to the Knapsack Problem
- Finding a Minimum Circuit in a Graph
- Faster All-Pairs Shortest Paths via Circuit Complexity
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Tight Hardness Results for Maximum Weight Rectangles
- Dense Subset Sum may be the hardest
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- On Problems Equivalent to (min,+)-Convolution
- Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
- Average-case fine-grained hardness
- Constant-Round Interactive Proofs for Delegating Computation
- Deterministic APSP, Orthogonal Vectors, and More
- Worst-Case to Average-Case Reductions for Subclasses of P
- Constant-Round Interactive Proof Systems for AC0[2 and NC1]
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Listing Triangles
- An axiomatic approach to algebrization
- An Equivalence Class for Orthogonal Vectors
- How Proofs are Prepared at Camelot
- More Applications of the Polynomial Method to Algorithm Design
- Finding Four-Node Subgraphs in Triangle Time
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Multiplying matrices faster than coppersmith-winograd
- On the complexity of \(k\)-SAT
This page was built for publication: Improved Merlin-Arthur protocols for central problems in fine-grained complexity
