- talks - lists.cs.princeton.edu

Colloquium speaker Swarat Chaudhuri Thurs Sept 29
by Nicole E. Wagenblast 28 Sep '11

28 Sep '11

Composing Composure: Reasoning about Robustness of Software Systems Swarat Chaudhuri, Rice University Thursday, September 29- 4:30pm Computer Science 105 Most software is inherently nonrobust--change the operating conditions of a typical program slightly, and you may obtain very different results. This lack of robustness can not only result in unpredictable runtime behavior, it also makes testing, approximation, and mathematical analysis of programs highly challenging. We will argue that methods for automated logical reasoning about programs provide a way to cope with this problem. Using a program analysis, we can sometimes determine if a given program is robust, and if so, exploit this property. On the other hand, if a program is not robust, logic can help us approximate it into one that is robust. Using applications from several different areas of computer science, I will show how these techniques can lead to more reliable program execution under uncertainty, opportunities for language-based approximate computation, and easier solutions to hard optimization problems involving programs. Swarat Chaudhuri is an Assistant Professor of Computer Science at Rice University. His research lies in the interface of automated reasoning and programming languages.

1 1

Distinguished Colloquium speaker, Cynthia Dwork, Wed Sept 21- 4:30pm
by Nicole E. Wagenblast 15 Sep '11

15 Sep '11

Distinguished Colloquium Series Speaker Fairness Through Awareness Cynthia Dwork, Microsoft Research, SVC Wednesday, September 21, 2011, 4:30 PM Computer Science 105 "Why was I not shown this advertisement? Why was my loan application denied? Why was I denied admission to this university?" In this work we initiate the formal study of fairness in classification, where the goal is to prevent discrimination against protected population subgroups in classification systems while simultaneously preserving utility for the party carrying out the classification (eg, the advertiser, bank, or admissions committee). We argue that a classification is fair only when individuals who are similar with respect to the classification task at hand are treated similarly, and this in turn requires understanding of sub cultures of the population. Similarity metrics are applied in many contexts, but these are often hidden. Our work explicitly exposes the metric, opening it to public debate. We then formalize and show how to achieve fairness in classification, given a similarity metric. We also give conditions on the metric under which our "local" notion ensures statistical parity: namely that the demographics of those receiving any given classification are the same as the demographics of the underlying population. In a complementary setting, we propose tools for what can be viewed as "fair affirmative action." Namely, we give methods for guaranteeing statistical parity for a group while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: to what extent might fairness imply privacy, and is it possible to employ tools developed in the context of differential privacy in order to obtain fairness. Joint work with Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Cynthia Dwork '79, Distinguished Scientist at Microsoft Research, is the world's foremost expert on placing privacy-preserving data analysis on a mathematically rigorous foundation. A cornerstone of this work is differential privacy, a strong privacy guarantee permitting highly accurate data analysis. Dr. Dwork has also made seminal contributions in cryptography and distributed computing, and is a recipient of the Edsger W. Dijkstra Prize, recognizing some of her earliest work establishing the pillars on which every fault-tolerant system has been built for decades. She is a member of the US National Academy of Engineering and a Fellow of the American Academy of Arts and Sciences.

1 0

Wei Dong FPO
by Melissa M. Lawson 08 Sep '11

08 Sep '11

Wei Dong will present his FPO on Wednesday September 14 at 9:30AM in Room 402. The members of his committee are: Kai Li, advisor; Moses Charikar and Andrea LaPaugh, readers; Brian Kernighan and Olga Troyanskaya, nonreaders. A copy of his thesis, "High-Dimensional Similarity Search for Large Datasets", is on display in Room 310. Everyone is invited to attend his talk.

1 0

A Feldman preFPO
by Melissa M. Lawson 30 Aug '11

30 Aug '11

Ari Feldman will present his preFPO on Friday September 2 at 2PM in Room 302 (note room). The members of his committee are: Ed Felten, advisor; Mike Freedman and Andrew Appel, readers; David Walker and Brian Kernighan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------------------------------- Title: Using Untrusted Resources Securely Abstract: In a myriad of applications, users depend on devices or services provided by third parties to perform functions that they cannot carry out themselves or that third parties can do better. For example, in public elections, voters cast their votes on voting machines or paper ballots provided by election officials because they do not have the means to prepare properly formatted ballots on their own. In addition, in applications from word processing to social networking, users are increasingly adopting services in which their data resides not on their own devices, but on servers run by third parties. Users are drawn to these services because they provide levels of availability, scalability, and accessibility that average users cannot match using only their own equipment. Unfortunately, depending on third parties has typically forced users to give up control over their data. They must rely on the third parties to preserve their data’s confidentiality and integrity, and a third party that is malicious or has been subject to attack or legal pressure can compromise them. Furthermore, users typically have little more than the third parties’ promises to assure them that their data is safe. In this dissertation, we aim to improve this situation. We present protocols and systems that allow users to utilize third-party resources while providing them with a means to verify that the third parties are performing their functions correctly so that they need not trust mere promises. Our work covers three areas: cryptographic voting, cloud-based group collaboration, and social networking. Our prior work shows that widely-deployed non-cryptographic voting systems can be infected with malicious software that changes votes, potentially without detection. Vulnerabilities of this kind inspired the development of cryptographic voting systems in which the encryption of every cast ballot is made public and the encrypted ballots can be tallied in a publicly-verifiable way. Although cryptographic voting has the potential to make elections more trustworthy, it still forces voters to depend on voting machines to encrypt their ballots. Indeed, we show that a malicious voting machine can compromise the secrecy of the ballot by manipulating the ciphertext of only a handful of the ballots that are made public. We then present a protocol that significantly reduces this threat by forcing voting machines to encrypt ballots using random values chosen in advance of the election and that provides a way for anyone to verify that the right random values were used for every ballot. For applications such as word processing and calendaring, users are increasingly adopting cloud deployment because it provides benefits such as scalability, high availability, global accessibility, and real-time group collaboration. Unfortunately, moving to the cloud currently comes at the cost of trusting the cloud provider with users’ data. To overcome this tradeoff, we present SPORC, a generic framework for building a wide variety of collaborative applications with untrusted servers. In SPORC, servers only observe encrypted data and cannot deviate from correct execution without being detected. SPORC allows concurrent, low-latency editing of shared state, permits disconnected operation, and supports dynamic access control even in the presence of concurrency. Current social networking applications also require users’ to trust service providers with the plaintext of their social interactions. In response, numerous works have proposed distributing users’ data across multiple servers controlled by different parties. But, unless users bear the burden of running their own servers, they are still forced to trust third parties. Instead, we present a social networking system that allows users’ data to be hosted entirely on untrusted servers while still protecting the data’s confidentiality and integrity. Our design includes novel data structures that support efficient membership operations even for large groups and provide strong protection against server equivocation for the append-only logs that social networking applications use extensively.

1 0

S Jafarpour FPO
by Melissa M. Lawson 25 Aug '11

25 Aug '11

Sina Jafarpour will present his FPO on Friday September 2 at 2PM in Room 402. The members of his committee are: Rob Calderbank (ELE/MAT), advisor; Rob Schapire and Ingrid Daubechies (MAT), readers; Bernard Chazelle and Amit Singer (MAT), nonreaders. A copy of his thesis, "Deterministic Compressed Sensing", is on display in Room 310. Everyone is invited to attend his talk.

1 0

I Mukherjee FPO
by Melissa M. Lawson 23 Aug '11

23 Aug '11

Indraneel Mukherjee will present his FPO on Monday August 29 at 2PM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Yoav Freund (UCSD), readers; Moses Charikar and Philippe Rigollet (ORF), nonreaders. A copy of his thesis, "Game Theory and Optimization in Boosting", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Y Zhu FPO
by Melissa Lawson 18 Aug '11

18 Aug '11

Yaping Zhu will present her FPO on Thursday August 25 at 1PM in Room 402. The members of her committee are: Jennifer Rexford, advisor; Vivek Pai and Aman Shaikh (AT&T), readers; Michael Freedman and Andrea LaPaugh, nonreaders. A copy of her thesis, "Minimizing Wide-Area Performance Disruptions in Inter-Domain Routing", is on display in Room 310. Everyone is invited to attend her talk.

1 0

S Ihm FPO
by Melissa Lawson 18 Aug '11

18 Aug '11

Sunghwan Ihm will present his FPO on Wednesday August 24 at 2PM in Room 402. The members of his committee are: Vivek Pai, advisor; Jennifer Rexford and Larry Peterson, readers; Michael Freedman and Andrea LaPaugh, nonreaders. A copy of his thesis, "Understanding and Improving Modern Web-Traffic Caching", is on display in Room 310. Everyone is invited to attend his talk.

1 0

J Jiang preFPO
by Melissa M. Lawson 02 Aug '11

02 Aug '11

Joe Wenjie Jiang will present his preFPO on Friday August 5 at 10:30AM in Room 318B (networking lab). Note location. His committee is: Jennifer Rexford, advisor; Andrea LaPaugh and Augustin Chaintreau (Columbia), readers; Mike Freedman and Mung Chiang (ELE), nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- Title: Wide-Area Traffic Management for Cloud Services Abstract: Cloud services need an effective way to distribute contents across wide area networks. Providing large-scale, geographically-replicated online services presents new opportunities for coordination between server selection (to match subscribers with servers), traffic engineering (to select efficient paths for the traffic) and adaptive content caching (to place contents sources close to users). Traditional designs isolate these problems, which degrades performance, scalability, reliability and responsiveness. We leverage the theory of distributed optimization, collaborative game theory and randomized algorithms to provide solutions that jointly optimizes over different degrees of design freedom. This dissertation proposes a sets of solutions to wide-area and data center traffic management, which consists of the following three thrusts: (i) Cooperative content distribution and traffic engineering in an ISP network. We develop cooperation models with an increasing amount of information exchange between ISPs and content providers. We show that the lack of communication leads to sub-optimal performance, and even when extra information is used inappropriately. We propose a joint design solution to reduce such efficiency loss. (ii) Traffic management in Nano data centers, which represents the trend of decentralizing content delivery by placing contents close to the last mile of end user connectivity and utilizing their upload capability. We solve a joint content caching and request routing problem for minimizing cross-traffic and propose a distributed implementation. (iii) Cost-efficient data center traffic engineering with joint server placement and route selection, by exploiting multipath capability and virtual machine migrations. Our systems can be easily implemented with incremental modifications to today's architecture such as content-selection mechanisms, and infrastructure such as switches and end hosts. The effectiveness of our schemes is demonstrated by our evaluation with real-life traffic traces.

1 0

M Yu FPO
by Nicole E. Wagenblast 29 Jul '11

29 Jul '11

Minlan Yu will present her FPO on Friday August 5 at 3PM in Room 402. The members of her committee are: Jennifer Rexford, advisor; Michael Freedman and Albert Greenberg (MSR), readers; Vivek Pai and Ed Felten, nonreaders. A copy of her thesis, "Scalable Management of Enterprise and Data Center Networks", is on display in Room 310. Everyone is invited to attend her talk.

1 0