Analytical Tools in Probability for Social Choice Theory and Computer Science

本项目旨在回答以下问题。(1)“我们如何设计一场选举，使结果不会因为错误计数或腐败的选票而改变？“（2）“在计算机上聚类数据的最佳方法是什么？“（3）“我们如何理解网络的几何结构？问题（1）和（2）可以重新表述为等周问题。 等周问题的一个例子是要求一个固定长度的栅栏的形状，它包围了最大的面积（答案是圆形栅栏，自古以来就被称为）。 主要研究者所研究的具体等周问题可以表述为概率问题，本项目从微积分中开发了一些新的工具来处理这些问题。 问题（1）的不同版本在20世纪50年代和60年代被博弈论家广泛研究，但在过去的二十年中，理论计算机科学的研究重新引起了对问题（1），（2）和（3）的兴趣。 一般来说，理论计算机科学为计算机找到尽可能快速和有效地解决问题的方法。本项目开发了两种概率分析工具：变分法和曲率。 最近在概率论和理论计算机科学中的几个等周问题，如（1）和（2）要求最小高斯周长和固定高斯体积的欧几里得集。 Choksi和斯滕贝格在2007年的一个突破性成果允许变分法应用于这些优化问题，尽管其他人还没有使用变分工具来解决这些问题。 首席研究员还将开发曲率理论的超压缩和对数Sobolev不等式。 对于一个黎曼流形，Ricci曲率界包含对数Sobolev不等式，这是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.