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.