November 2013 - talks - lists.cs.princeton.edu

Colloquium Speaker David Malan Tues Dec 3, 4:30pm
by Nicole E. Wagenblast 02 Dec '13

02 Dec '13

Pedagogy behind CS50 David Malan , Harvard University Tuesday, December 3, 4:30pm Computer Science 105 CS50 is Harvard University's introductory course for majors and non-majors alike, a one-semester amalgam of courses generally known as CS1 and CS2. In 2007, we set out to alter the course's style and tone to resonate with those "less comfortable" and "more comfortable" alike, albeit without sacrificing the course's historical rigor. We maintained the course's underlying syllabus but revamped every problem set, providing students not only with more direction but context as well. And we augmented the course's support structure. As of 2013, CS50 is Harvard's second-largest course with nearly 700 students, up from 132 in 2006, and those "less comfortable" now compose the course's largest demographic. We present in this talk what we have done and why we have done it. And we offer a glimpse of CS50x, Harvard College's first course to be offered on an even larger scale via edX. BIO David J. Malan is a Senior Lecturer on Computer Science at Harvard University for the School of Engineering and Applied Sciences. He received his A.B., S.M., and Ph.D. in Computer Science from the same in 1999, 2004, and 2007, respectively. His research in graduate school focused primarily on cybersecurity and computer forensics. His more recent publications focus on instructional technologies and pedagogy. He now teaches Harvard College's introductory computer science course, Computer Science 50, otherwise known as CS50, which is available as OpenCourseWare at cs50.tv as well as via edx.org.

1 1

J Lu preFPO
by Melissa M. Lawson 27 Nov '13

27 Nov '13

Jingwan (Cynthia) Lu will present her preFPO on Monday December 9 at 4:30 PM in Room 402. The members of her committee are: Adam Finkelstein, advisor; Szymon Rusinkiewicz and Stephen DiVerdi (Google), readers; Tom Funkhouser and Jianxiong Xiao, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ----- Original Message ----- Title: Data-driven Digital Drawing and Painting Abstract: Digital artists create evocative drawings and paintings using a tablet and stylus coupled with painting software like Adobe Photoshop or Corel Painter. Several research systems have shown promising improvements in various aspects of the art creation process by targeting specific drawing styles and natural media. Such systems combine carefully hand-crafted procedural rules and computationally expensive, style-specific physical simulations. Nevertheless, untrained users often find it hard to achieve their target style in these systems due to the challenge of controlling and predicting the outcome of their collective strokes. Moreover even trained digital artists are often restricted by the inherent stylistic limitations of these systems. In this thesis, I propose an alternative painting paradigm that allows novices to create artworks closely following an example style of their choice. The style is characterized by a set of example brush strokes. We present three prototype painting systems, all of which follow a common sketching interface, wherein the user's 1D paths are automatically replaced by complex 2D strokes shaped and textured by a small set of exemplars. The three prototype systems HelpingHand, RealBrush and DecoBrush make use of different types of exemplars for distinct styles of artwork. HelpingHand learns from hand gesture data to hallucinate the possible gestures used during drawing, which then drive a chosen virtual brush simulation engine to produce stylistic handwritings or line drawings. RealBrush uses photographed natural media stroke marks to stylize the user's query path, completely obviating the need for physical simulation. It also stylizes the stroke interactions based on captured physical examples. DecoBrush further generalizes the conventional "painting" concept beyond the scope of natural media to allow "painting" structured decorative vector patterns following user-sketched path, which alleviates the difficulty of creating such patterns from scratch in programs like Adobe Illustrator. All three systems address the common challenge of predicting the appearance of user's new query paths being faithful to the style of a small number of chosen exemplars. With the convenience of data sharing on the internet, this data-driven paradigm opens up new opportunities for artists and novices to create original stylistic artworks and to abstract, share, and reproduce their styles more easily and faithfully.

1 0

S Li FPO
by Melissa M. Lawson 27 Nov '13

27 Nov '13

Shi Li will present his FPO on Monday December 9 at 3PM in Room 402. The members of his committee are: Moses Charikar, advisor; Mark Braverman and Julia Chuzhoy (TTI), readers; Bernard Chazelle and Zeev Dvir, nonreaders. A copy of his thesis, "Approximation Algorithms on Network Routing and Facility Location Problems" can be viewed by contacting his advisor. Everyone is invited to attend his talk.

1 0

H Nguyen preFPO
by Melissa M. Lawson 27 Nov '13

27 Nov '13

Huy Nguyen will present his preFPO on Friday December 6 at 4:30 PM in Room 402. The members of his committee are: Moses Charikar, advisor; Bernard Chazelle and Piotr Indyk (MIT), readers; Sanjeev Arora and Mark Braverman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Algorithms for Data in High Dimensions In the last decade, the availability of large data sets in high dimensions has been both an opportunity and a challenge for algorithm design. Many new algorithms are invented and yet many challenges remain unconquered. This thesis examines several methods for handling such data efficiently in terms of time and space, their limitations, and new techniques to get beyond those limitations. First, we look at embeddings, a powerful technique to reduce data in high dimensions to low dimensions. Tight or near tight bounds are shown for sparse subspace embeddings, sparse Johnson-Lindenstrauss transforms, and sparse RIP matrices. We also touch upon applications of subspace embeddings in numerical linear algebra and approximating large eigenvalues in both the classical setting and the streaming setting. For instance, the algorithm implied by our bound for subspace embeddings runs in time linear in the sparsity of the input plus an additive term that is optimal unless one can bypass generic matrix multiplication. To conclude the embedding section, we show a near linear lower bound for dimension reduction in L1. This bound is close to optimal as one can reduce the dimensions to linear while approximately preserving all pairwise distances. Even though significant dimension reduction is not possible in L1, fortunately there is a technique called locality sensitive hashing (LSH) allowing for efficient approximate nearest neighbor search in L1. In the second section of the thesis, we give a new construction of LSH for L_p (1<p<2) that is close to the lower bound for LSH. The algorithm is a generalization of previous work for L2 via the uniform convexity property. Lastly, in the final section of the thesis, we overcome the aforementioned lower bound for LSH and design a new algorithm for approximate nearest neighbor search in L1 and L2 that is faster and uses less memory than any LSH. Unlike LSH, the algorithm exploits the structure of the whole point set, and can be viewed as a step toward understanding data-aware methods for nearest neighbor search, which are ubiquitous in practice.

1 0

Y Pritykin preFPO
by Melissa M. Lawson 27 Nov '13

27 Nov '13

Yuri Pritykin will present his preFPO on Friday December 6 at 1:30 PM in Room 402. The members of his committee are: Mona Singh, advisor; Olga Troyanskaya and Bernard Chazelle, readers; Tom Funkhouser and Stanislav Shvartsman (CBE/Genomics), nonreaders. Everyone is invited to attend his talk. His abstract follows below. Title: Intermodular and intramodular proteins in protein interaction networks The availability of large-scale protein-protein interaction networks for numerous organisms provides an opportunity to comprehensively analyze the roles proteins play in the functional organization of the cell. First, we re-examine an influential but controversial characterization of the dynamic modularity of the S. cerevisiae interactome that incorporated gene expression data into network analysis. We analyse the protein-protein interaction networks of five organisms, S. cerevisiae, H. sapiens, D. melanogaster, A. thaliana, and E. coli, and confirm significant and consistent functional and structural differences between hub proteins that are co-expressed with their interacting partners and those that are not, and support the view that the former tend to be intramodular whereas the latter tend to be intermodular. However, we also demonstrate that in each of these organisms, simple topological measures are significantly correlated with the average co-expression of a hub with its partners, and therefore also reflect protein intra- and inter- modularity. Further, cross-interactomic analysis demonstrates that these simple topological characteristics of hub proteins tend to be conserved across organisms. Overall, we give evidence that purely topological features of static interaction networks reflect aspects of the dynamics and modularity of interactomes as well as previous measures incorporating expression data, and are a powerful means for understanding the dynamic roles of hubs in interactomes. Second, we study the role of multifunctional genes (and proteins they encode) in protein interaction networks. Many genes in a genome have more than one function. However, genome-wide analysis of multifunctional genes and an explanation of the mechanisms underlying multifunctionality are still lacking. We leverage functional annotations of genes to extract a group of genes each of which has at least two completely different functions, and distinguish these, the most multifunctional genes, from the remaining genes that are currently known to have a single function. We find biologically significant differences between multifunctional and all other genes on a large scale. We show that multifunctional genes are intermodular and play a central role in the interactome, bridging different functional modules.

1 0

Systems talk on stable multithreading, Junfeng Yang, Monday Nov 25, 3:00pm
by Mike Freedman 25 Nov '13

25 Nov '13

Speaker: Junfeng Yang, Columbia Title: Determinism Is Not Enough: Making Parallel Programs Reliable with Stable Multithreading Date/time: 3-4pm on Monday November 25 Location: CS 402 Abstract: Our accelerating computational demand and the rise of multicore hardware have made parallel programs, especially shared-memory multithreaded programs, increasingly pervasive and critical. Yet, these programs remain extremely difﬁcult to write, test, analyze, debug, and verify. Conventional wisdom has attributed these difﬁculties to nondeterminism (i.e., repeated executions of the same program on the same input may show different behaviors), and researchers have recently dedicated much effort to bringing determinism into multithreading. In this talk, I argue that determinism is not as useful as commonly perceived: it is neither sufﬁcient nor necessary for reliability. We present our view on why multithreaded programs are difﬁcult to get right, describe a promising approach we call stable multithreading to dramatically improve reliability, and summarize our last four years’ research on building and applying stable multithreading systems. Bio: Junfeng Yang's research (http://www.cs.columbia.edu/~junfeng) centers on making reliable and secure systems. He earned his PhD at Stanford, where he created eXplode, a general, lightweight system for effectively finding storage system errors. This work has led to an OSDI '04 best paper, numerous bug fixes to real systems such as the Linux kernel, and a featured article in Linux Weekly news. He worked at Microsoft Research, Silicon Valley from 2007-2008, extending eXplode to check production distributed systems. MoDist, the resultant system, is being transferred to Microsoft product groups. He's now co-directing the Software Systems Lab (ssl.cs.columbia.edu) at Columbia University, where his recent work on making reliable parallel programs---the Tern/Peregrine/Parrot stable multithreading systems--- was featured in CACM, ACM Tech News, The Register, and many other sites. He won Sloan and AFOSR YIP both in 2012; and NSF CAREER in 2011.

1 1

3pm Tue Nov 26 talk on Internet censorship and control in CS 105 (small auditorium)
by Jennifer Rexford 21 Nov '13

21 Nov '13

Speaker: Nick Feamster, Georgia Tech Title: Defending Against Internet Censorship and Control, from Firewalls to Filter Bubbles Date/time: 3-4pm on Tuesday November 26 Location: CS 105 (small auditorium) Abstract: The Internet's promise of open communication and transparency is threatened by both censorship (blocking communication outright) and manipulation (otherwise affecting the performance that a user experiences or the information that a user sees). Censorship is a pervasive threat, with more than 60 countries around the world censoring Internet communications in some form. Unfortunately, many conventional censorship circumvention tools are detectable and can be blocked; in some cases, the use of such software may even be incriminating. Thus, users may need not only to defeat censorship mechanisms but also to hide the fact that they are doing so in the first place. In the first part of the talk, I will describe two systems that achieve this goal, Infranet and Collage. In addition to circumventing censorship firewalls, both Infranet and Collage provide users with the deniability that they are using the censorship circumvention system in the first place. In both systems, we achieve deniability by designing them so that the observable network traffic that they generate is statistically indistinguishable from the user's "normal" traffic patterns if the tools were not in use. Infranet achieves deniability by hiding a user's requests for Web content in other Web traffic that resembles a user's typical browsing pattern. Collage achieves deniability by hiding content in user-generated content sites and encoding a user's request for the content in a sequence of operations that a given user is likely to perform. In recent years, however, circumvention alone is insufficient: sophisticated organizations can also control users by manipulating network traffic. Manipulation can take many forms, from degrading performance to such an extent that a user does not want to use the service, to using Internet communication to generate propaganda (e.g., via social media), to attacking personalization algorithms to affect the results that a user sees in response to a search query. In the second part of the talk, I will describe several manipulation attacks that we have studied and inference techniques that we have developed to detect them. I will conclude with our ongoing efforts to tackle open challenges in this area, such as the deceptively challenging problem of confirming the existence of various forms of censorship in the first place. Bio: Nick Feamster is an associate professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, with a focus on network operations, network security, and censorship-resistant communication systems. In December 2008, he received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include the Technology Review 35 "Top Young Innovators Under 35" award, the ACM SIGCOMM Rising Star Award, a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, the IRTF Applied Networking Research Prize, and award papers at the SIGCOMM Internet Measurement Conference (measuring Web performance bottlenecks), SIGCOMM (network-level behavior of spammers), the NSDI conference (fault detection in router configuration), Usenix Security (circumventing web censorship using Infranet), and Usenix Security (web cookie analysis).

1 0

Colloquium Speaker Arjun Guha Thurs Nov 21, 4:30pm
by Nicole E. Wagenblast 20 Nov '13

20 Nov '13

Reclaiming Security for Web Programmers Arjun Guha , University of Massachusetts, Amherst Thursday, November 21, 4:30pm Computer Science, 105 The Web enables new classes of programs that pose new security risks. For example, because Web programs freely mix data and code from untrusted sources, major websites have been compromised by third-party components, such as malicious ads. In addition, users cannot fully control which programs run; Web programs are visited, not installed. Therefore, Web security is entirely in the hands of programmers, not users. I address the problem of securing existing Web programs, which are universally written in JavaScript. Unfortunately, JavaScript has several warts that make it difficult to reason about even simple snippets of code. Several companies have developed "Web sandboxes" to make JavaScript programming safe. However, these Web sandboxes have no security guarantees. In this talk, I show how programing languages research can be used to verify properties of Web applications. I present a type-based verification method for JavaScript that we use to find bugs in and produce the first verification of an existing, third-party Web sandbox. Programming language techniques can give us mathematical proofs of security, but attackers attack implementations, not theorems. I discuss our approach to doing principled, real-world Web security research, which combines semantics with systems. I also review additional projects that use our tools and techniques. Arjun Guha is an assistant professor of Computer Science at UMass Amherst. He enjoys tackling practical problems, while adhering to the mathematical foundations of programming languages. For example, his dissertation on JavaScript semantics and type-checking, from Brown University, is used by several other researchers as a foundation for their own work. As a postdoc at Cornell University, he developed a model of software-defined networking (SDN) in the Coq Proof Assistant, which is the foundation for a verified runtime and other SDN tools. For his research, he has developed and contributed to several software systems, such as LambdaJS, Frenetic, and Flapjax that are in active use.

1 1

Nagpal from Harvard CS to speak on Friday at 3:30 pm in Friend 113 on Taming the Swarm
by Scott Karlin 20 Nov '13

20 Nov '13

Friday, November 22nd 3:30 PM Friend Center 113 Taming the Swarm Prof. Radhika Nagpal Harvard University Cambridge, MA Biological systems, from cells to social insects, get tremendous mileage from the cooperation of vast numbers of cheap, and limited individuals. Cells with identical DNA cooperate to self-assemble large and complex organisms, and even regenerate after damage. Large colonies of tiny ants cooperate to forage over vast unknown areas, move large objects, and achieve as a group what no single ant could ever achieve. What would it take to create (build and program) our own artificial collectives of the scale and complexity that nature achieves? In this talk, I will discuss one of our recent and ongoing endeavors – the Kilobot project - which aims to create a 1024 ("kilo") robot swarm testbed for studying collective intelligence. Creating an autonomous robot collective at this scale poses many challenges, e.g. how do we bulk manufacture robust but low-cost robots, how do we move from micromanaging single robots to managing and programming a thousand autonomous entities? At the same time such a swarm allows us to study at scale many collective algorithms, inspired by engineering (coordinate systems), social insects (collective transport), and cells (self-assembly). I will talk about both the design of the Kilobot swarm and several algorithms we have studied using this system. A common theme in all of our work is understanding the global-to-local relationship: how complex and robust collective behavior can be systematically achieved from large numbers of simple agents. Radhika Nagpal is the Kavli Professor of Computer Science at Harvard University and a core faculty member of the Wyss Institute for Biologically Inspired Engineering. She received her PhD degree in Computer Science from MIT, and spent a year as a research fellow at the Systems Biology Department in Harvard Medical School. At Harvard she leads the self-organizing systems research group and her research interests span computer science, robotics, and biology. She has received several awards, including the 2012 Radcliffe Fellowship, the 2010 Borg Early Career Award, an NSF Career Award, and the Microsoft New Faculty Fellowship Award. Social Period following the seminar. For inquiries, please contact the Dept. of Mechanical & Aerospace Engineering at 609-258-0315 ALL VISITORS ARE WELCOME!

1 0

4:30pm talk today on routing algebras in room 302
by Jennifer Rexford 19 Nov '13

19 Nov '13

Speaker: Joao Sobrinho, Instituto de Telecomunicações Title: Algebra: A Tool for a Unifying View of Routing Protocol Behavior Date/time: 4:30-5:30pm, Tuesday November 19 Location: room 302 in the CS building Abstract: The Internet routing system is composed of millions of routers running one or more of several routing protocols---BGP, OPSF, IS-IS, RIP, EIGRP, DSR, AODV, OLSR, RPL---with the goal of guiding data-packets from sources to destinations. Beyond the specificity of every routing protocol, a number of questions are pertinent across wide classes of them, namely: • Does the routing protocol always terminate in a stable state devoid of forwarding loops and forwarding deflections? • Are the paths followed by data-packets optimal in some sense? • How much of the inherent resiliency of the network does the routing protocol exploit? • Does the routing protocol scale with the number of destinations? Routing selects paths for the transport of data-packets indirectly, through attributes they possess. Routing protocols operate by continually interleaving two processes: that of computing attributes of paths from characteristics of its constituent links; and that of choosing best attributes. The algebraic approach studies how the entwining of these two processes determines the global behavior of a routing protocol, providing answers to the questions above. In this talk, I will illustrate the unifying power of the algebraic approach by delving into the non-optimality of paths determined by EIGRP (Enhanced Interior Gateway Routing Protocol) and termination and resiliency issues raised by BGP (Border Gateway Protocol). In addition, I will survey recent applications of the algebraic approach, notably to the interconnection of routing instances and to route aggregation in the Internet. Bio: João Luís Sobrinho received his Licenciatura and Ph.D. degrees in Electrical and Computer Engineering from the Technical University of Lisbon, Portugal, in 1990 and 1995, respectively. During 1995 and 1996, he was a Member of the Technical Staff at Bell Labs, Nieuwegein, The Netherlands; he further consulted for Bell Labs, Murray Hill, NJ, from 1997 to 1999. He is currently Associate Professor at the Faculty of Engineering of the Technical University of Lisbon and a Researcher at the Telecommunications Institute. Prof. Sobrinho is a member of the IEEE and of the ACM. http://www.lx.it.pt/~jls/

1 0