2 citations · 3 across the 14 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
cs.CC2024
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee +1
Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results fo…
cs.CC2024
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…