Amey Bhangale

activity

20142026

most citedRigid Matrices From Rectangular PCPs

16 citations · 45 across the 22 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.DM2017

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 $n$ unbiased Bernoulli random variables which are $n /2$ -wise independent. For general $k$ -wise independence, we g…

cs.DS2017★ 5 cited

Improved approximation algorithm for the Dense-3-Subhypergraph Problem

Amey Bhangale, Rajiv Gandhi, Guy Kortsarz

The study of Dense- $3$ -Subhypergraph problem was initiated in Chlamt{á}c et al. [Approx'16]. The input is a universe $U$ and collection $S$ of subsets of $U$ , each of size $…

cs.CC2017

An Improved Dictatorship Test with Perfect Completeness

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f : {0, 1}^{n} \to {0, 1}$ is called a dictator if it depends on exactly one variable i.e $f (x_{1}, x_{2}, \dots, x_{n}) = x_{i}$ for some $i \in [n]$ . In this wor…