2 papers
cs.CC2023
Parameterized Inapproximability Hypothesis under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the numb…
cs.DS2020
Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun +1
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…