Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

A tight quantitative version of Arrow’s impossibility theorem

Nathan Keller — 2012

Journal of the European Mathematical Society

The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any ϵ > 0 , there exists δ = δ ( ϵ ) such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive...

Geometric influences II: Correlation inequalities and noise sensitivity

Nathan Keller;  Elchanan Mossel;  Arnab Sen — 2014

Annales de l'I.H.P. Probabilités et statistiques

In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand’s lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini–Kalai–Schramm (BKS) noise sensitivity theorem....

Page 1

Download Results (CSV)