Show simple item record

dc.contributor.authorGuo, Patrick
dc.date.accessioned2020-08-28T09:31:34Z
dc.date.created2019-05
dc.date.issued2019-08-23
dc.date.submitted2019
dc.identifier.citationGuo, Patrick. 2019. Lower Bounds for Graph Stream Algorithms Through the Boolean Hidden Matching Problem. Bachelor's thesis, Harvard College.
dc.identifier.urihttps://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364610*
dc.description.abstractSpace lower bounds for streaming algorithms are frequently proven through reductions from communication complexity problems. We study reductions from a specific communication problem, Boolean Hidden Matching (BHM), to various graph streaming algorithms. Variants of BHM have been shown to reduce to (and give the current best lower bounds for) triangle counting, maxcut approximation, and maximum matching approximation. Though the graph problems are seemingly dissimilar, the communication problems they reduce from are all based on BHM, and moreover all have lower bounds established through Fourier analysis. This thesis examines why such a communication problem is successful in capturing the hardness of these graph problems. We review the original proof of the lower bound for BHM and discuss the aspects which likely motivated using Fourier analysis. Next, we review three BHM variants and the graph problems they reduce to. From this, we identify characteristics of graph problems that suggest reduction from BHM to be a good candidate for capturing the hardness of the graph problem. Then, we consider the problem of counting connected components in regular bipartite graphs, and we establish a streaming lower bound through reducing from BHM. Finally, we adapt a variant of BHM for the same problem which we show gives a stronger bound for a specific subclass of streaming algorithms.
dc.description.sponsorshipComputer Science
dc.description.sponsorshipComputer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.titleLower Bounds for Graph Stream Algorithms Through the Boolean Hidden Matching Problem
dc.typeThesis or Dissertation
dash.depositing.authorGuo, Patrick
dc.date.available2020-08-28T09:31:34Z
thesis.degree.date2019
thesis.degree.grantorHarvard College
thesis.degree.grantorHarvard College
thesis.degree.levelUndergraduate
thesis.degree.levelUndergraduate
thesis.degree.nameAB
thesis.degree.nameAB
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.departmentComputer Science
dash.identifier.vireo
dash.author.emaillaoqimi@gmail.com


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record