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 5representative citing papers
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
-
Node-Weighted Triangles: Faster and Simpler
Node-weighted triangle detection can be solved in optimal O(MM(n)) time with a simpler algorithm than previous work.
-
Approximation Preserving Coresets
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.