{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/100996"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/100996","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Social computation: Fundamental limits and efficient algorithms","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","abstract_has_math":false,"creators":["Khetan, Ashish Kumar"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Oh, Sewoong","Hajek, Bruce","Sun, Ruoyu","Viswanath, Pramod"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-04T20:27:12Z","date_published":"2018-09-04T20:27:12Z","updated_at":"2026-07-22T22:24:38Z","subjects":["Ranking, Crowdsourcing"],"languages":["en"],"rights":["Copyright 2018 Ashish Kumar Khetan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/100996","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Oh, Sewoong","Hajek, Bruce","Sun, Ruoyu","Viswanath, Pramod"]},{"key":"dc:creator","label":"Author","values":["Khetan, Ashish Kumar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-04T20:27:12Z","2018-04-17","2018-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Ranking, Crowdsourcing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Ashish Kumar Khetan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/100996"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","The student, Ashish Kumar Khetan, accepted the attached license on 2018-04-16 at 19:46.","The student, Ashish Kumar Khetan, submitted this Dissertation for approval on 2018-04-16 at 19:53.","This Dissertation was approved for publication on 2018-04-17 at 16:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12291 on 2018-08-31 at 17:13:12","Made available in DSpace on 2018-09-04T20:27:12Z (GMT). No. of bitstreams: 3 KHETAN-DISSERTATION-2018.pdf: 2970343 bytes, checksum: fd1f0899c282e35397079feda70785da (MD5) LICENSE.txt: 4216 bytes, checksum: 603236ee30df325a49ac03ec8799ccc7 (MD5) PROQUEST_LICENSE.txt: 4562 bytes, checksum: c86465ee5f900e6a72d50408a79a577a (MD5) Previous issue date: 2018-04-17","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Social computation: Fundamental limits and efficient algorithms"]}]}],"canonical_facts":{"dc:contributor":["Oh, Sewoong","Hajek, Bruce","Sun, Ruoyu","Viswanath, Pramod"],"dc:creator":["Khetan, Ashish Kumar"],"dc:date":["2018-09-04T20:27:12Z","2018-04-17","2018-05"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","The student, Ashish Kumar Khetan, accepted the attached license on 2018-04-16 at 19:46.","The student, Ashish Kumar Khetan, submitted this Dissertation for approval on 2018-04-16 at 19:53.","This Dissertation was approved for publication on 2018-04-17 at 16:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12291 on 2018-08-31 at 17:13:12","Made available in DSpace on 2018-09-04T20:27:12Z (GMT). No. of bitstreams: 3 KHETAN-DISSERTATION-2018.pdf: 2970343 bytes, checksum: fd1f0899c282e35397079feda70785da (MD5) LICENSE.txt: 4216 bytes, checksum: 603236ee30df325a49ac03ec8799ccc7 (MD5) PROQUEST_LICENSE.txt: 4562 bytes, checksum: c86465ee5f900e6a72d50408a79a577a (MD5) Previous issue date: 2018-04-17","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."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/100996"],"dc:language":["en"],"dc:rights":["Copyright 2018 Ashish Kumar Khetan"],"dc:subject":["Ranking, Crowdsourcing"],"dc:title":["Social computation: Fundamental limits and efficient algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:38Z"}