General Information • Project Description • Project Log • Links
General Information
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 
Project Description
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)
Final Presentation (ppt)
Project Log
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 1round 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 multiround 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 89: Prague!
Links and Resources
Rutgers DIMACS
