Williams College Computer Science Professor Awarded NSF Grant
 |
WILLIAMSTOWN, Mass. — Shikha Singh, assistant professor in computer science at Williams College, has been awarded a two-year, $155,000 grant from the National Science Foundation to fund her research on verifying that computation outsourced to third-party service providers has been performed correctly.
Her work in this area aims to increase understanding of the role of incentives in algorithms, which has wide applications to areas such as crowdsourcing, cloud computing, and social computing.
With the growing popularity of cloud computing, most computation today is not done locally but rather outsourced to third-party service providers, or SPs. Outsourcing computation poses the research problem of how the client outsourcing the computation can verify that it has been performed correctly, without having to redo it.
"Most previous work has studied this problem from a security standpoint, assuming that the SPs are malicious or adversarial," Singh said. "This assumption does not capture the nature of SPs on internet marketplaces, who are often profit-driven, performing computation for money."
Singh's project, titled "CRII: AF: RUI: Verifiable Computation Outsourcing: A Non-Cooperative Approach," approaches the problem of verifying outsourced computation from an economic perspective. In particular, her work focuses on SPs that want to maximize their payment, with the goal of designing payment schemes that directly incentivize correctness.
"The advantage of this approach is that it leads to verification protocols that are simple, practical, and require extremely small verification overhead on the part of the client," Singh said.
Interactive proofs (IP) are a common framework used to study verifiable computation outsourcing. In an IP, the weak client (or verifier) interacts with powerful service providers (or provers) to determine the truthfulness of their claim. Existing IP protocols largely fall into two categories: the cooperative-prover model, such as classical IPs, or the competing-prover model, such as refereed games. In computation-outsourcing applications, the nature of SPs is arguably in the middle of these two extremes, neither cooperative or competitive, but rational—acting to maximize their own payment. The model of non-cooperative rational interactive proofs was introduced recently to capture this middle ground.
Singh's project aims to take advantage of this new model to design extremely efficient interactive proofs tailored for computation outsourcing. As part of this work, new insights and techniques from game theory and mechanism design will be used to design protocols that achieve extremely small verification overhead compared to existing rational-proof and refereed-games protocols, guarantee robustness against deviating provers, and do not rely on private channels of communication between the verifier and provers.
"My hope is that this project informs the design of future computational-outsourcing platforms and more broadly sheds light on the role of incentives in computation," Singh said.
Tags: Williams College,
