39 citations · 65 across the 14 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
quant-ph2014★ 39 cited
Gaussian Noise Sensitivity and BosonSampling
Gil Kalai, Guy Kindler
We study the sensitivity to noise of |permanent(X)|^2 for random real and complex n x n Gaussian matrices X, and show that asymptotically the correlation between the noisy and nois…
cs.CC2014★ 1 cited
Unique Games on the Hypercube
Naman Agarwal, Guy Kindler, Alexandra Kolla +1
In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instanc…