{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/158948"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/158948","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Tackling Algorithmic Problems on Massive Graphs","abstract":"As datasets grow increasingly larger, traditional computational models, which require reading the entire input, become impractical due to constraints on time, memory, and randomness. This thesis explores alternative algorithmic approaches for processing massive graphs under these constraints. Specifically, we focus on algorithms for the following graph problems. Motif Counting and Sampling: This involves developing efficient algorithms for counting and sampling small motifs (constant sized subgraphs) like stars and triangles, which are crucial for applications in biology, chemistry, and social networks. The thesis presents improved methods for both approximate and exact counting and sampling of general motifs. Graph Sparsification and Spanners: The problem of sparsifying graphs involves removing (usually most) edges of the input graph in a way that preserves essential properties such as connectivity and approximate distances. This thesis introduces algorithms for constructing sparse spanning graphs, as well spanners – sparse subgraphs that approximate distances up to a multiplicative factor. We obtain faster algorithms in parallel settings, and also initiate the study of average case graph inputs in the sublinear setting, and obtain results beyond the worst case lower bounds We investigate both of these problems in different models, including sublinear query access, local computation algorithms (LCAs), and the MPC model, and also discuss implications of these in distributed and parallel models of computation.","abstract_html":"As datasets grow increasingly larger, traditional computational models, which require reading the entire input, become impractical due to constraints on time, memory, and randomness. This thesis explores alternative algorithmic approaches for processing massive graphs under these constraints. Specifically, we focus on algorithms for the following graph problems. Motif Counting and Sampling: This involves developing efficient algorithms for counting and sampling small motifs (constant sized subgraphs) like stars and triangles, which are crucial for applications in biology, chemistry, and social networks. The thesis presents improved methods for both approximate and exact counting and sampling of general motifs. Graph Sparsification and Spanners: The problem of sparsifying graphs involves removing (usually most) edges of the input graph in a way that preserves essential properties such as connectivity and approximate distances. This thesis introduces algorithms for constructing sparse spanning graphs, as well spanners – sparse subgraphs that approximate distances up to a multiplicative factor. We obtain faster algorithms in parallel settings, and also initiate the study of average case graph inputs in the sublinear setting, and obtain results beyond the worst case lower bounds We investigate both of these problems in different models, including sublinear query access, local computation algorithms (LCAs), and the MPC model, and also discuss implications of these in distributed and parallel models of computation.","abstract_has_math":false,"creators":["Biswas, Amartya Shankha"],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Rubinfeld, Ronitt"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-02","date_published":"2025-02","updated_at":"2026-07-22T22:21:49Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"rights_urls":["https://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/158948","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Rubinfeld, Ronitt"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Biswas, Amartya Shankha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-03-27T16:59:56Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-03-27T16:59:56Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral","Doctor of Philosophy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/158948"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["As datasets grow increasingly larger, traditional computational models, which require reading the entire input, become impractical due to constraints on time, memory, and randomness. This thesis explores alternative algorithmic approaches for processing massive graphs under these constraints. Specifically, we focus on algorithms for the following graph problems. Motif Counting and Sampling: This involves developing efficient algorithms for counting and sampling small motifs (constant sized subgraphs) like stars and triangles, which are crucial for applications in biology, chemistry, and social networks. The thesis presents improved methods for both approximate and exact counting and sampling of general motifs. Graph Sparsification and Spanners: The problem of sparsifying graphs involves removing (usually most) edges of the input graph in a way that preserves essential properties such as connectivity and approximate distances. This thesis introduces algorithms for constructing sparse spanning graphs, as well spanners – sparse subgraphs that approximate distances up to a multiplicative factor. We obtain faster algorithms in parallel settings, and also initiate the study of average case graph inputs in the sublinear setting, and obtain results beyond the worst case lower bounds We investigate both of these problems in different models, including sublinear query access, local computation algorithms (LCAs), and the MPC model, and also discuss implications of these in distributed and parallel models of computation."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Tackling Algorithmic Problems on Massive Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Rubinfeld, Ronitt"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Biswas, Amartya Shankha"],"dc:date.accessioned":["2025-03-27T16:59:56Z"],"dc:date.available":["2025-03-27T16:59:56Z"],"dc:date.issued":["2025-02"],"dc:description.abstract":["As datasets grow increasingly larger, traditional computational models, which require reading the entire input, become impractical due to constraints on time, memory, and randomness. This thesis explores alternative algorithmic approaches for processing massive graphs under these constraints. Specifically, we focus on algorithms for the following graph problems. Motif Counting and Sampling: This involves developing efficient algorithms for counting and sampling small motifs (constant sized subgraphs) like stars and triangles, which are crucial for applications in biology, chemistry, and social networks. The thesis presents improved methods for both approximate and exact counting and sampling of general motifs. Graph Sparsification and Spanners: The problem of sparsifying graphs involves removing (usually most) edges of the input graph in a way that preserves essential properties such as connectivity and approximate distances. This thesis introduces algorithms for constructing sparse spanning graphs, as well spanners – sparse subgraphs that approximate distances up to a multiplicative factor. We obtain faster algorithms in parallel settings, and also initiate the study of average case graph inputs in the sublinear setting, and obtain results beyond the worst case lower bounds We investigate both of these problems in different models, including sublinear query access, local computation algorithms (LCAs), and the MPC model, and also discuss implications of these in distributed and parallel models of computation."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/158948"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"dc:rights.uri":["https://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Tackling Algorithmic Problems on Massive Graphs"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral","Doctor of Philosophy"]},"updated_at":"2026-07-22T22:21:49Z"}