16 citations · 45 across the 22 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
On Fortification of Projection Games
Amey Bhangale, Ramprasad Saptharishi, Girish Varma +1
A recent result of Moshkovitz \cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection g…
cs.CC2015★ 12 cited
The complexity of computing the minimum rank of a sign pattern matrix
Amey Bhangale, Swastik Kopparty
We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and…