Williams College Computer Science Professor Awarded NSF Grant

Print Story | Email Story

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,   

iBerkshires.com welcomes critical, respectful dialogue; please keep comments focused on the issues and not on personalities. Profanity, obscenity, racist language and harassment are not allowed. iBerkshires reserves the right to ban commenters or remove commenting on any article at any time. Concerns may be sent to info@iberkshires.com.

Williamstown Author's Book is a Massachusetts Book Awards 'Must Read'

The Massachusetts Center for the Book has announced the "Must Read" long lists in the 20th annual Massachusetts Book Awards.

The awards recognize significant works of fiction, nonfiction and poetry for adults and young readers written by Massachusetts authors and published during the preceding calendar year.  

This year's long list for Middle Grade/Young Adult books includes "The Next Great Paulie Fink" (Little, Brown), by Williamstown resident Ali Benjamin. The book is a funny and touching story about being thrust into the spotlight as a new kid and outsider in a small rural middle school.

"What a lucky group our state's tween and teenage readers prove to be. Our Middle Grade and Young Adult Must Read picks include an incredible swath of history, along with stories about artistic inspiration, fantasy, and the growing pains of surviving realities both ordinary and everything but," said Michelle Hoover, coordinator of MassBooks 20 and author of "The Quickening" (2010 Must Read) and "Bottomland" (2016 Must Read).   

In August, the center will announce the award winner and two honors titles in each of the five award categories with the hope of celebrating all titles in the program at a 20th  anniversary reception in the fall. 

"In the midst of a public health crisis, we take heart that we can announce another exciting year for Massachusetts writing," said Sharon Shaloo, executive director of MCB. "These awards confirm the strength and vitality of our extensive community of authors and  illustrators working in our academic and literary economies. We look forward to  promoting the long lists in every way we can throughout the spring and summer."

The Massachusetts Center for the Book is a public-private partnership, chartered as the commonwealth affiliate of the Center for the Book in the Library of Congress, and charged with developing, supporting and promoting cultural programming to advance the cause of  books and reading.

View Full Story

More Williamstown Stories