CAREER: Social Computation: Fundamental Limits and Efficient Algorithms

社会计算系统通过利用社区成员产生的数据为社会带来巨大的价值。虽然每个人单独只能提供有限的知识、时间和努力，但群体在一起可以解决具有挑战性的社会问题。从人群中汇总此类数据的一般方法是存在的，但通常不是最优的，效率也不高。这个项目应用信息论技术来探索社会计算中的基本样本/计算/精度权衡。拟议研究的成功将朝着一个有效地从其成员的活动中学习以实现更大的社会利益的社会取得进展。拟议的研究与一项教育计划紧密结合在一起，该计划旨在开发一门新的研究生课程，内容是社会计算的算法基础和创新的自适应学习平台，将社会计算技术融入教育领域。该项目将调查几个主题：(1)通过应用信息论工具和方法，表征众包平台中可用预算和答案准确性之间的基本权衡；(2)使用谱图理论和编码理论的技术，以及通过应用一系列新的排序打破方法来降低复杂性，设计实现这一基本权衡的高效算法；以及(3)表征计算复杂性、样本大小和从部分观察到的在线和移动活动的痕迹收集偏好时的准确性之间的三个基本权衡。

Social computing systems bring enormous value to society by harnessing the data generated by members of a community. While each individual alone can offer only limited knowledge, time, and effort, a crowd together can solve challenging societal problems. General approaches to aggregate such data from crowds exists, but are typically suboptimal and inefficient. This project applies information-theoretic techniques to explore the fundamental sample/computation/accuracy trade-offs in social computing. The success of the proposed research will make progress towards a society that efficiently learns from the activities of its members for greater societal good. The proposed research is strongly integrated with an education plan that aims to develop a new graduate course on algorithmic foundations of social computing and innovative adaptive learning platforms that integrates the technology of social computing into the domain of education. The project will investigate several topics: (1) characterizing the fundamental trade-offs between the available budget and the accuracy of the answers in crowd-sourcing platforms, by applying information-theoretic tools and methods; (2) designing efficient algorithms achieving this fundamental trade-off using techniques from spectral graph theory and coding theory, as well as by applying a family of novel rank-breaking approaches to reduce complexity; and (3) characterizing the three-way fundamental trade-offs between computational complexity, sample size, and accuracy in aggregating preferences from partially observed traces of online and mobile activities.