Social computation: Fundamental limits and efficient algorithms

Khetan, Ashish Kumar

Permalink

https://hdl.handle.net/2142/100996 Copy

Description

Title

Social computation: Fundamental limits and efficient algorithms

Author(s)

Khetan, Ashish Kumar

Issue Date

2018-04-17

Director of Research (if dissertation) or Advisor (if thesis)

Oh, Sewoong

Doctoral Committee Chair(s)

Oh, Sewoong

Committee Member(s)

• Hajek, Bruce
• Sun, Ruoyu
• Viswanath, Pramod

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Ranking, Crowdsourcing

Abstract

Social computing systems bring enormous value to society by harnessing the data generated by the members of a community. Though each individual reveals a little information through his online traces, collectively this information gives significant insights on the societal preferences that can be used in designing better systems for the society. Challenging societal problems can be solved using the collective power of a crowd wherein each individual offers only a limited knowledge on a specifically designed online platform. There exists general approaches to design such online platforms, to aggregate the collected data, and to use them for the downstream tasks, but are typically sub-optimal and inefficient. In this work, we investigate several social computing problems and provide efficient algorithms for solving them. This work studies several topics: (a) designing efficient algorithms for aggregating preferences from partially observed traces of online activities, and characterizing the fundamental trade-off between the computational complexity and statistical efficiency; (b) characterizing the fundamental trade-off between the budget and accuracy in aggregated answers in crowdsourcing systems, and designing efficient algorithms for training supervised learning models using the crowdsourced answers; (c) designing efficient algorithms for estimating fundamental spectral properties of a partially observed data such as a movie rating data matrix in recommendation systems, and connections in a large network.

Graduation Semester

2018-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/100996

Copyright and License Information

Copyright 2018 Ashish Kumar Khetan

Owning Collections