权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Analytical Tools in Probability for Social Choice Theory and Computer Science

社会选择理论和计算机科学的概率分析工具

基本信息

批准号：
1839406
负责人：
Steven Heilman
金额：
$ 4.65万
依托单位：
University of Southern California
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2020-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1839406&HistoricalAwards=false
关键词：
Analytical Tools Probability Social Choice

项目摘要

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.

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