4 papers
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some such that given as input a -CSP ins…
PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
Venkatesan Guruswami, Xuandi Ren, Kewen Wu
The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring on…
Locally Sampleable Uniform Symmetric Distributions
Daniel M. Kane, Anthony Ostuni, Kewen Wu
We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let be a Boolean function where each outp…
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant such tha…