October 2012 - talks - lists.cs.princeton.edu

Colloquium speaker Michael Walfish Friday, Oct 26
by Nicole E. Wagenblast 26 Oct '12

26 Oct '12

Making proof-based verified computation almost practical Michael Walfish , The University of Texas at Austin Computer Science Small Auditorium, Room 105 Friday, October 26, 2012, 3:30pm How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? And how can this be done without assumptions about the performer (replication, trusted hardware, etc.) or restrictions on the computation? This is the problem of _verified computation_, and it is motivated by the cloud and other third-party computing models. It has long been known that (1) this problem can be solved in theory using probabilistically checkable proofs (PCPs) coupled with cryptographic tools, and (2) the performance of these solutions is wildly impractical (trillions of CPU-years or more to verify simple computations). I will describe a project at UT Austin that challenges the second piece of this folklore. We have developed an interactive protocol that begins with an efficient argument [IKO CCC '07] and incorporates new theoretical work to improve performance by 20+ orders of magnitude. In addition, we have broadened the computational model from Boolean circuits to a general-purpose model. We have fully implemented the system, accelerated it with GPUs, and developed a compiler that transforms computations expressed in a high-level language to executables that implement the protocol entities. The resulting system, while not quite ready for the big leagues, is close enough to practicality to suggest that in the near future, PCPs could be a real tool for building actual systems. Talk will be based on these papers and ongoing work: * http://www.cs.utexas.edu/~mwalfish/papers/ginger-usec12.pdf * http://www.cs.utexas.edu/~mwalfish/papers/pepper-ndss12.pd Michael Walfish is an assistant professor in the Computer Science Department at The University of Texas at Austin. His research interests are in systems, security, and networking. His honors include an Air Force Young Investigator Award, an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence Award from the UT College of Natural Sciences, the Intel Early Career Faculty Honor Program, and the UT Society for Teaching Excellence. He received his B.A. from Harvard and his Ph.D. from MIT, both in Computer Science.

1 2

Talk- Theodore Johnson of ATT Labs Wed. Oct 24
by Nicole E. Wagenblast 19 Oct '12

19 Oct '12

Hi all, Theodore Johnson will be visiting the department from ATT Labs on Wednesday, October 24. He'll be giving a talk about Data Stream Warehousing. The talk will be 12 noon to 1:30 pm, in Room 302. Abstract: Data stream processing is a well-studied area that has led to many commercial offerings. Stream processing systems typically store only a small history of a stream, and provide services such as real-time alerting and visualization, and data reduction for downstream processing. However many applications also require that long term (e.g. 2 year) histories as well as real-time data be provided to analysts. A stream warehouse combines aspects of data stream processing (continual data ingest) with data warehousing (long-term storage and materialized views). I will discuss special issues and opportunities that arise in stream warehousing, and stream warehouse applications within AT&T Labs - Research. Bio: Theodore Johnson received a PhD in Computer Science from New York University in 1990. From 1990 through 1996, he was an Associate Professor at the CISE department of the University of Florida. In 1996, Ted moved to the Database Research group of AT&T Labs - Research and has been there since. Ted has specialized in data steam management systems, being one of the principal authors of the GS Tool (previously, Gigascope) and of the DataDepot stream warehouse. Ted has written two books, Distributed Operating Systems and Algorithms (with Randy Chow) and Exploratory Data Mining and Data Cleaning (with Tamraparni Dasu). -- Ari Rabkin asrabkin(a)gmail.com Princeton Computer Science Department

1 0

CS Colloquia on making PCP practical: Friday 10/26 @ 3:30pm
by Mike Freedman 19 Oct '12

19 Oct '12

[Mike is a systems researcher who, along with students, has been working on this problem with Andrew Blumberg. Andrew is a mathematician who spent 2007-2008 at IAS. So, this talk might be interesting to some folks on varying backgrounds.] --- Making proof-based verified computation almost practical Michael Walfish, The University of Texas at Austin Friday, October 26, 2012, 3:30 PM - 4:30 PM CS Small Auditorium (Room 105) --- How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? And how can this be done without assumptions about the performer (replication, trusted hardware, etc.) or restrictions on the computation? This is the problem of _verified computation_, and it is motivated by the cloud and other third-party computing models. It has long been known that (1) this problem can be solved in theory using probabilistically checkable proofs (PCPs) coupled with cryptographic tools, and (2) the performance of these solutions is wildly impractical (trillions of CPU-years or more to verify simple computations). I will describe a project at UT Austin that challenges the second piece of this folklore. We have developed an interactive protocol that begins with an efficient argument [IKO CCC '07] and incorporates new theoretical work to improve performance by 20+ orders of magnitude. In addition, we have broadened the computational model from Boolean circuits to a general-purpose model. We have fully implemented the system, accelerated it with GPUs, and developed a compiler that transforms computations expressed in a high-level language to executables that implement the protocol entities. The resulting system, while not quite ready for the big leagues, is close enough to practicality to suggest that in the near future, PCPs could be a real tool for building actual systems. Talk will be based on these papers and ongoing work: http://www.cs.utexas.edu/~mwalfish/papers/ginger-usec12.pdf http://www.cs.utexas.edu/~mwalfish/papers/pepper-ndss12.pd --- Michael Walfish is an assistant professor in the Computer Science Department at The University of Texas at Austin. His research interests are in systems, security, and networking. His honors include an Air Force Young Investigator Award, an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence Award from the UT College of Natural Sciences, the Intel Early Career Faculty Honor Program, and the UT Society for Teaching Excellence. He received his B.A. from Harvard and his Ph.D. from MIT, both in Computer Science.

1 0

M Wawrzoniak preFPO
by Melissa M. Lawson 17 Oct '12

17 Oct '12

Michael Wawrzoniak will present his preFPO on Wednesday October 24 at 10AM in Room 402. The members of his committee are: Larry Peterson, advisor; David Blei, Andrea LaPaugh, Vivek Pai, and Rob Schapire. Everyone is invited to attend his talk. His abstract follows below. ---- The role played by data analysis and machine learning continues to gain significance in many fields, and society as a whole. In particular, statistical learning in the framework of graphical models has become a very successful and popular machine learning method used in many fields. However developing these models requires substantial expertise and applying them to very large distributed and streaming data sets can still be a very challenging problem. In this talk I will propose an architecture which will make a substantial subset of these techniques accessible to users with less expert machine learning knowledge. A framework for high-level description of models in conjugate-exponential family, automatically transforming them to distributed streaming stochastic variational inference procedure, and an evaluation platform will be outlined. The vision of this software stack is to show a possible future path for a shift from data analysis being in the hands the expert elites towards empowering the wider public. ----

1 0

S Sevinc preFPO
by Melissa M. Lawson 15 Oct '12

15 Oct '12

Soner Sevinc will present his preFPO on Monday October 22 at 8:30 AM in Room 402. The members of his committee are: Larry Peterson (advisor), Jennifer Rexford and Andy Bavier, readers; Michael Freedman and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------- "Federation Framework Discovering and authorizing resources dispersed across autonomous organizations is a challenge for federations as they scale in number of participant organizations. We first give an analysis of some of today's federations in terms of trust models and argue that complex trust models, that entail indirect trust relations, can be one way to scale federations in the future. We introduce our federation framework, which can be used to realize access control and resource discovery in federations with arbitrary complex trust models. This framework synthesizes three area of previous work; trust management systems, policy languages and resource discovery systems. CERTDIST trust management system performs access control using digital certificates for proof construction. Different from its counterparts such as ABAC or SD3, it can construct proofs for more complex trust relations, by utilizing a DHT to perform key based certificate lookup. In addition, CERTDIST's programmable credentials allow dynamic policies be expressed as digital certificates. Federation Policy Language, FPL, is used to express security and resource allocation policies in federation. FPL primitives interface to underlying CERTDIST functionality, which are used by security architects and resource providers to write policies easily. Our contract based discovery and allocation system, CODAL, performs policy-driven peer discovery and collaborative resource discovery/allocation to address two problems: (1) participants in a federation can be unknown, and (2) their resource information and policies can be private. We evaluate our design in PlanetLab, emulating a realistic federation based on PlanetLab usage logs. Results show that our system is capable of discovering and allocating resources in a large scale federation, fulfilling a request from tens of organizations. We also show allocation policies are successfully enforced by our language, and explore run-time characteristics of the FPL proof construction process, and investigate certificate retrieval in terms of time and incurred system load."

1 0

Colloquium Speaker Phil Levis- Fri Oct 12, 3:30pm
by Nicole E. Wagenblast 11 Oct '12

11 Oct '12

Full Duplex Wireless Phil Levis , Stanford University Friday, October 12- 3:30pm Computer Science 105 Wireless networking traditionally assumes that radios are half-duplex. On a given frequency, a half-duplex radio can either transmit or receive, but not both at the same time. I present recent results demonstrating that a full-duplex radio -- a radio that can receive and transmit simultaneously on the same frequency -- can be built using commodity, off-the-shelf components. I discuss some of the possible implications of full duplex, including solving some long-standing problems in wireless, such as the hidden terminal problem, signal boosters, and access point fairness. I examine the design space for full duplex radios, describing the corresponding tradeoffs. Full duplex has the potential to revolutionize a large number of wireless systems: I'll conclude with current strengths and limitations of the technology to try to shed some light on where I think it might be most and least successful. The talk is intended for a CS audience; it does not assume any RF theory background, just a high school level understanding of the physics and mathematics of sine waves. Philip Levis is an Associate Professor of Computer Science and Electrical Engineering at Stanford University. He received his Sc.B. from Brown University in 1999, his M.S. from the University of Colorado at Boulder in 2001, and his Ph.D. from UC Berkeley in 2005. In 2008 he received an NSF CAREER award and a Microsoft Research New Faculty Fellowship. He researches the design and implementation of networked systems that interact with the world, including operating systems and protocols for embedded wireless devices, wireless mesh protocols, network infrastructure for virtual worlds, and energy efficient computing. The results of his research, including the TinyOS operating system, nesC language, Trickle algorithm, and the collection tree protocol (CTP), have been adopted by tens of thousands of users and researchers worldwide. He's authored a few Internet standards based on his work. He really likes excellent engineering and has a self-destructive aversion to low-hanging fruit.

1 1

Colloquium Speaker Scott Klemmer- Thurs Oct 11, 4:30pm
by Nicole E. Wagenblast 11 Oct '12

11 Oct '12

The Power of Examples Scott Klemmer , Stanford University Thursday Oct 11, 4:30pm Computer Science 105 Designers in many fields rely on examples for inspiration, and examples play an important role in art and design curricula. In this talk, I'll describe several ways that examples help the creative process by illustrating concepts and alternatives. Online media offer a corpus of examples at a scale and diversity never before seen. This wealth of examples opens up new possibilities, but also poses several challenges. How can we leverage these resources? My group's research tools harvest and synthesize examples to empower more people to design interactive systems, learners to acquire new skills, experts to be more creative, and programmers to engage in more design thinking. This research shapes my project-based design teaching, which emphasizes creating diverse alternatives, self-assessment, and using examples to provide design insights and teach abstract principles. This spring, we collaborated with Coursera to launch the first massive-scale class with self and peer assessment. This enabled online students to engage in open-ended design projects, and it worked surprisingly well. Scott is an Associate Professor of Computer Science at Stanford University. He co-directs the Human-Computer Interaction Group and holds the Bredt Faculty Scholar development chair. Organizations around the world use his lab's open-source design tools and curricula; several books and popular press articles have covered his research and teaching. He has been awarded the Katayanagi Emerging Leadership Prize, Sloan Fellowship, NSF CAREER award, Microsoft Research New Faculty Fellowship. He has authored and co-authored more than 40 peer-reviewed articles; six have been awarded best paper or honorable mention at the premier HCI conferences (CHI and UIST). His former graduate students are leading professors, researchers, founders, social entrepeneurs, and engineers. He has a dual BA in Art-Semiotics and Computer Science from Brown University, Graphic Design work at RISD, and an MS and PhD in Computer Science from UC Berkeley. He serves on the editorial board of TOCHI and HCI, was the program co-chair of UIST 2011, and co-chaired the systems area of CHI 2010. He helped introduce peer assessment to open online education, and taught the first peer-assessed online course.

1 1

R Manokaran FPO
by Melissa M. Lawson 10 Oct '12

10 Oct '12

Rajsekar Manokaran will present his FPO on Wednesday October 17 at 10 AM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark Braverman and Rob Schapire, nonreaders. A copy of his thesis, "Approximability and Mathematical Relaxations", is on display in Room 410. Everyone is invited to attend his talk.

1 0

V Kim preFPO
by Melissa M. Lawson 10 Oct '12

10 Oct '12

Vladimir (Vova) Kim will present his preFPO on Wednesday October 17 at 4PM in room 402. The members of his committee are: Tom Funkhouser, advisor; Szymon Rusinkiewicz and Wilmot Li (Adobe), readers; Adam Finkelstein and David Dobkin, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------- TITLE: Establishing Correspondences in Collections of Diverse 3D Shapes ABSTRACT: Large repositories of 3D models have become available in recent years. These repositories include scans of everyday objects and outdoor environments, CAD models created by engineers, and computer graphics models created by artists and casual users. Establishing corresponding points allows reasoning about functional and semantic similarities between models in a collection, and opens space for many applications like transferring properties, classifying and segmenting new data and exploring 3D collections. Scale of these collections necessitates development of automatic algorithms for computing such correspondences. Much of the previous work concentrates on matching pairs of shapes with limited geometric diversity. Our work addresses several challenges related to finding and representing correspondences in large collections where models exhibit substantial geometric variations including non-uniform deformations, or have different multiplicities, complexities and styles of parts. We develop algorithms that (i) handle such variations robustly, (ii) represent semantic ambiguity due to diversity of the data, and (iii) efficiently process large collections. First, to address the challenge of matching models with non-uniform deformations, we propose a fully automatic pipeline for finding an intrinsic map between two non-isometric, genus zero surfaces. Our approach is based on the observation that efficient methods exist to search for nearly isometric maps, but no single solution found with these methods provides low-distortion everywhere for pairs of surfaces differing by large deformations. To address this problem, we suggest using a weighted combination of these maps to produce a “blended map.” This approach enables algorithms that leverage efficient search procedures, yet can provide the flexibility to handle large deformations. During experiments with these methods, we find that our algorithm produces blended maps that align semantic features better than alternative approaches over a variety of data sets. Second, we propose an automatic analysis method for computing similarity relationships between points on 3D shapes across a relatively homogeneous and small collection (order of hundreds of models). Our method is robust to general geometric variations, including non-uniform deformations, and partial similarity (e.g. due to different part multiplicities or styles). We encode the inherent ambiguity in similarity relationships using fuzzy point correspondences and propose a robust and efficient computational framework that estimates fuzzy correspondences using only a sparse set of pairwise model alignments. We evaluate our analysis method on a range of correspondence benchmarks and report substantial improvements in both speed and accuracy over existing alternatives. Finally, we address the challenge of establishing correspondences in large and diverse collections (order of tens of thousands of models) efficiently and robustly. We concentrate on models that can be represented as part-wise assemblies, and our goal is to compute consistent segmentation of models along with aligning transformations between all parts, (i.e. providing a representation that can directly define point-to-point or fuzzy correspondences). We propose a method that relies on fitting a deformable template that explicitly models class-specific geometric variations. The key contribution of our approach is in iterative learning of these variations from large collections with unreliable and noisy labels, (as they appear in public repositories, such as Google Warehouse). Resulting deformable template and consistent segmentations can be used in several applications including exploring collections of shapes, synthesizing new shapes by part-wise assembly and interpreting (classifying, segmenting and reconstructing) noisy 3D scans.

1 0

J Nelson general exam
by Melissa M. Lawson 09 Oct '12

09 Oct '12

Jude Nelson will re-present the oral exam portion of his research seminar/general exam on Tuesday October 16 at 9AM in Room 402. The members of his committee are: Larry Peterson (advisor), Michael Freedman, and Vivek Pai. Any additional faculty members wishing to attend are welcome to do so. His abstract and reading list follow below. ------------------ Abstract: It is well understood that network caches offer three potential advantages to cloud storage providers: they reduce read latency, they scale read bandwidth, and they reduce the amount of data that must be transferred directly from the datacenter (which incur some cost). Network caches "extend" cloud storage into the readers' edge networks--read requests are serviced by nearby network caches instead of upstream cloud storage. However, the same cannot be said for writers--a writer must upload data synchronously to upstream storage. Additionally, network caches may serve readers stale or even corrupt data in the presence of writes. To remedy this, we propose Syndicate--a distributed wide-area storage service that extends cloud storage to the edge of the network for both readers and writers. Syndicate provides readers the performance benefits and download transfer savings enabled by underlying CDNs and caching proxies, while at the same time guaranteeing that readers see the effects of all completed writes. It also provides writers the performance benefits of network-local storage by reducing the amount of data that must be synchronously uploaded to cloud storage on each write. Finally, by organizing data into a hierarchical namespace, and by allowing concurrent reads and writes on records while enforcing a sequential history of record creation and deletion, Syndicate provides applications with filesystem-like storage semantics similar to many existing cloud storage services. Syndicate makes two contributions over existing wide-area storage systems. First, it simultaneously leverages CDNs and other edge caches while also supporting a well-defined consistency model in the face of writes. Second, it uses a ``built from parts'' design strategy, whereby Syndicate is effectively layered on top of a disparate set of commodity components. Syndicate manages naming and consistency, existing cloud storage services enhance data persistence, and unmodified CDNs offer the performance and cost advantages outlined above. Reading list: Peterson, Larry L., and Davie, Bruce S. "Computer Networks, a Systems Approach. 4th Ed." Cerf, V., and Kahn, R. "A Protocol for Packet Network Intercommunication." Lamport, L. "Time, clocks, and the ordering of events in a distributed system." Schneider, F. "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial" Park, K. and Pai, V. "Scale and Performance in the CoBlitz Large-File Distribution Service." L. Wang, V. Pai, and Peterson, L. "The Effectiveness of Request Redirection on CDN Robustness." Annapureddy, S., Freedman, M., and Mazieres, D. "Shark : Scaling File Servers via Cooperative Caching." Burrows, M. "The Chubby lock service for loosely-coupled distributed systems." Peterson, L., Bavier, A., Fiuczynski, M., Muir, S. "Experineces Building PlanetLab." Belaramani, N., Dahlin, M., Gao, L., et. al. "PRACTI Replication." Stribling, J., Sovran, Y., Zhang, I., et. al. "Flexible , Wide-Area Storage for Distributed Systems with WheelFS." Freedman, M., Freudenthal, E., Mazieres, D. "Democratizing content publication with Coral." Vahdat, A., Eastham, P., Yoshikawa, C., et. al. "WebOS: Operating System Services for Wide Area Applications."

1 0