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
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
verdicts
UNVERDICTED 5representative citing papers
Any 1-PRS can be amplified to t-PRS for polynomial t by randomness accounting and quantum extractors that eliminate arbitrary ancilla.
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.
-
Generic Number-of-Copies Amplification for Pseudorandom States
Any 1-PRS can be amplified to t-PRS for polynomial t by randomness accounting and quantum extractors that eliminate arbitrary ancilla.
-
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.