Analytical Tools in Probability for Social Choice Theory and Computer Science

本项目试图回答以下问题。(1)“我们如何设计一场选举，使结果不会因为错误计算或损坏的选票而改变？”(2)“在计算机上聚集数据的最佳方式是什么？”(3)“我们如何理解网络的几何形状？”问题(1)和(2)可以重新表述为等周问题。等周问题的一个例子是要求固定长度的栅栏的形状，该栅栏包围了最大的区域(答案是圆形栅栏，这是自古以来就知道的)。主要研究人员研究的特定等周问题可以归结为概率问题，本项目从微积分的角度开发了一些新的工具来处理这些问题。在20世纪50年代和60年代，博弈论学者对问题(1)的不同版本进行了广泛的研究，但在过去20年里，理论计算机科学的研究重新引起了人们对问题(1)、(2)和(3)的兴趣。一般说来，理论计算机科学会找到让计算机尽可能快速高效地解决问题的方法。这个项目开发了两个概率分析工具：变分法和曲率演算。最近概率和理论计算机科学中的几个等周问题，如(1)和(2)要求最小高斯周长和固定高斯体积的欧几里德集。Choksi和Sternberg在2007年的一个突破性结果允许变分法应用于这些优化问题，尽管其他人还没有使用变分工具来解决这些问题。主要研究人员还将发展超压缩型和对数索波列夫不等式的曲率理论。对于黎曼流形，Ricci曲率界蕴含着对数Sobolv不等式，这是Bakry和Emery在1985年得出的结果。在这个项目中，我们将研究随机图上的Ricci曲率的不同概念。非对易对数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.