CAREER: Social Computation: Fundamental Limits and Efficient Algorithms

点击翻译按钮获取中文摘要

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.