An oracle exists relative to which TAUT has neither optimal proof systems nor recursive jump operators (even with infinite PH), showing Khaniki's question is not relativizably provable.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages =
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
years
2026 5verdicts
UNVERDICTED 5representative citing papers
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.
Node-weighted triangle detection can be solved in optimal O(MM(n)) time with a simpler algorithm than previous work.
Explicit CSS quantum codes with transversal CCZ, [[N, Θ(N), Ω(N^{1/m})]] parameters for m≥3, sublinear Z-stabilizer generators, extended to fixed prime fields with near-linear dimension and n^{1/m} distance up to polylog factors.
Introduces approximation-preserving coresets that guarantee cost preservation for near-optimal solutions and proves that even tiny approximation-factor distortion forbids coresets of that size.
citing papers explorer
-
Quantum Codes with Transversal $CCZ$ Gates and Sublinear $Z$-Stabilizers
Explicit CSS quantum codes with transversal CCZ, [[N, Θ(N), Ω(N^{1/m})]] parameters for m≥3, sublinear Z-stabilizer generators, extended to fixed prime fields with near-linear dimension and n^{1/m} distance up to polylog factors.