Modular construction of succinct arguments for QMA via OSP-based interactive protocol plus collapsing-hash communication compression compiler, without LWE.
Title resolution pending
7 Pith papers cite this work, alongside 1,420 external citations. Polarity classification is still indexing.
7
Pith papers citing it
1,420
external citations · external index
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
A new reduction converts constant-gap PCPs from imperfect to perfect completeness with small overhead and proves equivalence of Gap-ETH variants with and without perfect completeness.
Approximating the quantum value of tilted XOR games to constant precision is RE-complete, implying binary nonlocal games are RE-hard to approximate.
An FPT-time O(2^k log n)-approximation is given for k-MMSA_3, alongside gap-preserving reductions clarifying inapproximability across the MMSA hierarchy.
Proves ∃R-hardness of approximating MAX-ETR-INV to within a constant factor and gives polynomial-time 8-factor and nondeterministic 2-factor approximation algorithms.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
citing papers explorer
-
A Modular Approach to Succinct Arguments for QMA
Modular construction of succinct arguments for QMA via OSP-based interactive protocol plus collapsing-hash communication compression compiler, without LWE.
-
Streaming Complexity Separations for Dense and Sparse Graphs
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
-
Imperfect Gaps in Gap-ETH and PCPs
A new reduction converts constant-gap PCPs from imperfect to perfect completeness with small overhead and proves equivalence of Gap-ETH variants with and without perfect completeness.
-
XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
Approximating the quantum value of tilted XOR games to constant precision is RE-complete, implying binary nonlocal games are RE-hard to approximate.
-
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
An FPT-time O(2^k log n)-approximation is given for k-MMSA_3, alongside gap-preserving reductions clarifying inapproximability across the MMSA hierarchy.
-
Probabilistically checkable proofs for the Existential Theory of the Reals
Proves ∃R-hardness of approximating MAX-ETR-INV to within a constant factor and gives polynomial-time 8-factor and nondeterministic 2-factor approximation algorithms.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.