General Information • Project Description • Project Log • Links
Student: |
Roy Luo |
Email: |
royluo at berkeley dot edu |
Office: |
CoRE 442 |
School: |
UC Berkeley |
Faculty Advisor: |
Graham Cormode, AT&T Labs |
Project: |
Outsourced Computation Verification |
Frequently when processing large amounts of information with limited memory (such as a situation with streaming data), it is necessary or more practical to outsource computation of this data to a third party with more powerful means of computation. A problem arises when the third party is not trusted to be completely accurate; then we require some sort of proof that the third party's computation was computed correctly. My research is in practical methods of verifying outsourced computation of certain canonical problems using limited space.
Introductory Presentation (ppt)
Week 1: Familiarized myself with the topic via some background articles, and discussed the project with my advisor.
Week 2: Set up website, gave introductory presentation, began implementing protocols to test.
Week 3: Worked on implementing the 1-round frequency moment protocol. Got a functioning but very slow version - learned about different methods of implementing finite fields in Mathematica. Began analyzing and improved the runtime of the algorithms used.
Week 4: Moved on to the multi-round frequency moment protocol. Read the literature, worked through some examples, and began implementation.
Week 5: Continued work on the protocol. Finally got a working version, which I analyzed for space, communication, and time usage. The time complexity needed some improvement so I began work on that.
Week 6: Spent most of the time trying to improve the runtime of the protocol - working through examples, analyzing algorithms, etc. Got it to work in about O(n*Log(n)) time as opposed to O(n^2) by the end of the week which allowed me to test the protocol on much larger values.
Week 7: Cleaned up the code for better usability and prepared final presentation.
Week 8-9: Prague!