- talks - lists.cs.princeton.edu

P Prabhu preFPO
by Melissa M. Lawson 12 Sep '12

12 Sep '12

Prakash Prabhu will present his preFPO on Tuesday September 18 at 11AM in Room 402. The members of his committee are: David August, advisor; David Walker and JP Singh, readers; Margaret Martonosi and Kai Li, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------- Semantic Language Extensions for Implicit Parallel Programming Several emerging ﬁelds of science of engineering are increasingly characterized by computationally intensive programs that generate exponential amounts of data. Without parallelization, such programs do not benefit from the increasing core counts available in today’s chip multiprocessors. However, it is widely perceived that writing correct and well performing parallel programs is an extremely hard problem. In order to understand the challenges faced by scientific programmers in effectively leveraging parallel computation, this dissertation presents an in-depth field study of the practice of computational science. Based on the results of the ﬁeld study, two new implicit parallel programming (IPP) solutions are proposed. IPP solutions offer the best of both automatic and explicit parallelization. With IPP, artificial constraints imposed by sequential models for automatic parallelization are overcome by use of semantic programming extensions that do not sacriﬁce the ease of sequential programming. These extensions are exploited by transformation tools to synthesize a correct parallel program without requiring enormous manual programming effort associated with explicit parallelization. The first IPP solution, Commutative Set, generalizes existing notions of semantic commutativity. It allows a programmer to expressively relax execution orders prohibited under a sequential programming model and enables multiple parallelism forms without additional parallelism constructs. The second IPP solution, WeakC, provides language extensions to weaken semantics of sequential data structures, and dynamically optimizes a parallel configuration of these data structures via a combined compiler-runtime system. Both Commutative Set and WeakC have been implemented within the clang/LLVM compiler framework, and are evaluated on several real-world applications running on real hardware, including some that are actively used by several scientists in their day-to-day research. Based on experimental results, this dissertation demonstrates the effectiveness of the proposed techniques.

1 0

W Kim FPO
by Melissa M. Lawson 12 Sep '12

12 Sep '12

Wonho Kim will present his FPO on Wednesday September 19 at 2PM in Room 402. The members of his committee are: Vivek Pai, advisor; Michael Freedman and Larry Peterson, readers; Jennifer Rexford and David Walker, nonreaders. A copy of his dissertation "Understanding Resource Usage and Performance in Wide-Area Distributed Systems", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Harlan Yu FPO
by Melissa M. Lawson 24 Aug '12

24 Aug '12

Harlan Yu will present his FPO on Friday August 31 at 10AM in 306 Sherrerd Hall (note room!). The members of his committee are: Ed Felten, advisor; Jennifer Rexford and Beth Noveck (New York Law School), readers; Michael Freedman and Matthew Salganik (SOC), nonreaders. A copy of his dissertation, "Designing Software to Shape Open Government Policy", is available in Room 310. Everyone is invited to attend his talk.

1 0

A Bhaskara FPO
by Melissa M. Lawson 24 Aug '12

24 Aug '12

Aditya Bhaskara will present his FPO on Thursday August 30 at 1PM in Room 402. The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and Zeev Dvir, readers; Bernard Chazelle and Amit Singer (MAT), nonreaders. A copy of his thesis, "Finding Dense Structures in Graphs and Matrices", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Rob Dockins FPO
by Melissa M. Lawson 17 Aug '12

17 Aug '12

Rob Dockins will present his FPO on Friday August 24 at 10AM in Room 402. The members of his committee are: Andrew Appel, advisor; David Walker and Xavier Leroy (INRIA), readers; David August and Mark Braverman, nonreaders. A copy of his thesis, "Operational Refinement for Compiler Correctness", is available in Room 310. Everyone is invited to attend his talk.

1 0

A Vijayaraghavan FPO
by Melissa M. Lawson 16 Aug '12

16 Aug '12

Aravindan Vijayaraghavan will present his FPO on Thursday August 23 at 2PM in Room 402. The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and Mark Braverman, readers; David Blei and Konstantin Makarychev (Microsoft Research), nonreaders. A copy of his thesis, "Beyond Worst Case Analysis in Approximation Algorithms", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Chong Wang FPO
by Melissa M. Lawson 05 Jul '12

05 Jul '12

Chong Wang will present his FPO on Tuesday July 10 at 11AM in Room 402. The members of his committee are: David Blei, advisor; Rob Schapire and Eric Xing (CMU), readers; Olga Troyanskaya and Andrea LaPaugh, nonreaders. A copy of his thesis, "Hierarchical Bayesian Modeling: Efficient Inference and Applications", is on display in Room 310. Everyone is invited to attend his talk.

1 0

11am Tue May 29 talk on FloodLight OpenFlow controller
by Jennifer Rexford 27 May '12

27 May '12

Speaker: Mike Cohen, BigSwitch Networks Title: The FloodLight OpenFlow Controller Date/time: 11am-noon on Tuesday May 29 Location: room 402 in the CS building Abstract Software-Defined Networking (SDN) and OpenFlow are quickly emerging as powerful trends in the networking industry. By separating the control and data planes, these technologies are accelerating the innovation cycle and creating opportunities for new application research and development. This talk will provide an overview of SDN and OpenFlow and introduce Floodlight, an Apache-licensed OpenFlow controller. Floodlight is driven by a community of developers including Big Switch Networks and was designed to offer a fast, easy-to-use programming environment, a rich set of development tools, an interoperability with a wide array of networking devices. The talk will also discuss other useful SDN development tools and highlight active areas for research and development. Biography of Speaker Mike Cohen is a product manager at Big Switch Networks. He was previously an early engineer on VMware’s hypervisor team and a search infrastructure product manager at Google. Mike holds a B.S.E in Electrical Engineering from Princeton and Masters from Harvard.

1 0

R Kiefer general exam
by Melissa M. Lawson 18 May '12

18 May '12

Rob Kiefer will present his research seminar/general exam on Thursday May 24 at 9AM in Room 402. The members of his committee are: Michael Freedman (advisor), Jen Rexford, and Margaret Martonosi. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------ Abstract: User devices are being used in increasingly diverse ways and conditions, and are connected to increasingly diverse network resources. Different conditions call for different network resources to be used (e.g., using cellular connectivity when away from Wi-Fi access points), and different resources come with varying restrictions (e.g., monthly data caps) that determine how and when they should be used. In addition, users carrying these devices are increasingly mobile, which means that the best network resource to utilize can change relatively quickly. Today, this decision process is typically done manually by the user, which is both clumsy and suboptimal. In this work, empowered by the new Serval network stack that supports transparent connection migration, we design and prototype a framework that allows users or applications to write network policies against a library containing system conditions such as battery statistics, interface statistics, and ongoing network flow statistics. This framework provides a coherent solution for determining how a device’s network resources should be used on a per-flow basis. The framework continuously evaluates each flow against a policy, which determines what action to take on the flow (e.g., “migrate this flow to Wi-Fi”). Policies are expressed as scripts to allow them to be flexible and expressive. We evaluate several different sample policies on our Android- and Linux-based prototype, including one for resilient connectivity, for minimizing latency, and for maximizing throughput. Reading list: 1. J.H. Saltzer, D.P. Reed and D.D. Clark. End-to-end arguments in system design. 2. A. C. Snoeren and H. Balakrishnan. An end-to-end approach to host mobility. In MOBICOM, Aug. 2000. 3. D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI, Mar. 2011. 4. Shyamnath Gollakota and Dina Katabi, "ZigZag Decoding: Combating Hidden Terminals in Wireless Networks," ACM SIGCOMM, 2008. 5. H. Soroush, P. Gilbert, N. Banerjee, B. Levine, M. Corner, L. Cox, "Concurrent Wi-Fi for Mobile Users: Analysis and Measurements", in the 7th International Conference on emerging Networking EXperiments and Technologies (CoNEXT'11), Tokyo, Japan, December 2011. 6. Srikanth Kandula, Kate Ching-Ju Lin, Tural Badirkhanli and Dina Katabi. FatVAP: Aggregating AP Backhaul Bandwidth. NSDI 2008. 7. "MultiNet: Connecting to Multiple IEEE 802.11 Networks Using a Single Wireless Card". Ranveer Chandra, Paramvir Bahl and Pradeep Bahl. Proceedings of IEEE Infocom 2004, Hong Kong, March 7-11, 2004. 8. “Juggler: Virtual Networks for Fun and Profit”, Anthony J. Nicholson, Scott Wolchok, Brian D. Noble, IEEE Transactions on Mobile Computing, vol. 9 (2010), pp. 31-43. 9. Mobile Apps: It's time to move up to ConDOS. David Chu, Aman Kansal, Jie Liu, Feng Zhao. (HotOS 2011) 10. Erik Nordstrom, David Shue, Prem Gopalan, Rob Kiefer, Matvey Arye, Steven Ko, Jennifer Rexford, and Michael J. Freedman. Serval: An End-Host Stack for Service-Centric Networking. 11. Computer networks: a systems approach. Larry L. Peterson and Bruce S. Davie. (Textbook)

1 0

Fwd: final abstract and reading list
by Melissa M. Lawson 18 May '12

18 May '12

Omri Weinstein will present his research seminar/general exam on Wednesday May 23 at 2PM in Room 402. The members of his committee are: Mark Braverman (advisor), Zeev Dvir, Sanjeev Arora. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. -------------------------------- Abstract: In the late 1940's Shannon developed his information theory in order to understand the one way data transmission problem. His work revealed the tight connection between communication and information, namely, that a the description length of a one-way message is essentially equivalent to the amount of information it contains. The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in *interactive* settings, where two (or more) parties must engage in an interactive conversation in order to accomplish some desirable task. Motivated by applications in communication complexity, our main quantity of interest is the Information Complexity of a problem, which informally measures the average amount of information the players need to reveal each other about their inputs in order to solve the problem. We provide the first general technique for proving information lower bounds on two-party communication problems, by showing that the discrepancy lower bound (which applies to randomized communication complexity) also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $\mu$ is $Disc_\mu f$, then any two party randomized protocol computing $f$ must reveal at least $\Omega(\log (1/Disc_\mu f))$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $\{0,1\}^n\times\{0,1\}^n$ must reveal $\Omega(n)$ bits of information to the participants. The proof of our main result develops a new simulation procedure that may be of an independent interest. In addition, we prove that the discrepancy of the Greater-Than function is $\Omega(1/\sqrt{n})$, which provides a simplified proof of the $\Omega(\log n)$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $\Omega(\log n)$ lower bound on its information complexity. I will try to cover some of our recent results: An optimal zero-error information-cost protocol for the notable AND function, which in turn enables us to compute the *exact* (0.48n) communication complexity of the well studied Disjointness function. Our results contribute to the characterization and understanding of several properties of the information complexity function, and in particular leads to the computability of this measure. The first result is a joint work with Mark Braverman, and the second, with Mark Braverman, Denis Pankratov and Ankit Garg. READING LIST: 1) Information = Amortized Communication [BR]. 2) How to Compress Interactive Communication [BBCR]. 3) Interactive Communication Complexity [Bra]. 4) Strong Direct Product [JPY]. 5) The communication complexity of Gap Hamming Distance [Shrestov]. 6) The communication complexity of Correlation [HJMR]. BOOK: Computational Complexity - A modern approach [Arora Barak].

1 1