University of Illinois Urbana-Champaign

Social computation: Fundamental limits and efficient algorithms

Khetan, Ashish Kumar

Content Files
KHETAN-DISSERTATION-2018.pdf

Permalink

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

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
Date of Ingest
2018-09-04T20:27:12Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering