The pinwheel problem is NP-hard, implying hardness for related problems like bamboo garden trimming, and admits a PTAS that improves on the prior 9/7 approximation factor.
InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing(Vancouver, BC, Canada)(STOC 2024).AssociationforComputingMachinery,NewYork,NY,USA,1816–1819
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
The paper reformulates polymorphisms in CSPs and PCSPs as right Kan extensions and supplies purely categorical proofs that complexity is determined by these structures.
Languages requiring exponential-size circuits are comeager in S^E_2.
citing papers explorer
-
NP-Hardness and a PTAS for the Pinwheel Problem
The pinwheel problem is NP-hard, implying hardness for related problems like bamboo garden trimming, and admits a PTAS that improves on the prior 9/7 approximation factor.
-
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
-
A categorical perspective on constraint satisfaction: The wonderland of adjunctions
The paper reformulates polymorphisms in CSPs and PCSPs as right Kan extensions and supplies purely categorical proofs that complexity is determined by these structures.
-
Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
Languages requiring exponential-size circuits are comeager in S^E_2.