dimacs logo

General InformationProject DescriptionProject LogLinks

General Information

Roy Luo
royluo at berkeley dot edu
CoRE 442
UC Berkeley
Faculty Advisor:
Graham Cormode, AT&T Labs
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 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!

Links and Resources

Rutgers DIMACS