Analytical Tools in Probability for Social Choice Theory and Computer Science

这个项目试图回答以下问题。(1)如何设计选举，使其不会因错误计算或腐败选票而改变结果？”(2)“在计算机上聚集数据的最好方法是什么？”(3)“我们如何理解网络的几何结构？”问题(1)和(2)可以重新表述为等周问题。等周问题的一个例子是要求一个固定长度的篱笆的形状，这个篱笆包围了大部分的区域（答案是圆形的篱笆，自古以来就知道）。主要研究者研究的具体等周问题可以被描述为概率问题，本项目从微积分中开发了一些新的工具来处理这些问题。在20世纪50年代和60年代，博弈论学家对问题(1)的不同版本进行了广泛的研究，但在过去二十年中，理论计算机科学的研究重新引起了对问题(1)、(2)和(3)的兴趣。一般来说，理论计算机科学为计算机寻找尽可能快速有效地解决问题的方法。本项目发展了两种概率分析工具：变分法和曲率法。最近在概率论和理论计算机科学中的几个等周问题，如(1)和(2)要求最小高斯周长和固定高斯体积的欧几里得集合。Choksi和Sternberg在2007年取得的突破性成果允许将变分演算应用于这些优化问题，尽管其他人尚未使用变分工具来解决这些问题。首席研究员还将发展超收缩和对数索博列夫不等式的曲率理论。对于黎曼流形，Ricci曲率界暗示对数Sobolev不等式，Bakry和Emery在1985年的结果。本计画将探讨随机图上里奇曲率的不同概念。非交换对数Sobolev不等式的Ricci曲率理论也将被研究。

This project seeks to answer the following questions. (1) "How can we design an election so that the outcome does not change due to miscounted or corrupted votes?" (2) "What is the best way to cluster data on a computer?" (3) "How can we understand the geometry of networks?" Questions (1) and (2) can be reformulated as isoperimetric problems. One example of an isoperimetric problem asks for the shape of a fence of fixed length that encloses the most area (the answer being a circular fence, which was known since ancient times). The specific isoperimetric problems the principal investigator studies can be phrased as probabilistic problems, and this project develops some new tools from calculus to deal with these problems. Different versions of Question (1) have been studied extensively by game theorists in the 1950s and 1960s, but investigations in theoretical computer science in the last two decades have given renewed interest for Questions (1), (2), and (3). Generally speaking, theoretical computer science finds ways for computers to solve problems as quickly and as efficiently as possible.This project develops two analytic tools in probability: the calculus of variations and curvature. Several recent isoperimetric problems in probability and theoretical computer science such as (1) and (2) ask for the Euclidean sets of smallest Gaussian perimeter and fixed Gaussian volume. A breakthrough result of Choksi and Sternberg from 2007 allows the calculus of variations to be applied to these optimization problems, though others have not yet used variational tools for these problems. The principal investigator will also develop theories of curvature for hypercontractive and logarithmic Sobolev inequalities. For a Riemannian manifold, Ricci curvature bounds imply logarithmic Sobolev inequalities, a result of Bakry and Emery from 1985. In this project, different notions of Ricci curvature on random graphs will be investigated. Theories of Ricci curvature for noncommutative logarithmic Sobolev inequalities will also be investigated.