12 citations · 22 across the 18 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
Optimal Inapproximability of Satisfiable -LIN over Non-Abelian Groups
Amey Bhangale, Subhash Khot
A seminal result of Håstad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies fraction of the constraints of a…
cs.CC2020
Hardness of Approximation of (Multi-)LCS over Small Alphabet
Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar
The problem of finding longest common subsequence (LCS) is one of the fundamental problems in computer science, which finds application in fields such as computational biology, tex…
cs.CC2020
Rigid Matrices From Rectangular PCPs
Amey Bhangale, Prahladh Harsha, Orr Paradise +1
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned…