12 citations · 13 across the 5 of their papers we have counts for
9 papers
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…
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…
Simplified inpproximability of hypergraph coloring via t-agreeing families
Per Austrin, Amey Bhangale, Aditya Potukuchi
We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal -agreeing families of . Sp…
Improved Inapproximability of Rainbow Coloring
Per Austrin, Amey Bhangale, Aditya Potukuchi
A rainbow -coloring of a -uniform hypergraph is a -coloring of the vertex set such that every hyperedge contains all colors. We prove that given a rainbow $(k - 2\lflo…
Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, Swastik Kopparty +2
In the simultaneous Max-Cut problem, we are given weighted graphs on the same set of vertices, and the goal is to find a cut of the vertex set so that the minimum, over the…
A short note on the joint entropy of n/2-wise independence
Amey Bhangale, Aditya Potukuchi
In this note, we prove a tight lower bound on the joint entropy of unbiased Bernoulli random variables which are -wise independent. For general -wise independence, we g…