{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/144952"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/144952","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Local Algorithms for Sparsification of Average-case Graphs","abstract":"Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case graphs require Ω(√ 𝑛) probes in order to detect whether a specific edge 𝑒 ∈ 𝐺′ . We want to show that, in expectation, this task can be accomplished much faster, by considering average-case graphs such as Erdos-Renyi random graphs and the Preferential Attachment model. We first present an LCA algorithm which, on an Erdos-Renyi graph input 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛) 𝑛 ), gives fast access to a sparsification 𝐺′ of 𝐺, such that 𝐺′ is connected and has 𝑛+𝑜(𝑛) edges. Queries to 𝐺′ are answered 𝒪(∆ log2 (𝑛)) probes to 𝐺 (where ∆ = 𝒪(𝑝𝑛) is the maximum degree). We then show an LCA algorithm that, for an Erdos-Renyi graph 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛)/√ 𝑛 ), gives access to a 4-spanner 𝐺′ of 𝐺 in 𝒪(log2/(𝑛)) probes in expectation per query, such that 𝐺′ has at most 2𝑛 edges. Finally, we give an LCA that runs on a Preferential Attachment graph 𝐺 with edge parameter Θ(log(𝑛)), which gives fast access to a sparsification 𝐺′ of 𝐺 where 𝐺′ is connected and has 𝑛 + 𝑜(𝑛) edges. Each query to 𝐺′ takes an expected 𝒪(log3 (𝑛)) probes to 𝐺.","abstract_html":"Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case graphs require Ω(√ 𝑛) probes in order to detect whether a specific edge 𝑒 ∈ 𝐺′ . We want to show that, in expectation, this task can be accomplished much faster, by considering average-case graphs such as Erdos-Renyi random graphs and the Preferential Attachment model. We first present an LCA algorithm which, on an Erdos-Renyi graph input 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛) 𝑛 ), gives fast access to a sparsification 𝐺′ of 𝐺, such that 𝐺′ is connected and has 𝑛+𝑜(𝑛) edges. Queries to 𝐺′ are answered 𝒪(∆ log2 (𝑛)) probes to 𝐺 (where ∆ = 𝒪(𝑝𝑛) is the maximum degree). We then show an LCA algorithm that, for an Erdos-Renyi graph 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛)/√ 𝑛 ), gives access to a 4-spanner 𝐺′ of 𝐺 in 𝒪(log2/(𝑛)) probes in expectation per query, such that 𝐺′ has at most 2𝑛 edges. Finally, we give an LCA that runs on a Preferential Attachment graph 𝐺 with edge parameter Θ(log(𝑛)), which gives fast access to a sparsification 𝐺′ of 𝐺 where 𝐺′ is connected and has 𝑛 + 𝑜(𝑛) edges. Each query to 𝐺′ takes an expected 𝒪(log3 (𝑛)) probes to 𝐺.","abstract_has_math":false,"creators":["Cao, Ruidi"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","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":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:21:24Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/144952","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":["Cao, Ruidi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-29T16:23:11Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-29T16:23:11Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-05"]},{"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":["Master","Master of Engineering in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://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/144952"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case graphs require Ω(√ 𝑛) probes in order to detect whether a specific edge 𝑒 ∈ 𝐺′ . We want to show that, in expectation, this task can be accomplished much faster, by considering average-case graphs such as Erdos-Renyi random graphs and the Preferential Attachment model. We first present an LCA algorithm which, on an Erdos-Renyi graph input 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛) 𝑛 ), gives fast access to a sparsification 𝐺′ of 𝐺, such that 𝐺′ is connected and has 𝑛+𝑜(𝑛) edges. Queries to 𝐺′ are answered 𝒪(∆ log2 (𝑛)) probes to 𝐺 (where ∆ = 𝒪(𝑝𝑛) is the maximum degree). We then show an LCA algorithm that, for an Erdos-Renyi graph 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛)/√ 𝑛 ), gives access to a 4-spanner 𝐺′ of 𝐺 in 𝒪(log2/(𝑛)) probes in expectation per query, such that 𝐺′ has at most 2𝑛 edges. Finally, we give an LCA that runs on a Preferential Attachment graph 𝐺 with edge parameter Θ(log(𝑛)), which gives fast access to a sparsification 𝐺′ of 𝐺 where 𝐺′ is connected and has 𝑛 + 𝑜(𝑛) edges. Each query to 𝐺′ takes an expected 𝒪(log3 (𝑛)) probes to 𝐺."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Local Algorithms for Sparsification of Average-case Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Rubinfeld, Ronitt"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Cao, Ruidi"],"dc:date.accessioned":["2022-08-29T16:23:11Z"],"dc:date.available":["2022-08-29T16:23:11Z"],"dc:date.issued":["2022-05"],"dc:description.abstract":["Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case graphs require Ω(√ 𝑛) probes in order to detect whether a specific edge 𝑒 ∈ 𝐺′ . We want to show that, in expectation, this task can be accomplished much faster, by considering average-case graphs such as Erdos-Renyi random graphs and the Preferential Attachment model. We first present an LCA algorithm which, on an Erdos-Renyi graph input 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛) 𝑛 ), gives fast access to a sparsification 𝐺′ of 𝐺, such that 𝐺′ is connected and has 𝑛+𝑜(𝑛) edges. Queries to 𝐺′ are answered 𝒪(∆ log2 (𝑛)) probes to 𝐺 (where ∆ = 𝒪(𝑝𝑛) is the maximum degree). We then show an LCA algorithm that, for an Erdos-Renyi graph 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛)/√ 𝑛 ), gives access to a 4-spanner 𝐺′ of 𝐺 in 𝒪(log2/(𝑛)) probes in expectation per query, such that 𝐺′ has at most 2𝑛 edges. Finally, we give an LCA that runs on a Preferential Attachment graph 𝐺 with edge parameter Θ(log(𝑛)), which gives fast access to a sparsification 𝐺′ of 𝐺 where 𝐺′ is connected and has 𝑛 + 𝑜(𝑛) edges. Each query to 𝐺′ takes an expected 𝒪(log3 (𝑛)) probes to 𝐺."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/144952"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Local Algorithms for Sparsification of Average-case Graphs"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:21:24Z"}