Files in this item

FilesDescriptionFormat

application/pdf

application/pdfKHETAN-DISSERTATION-2018.pdf (3MB)
(no description provided)PDF

Description

Title:Social computation: Fundamental limits and efficient algorithms
Author(s):Khetan, Ashish Kumar
Director of Research:Oh, Sewoong
Doctoral Committee Chair(s):Oh, Sewoong
Doctoral Committee Member(s):Hajek, Bruce; Sun, Ruoyu; Viswanath, Pramod
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2018-04-17
Type:Thesis
URI:http://hdl.handle.net/2142/100996
Rights Information:Copyright 2018 Ashish Kumar Khetan
Date Available in IDEALS:2018-09-04
Date Deposited:2018-05


This item appears in the following Collection(s)

Item Statistics