{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/120434"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/120434","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"New directions in sublinear algorithms and testing properties of distributions","abstract":"This thesis deals with sublinear algorithms for various types of problems in statistics, combinatorial optimization and graph algorithms. A first focus of this thesis is algorithms for testing whether a probability distribution, to which the algorithms have sample access, is equal to a given hypothesis distribution, using a number of samples that is sublinear in the domain size. A second focus is to consider various other models of computation defined by type of queries available to the user. This thesis shows how more powerful queries, such as the ability to get a sample according to the conditional distribution on a specified set, allows one to get faster algorithms for a number of problems. Thirdly, this thesis considers the problem of certifying and correcting the result of a crowdsourced computation with potentially erroneous worker reports, by using verification queries on a sublinear number of reports. Finally, we show improved methods to simulate graph algorithms for maximal independent set, minimum vertex cover and maximum matching by distributing the computation to multiple sublinear space computing machines and allowing only a sublinear number of rounds of communication between them.","abstract_html":"This thesis deals with sublinear algorithms for various types of problems in statistics, combinatorial optimization and graph algorithms. A first focus of this thesis is algorithms for testing whether a probability distribution, to which the algorithms have sample access, is equal to a given hypothesis distribution, using a number of samples that is sublinear in the domain size. A second focus is to consider various other models of computation defined by type of queries available to the user. This thesis shows how more powerful queries, such as the ability to get a sample according to the conditional distribution on a specified set, allows one to get faster algorithms for a number of problems. Thirdly, this thesis considers the problem of certifying and correcting the result of a crowdsourced computation with potentially erroneous worker reports, by using verification queries on a sublinear number of reports. Finally, we show improved methods to simulate graph algorithms for maximal independent set, minimum vertex cover and maximum matching by distributing the computation to multiple sublinear space computing machines and allowing only a sublinear number of rounds of communication between them.","abstract_has_math":false,"creators":["Gouleakis, Themistoklis"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Ronitt Rubinfeld."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:22:26Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/120434","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ronitt Rubinfeld."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Gouleakis, Themistoklis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-02-14T15:51:15Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-02-14T15:51:15Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/120434"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 189-200)."]},{"key":"dc:description.abstract","label":"Abstract","values":["This thesis deals with sublinear algorithms for various types of problems in statistics, combinatorial optimization and graph algorithms. A first focus of this thesis is algorithms for testing whether a probability distribution, to which the algorithms have sample access, is equal to a given hypothesis distribution, using a number of samples that is sublinear in the domain size. A second focus is to consider various other models of computation defined by type of queries available to the user. This thesis shows how more powerful queries, such as the ability to get a sample according to the conditional distribution on a specified set, allows one to get faster algorithms for a number of problems. Thirdly, this thesis considers the problem of certifying and correcting the result of a crowdsourced computation with potentially erroneous worker reports, by using verification queries on a sublinear number of reports. Finally, we show improved methods to simulate graph algorithms for maximal independent set, minimum vertex cover and maximum matching by distributing the computation to multiple sublinear space computing machines and allowing only a sublinear number of rounds of communication between them."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["New directions in sublinear algorithms and testing properties of distributions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ronitt Rubinfeld."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Gouleakis, Themistoklis"],"dc:date.accessioned":["2019-02-14T15:51:15Z"],"dc:date.available":["2019-02-14T15:51:15Z"],"dc:date.issued":["2018"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 189-200)."],"dc:description.abstract":["This thesis deals with sublinear algorithms for various types of problems in statistics, combinatorial optimization and graph algorithms. A first focus of this thesis is algorithms for testing whether a probability distribution, to which the algorithms have sample access, is equal to a given hypothesis distribution, using a number of samples that is sublinear in the domain size. A second focus is to consider various other models of computation defined by type of queries available to the user. This thesis shows how more powerful queries, such as the ability to get a sample according to the conditional distribution on a specified set, allows one to get faster algorithms for a number of problems. Thirdly, this thesis considers the problem of certifying and correcting the result of a crowdsourced computation with potentially erroneous worker reports, by using verification queries on a sublinear number of reports. Finally, we show improved methods to simulate graph algorithms for maximal independent set, minimum vertex cover and maximum matching by distributing the computation to multiple sublinear space computing machines and allowing only a sublinear number of rounds of communication between them."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/120434"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["New directions in sublinear algorithms and testing properties of distributions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:26Z"}