- talks - lists.cs.princeton.edu

Y Wang general exam
by Melissa Lawson 13 May '11

13 May '11

Yida Wang will present his research seminar/general exam on Thursday May 19 at 2PM in Room 302 (note room!). The members of his committee are; Kai Li (advisor), Moses Charikar, Rob Schapire. 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. ---------------- Full Correlation Computation and Analysis of Large-Scale FMRI Abstract: Human brain imaging such as Functional Magnetic Resonance Imaging (fMRI) has made transformational impacts on neuroscience. However, due to technology limitations in the past, researchers have constrained their analyses by making assumptions that are biased or false, leading to missed opportunities for science discovery, and in the worst case, incorrect inferences. In this project, we are conducting our research by fully leveraging recent advances in large-scale computing techniques, for the first time, to analyze the full correlation matrix of fMRI data. The success of our approach will result in a quantum increase in the power of neuroimaging analysis, extracting 7 orders of magnitude more information from the data than previous approaches and opening up qualitatively new opportunities for neuroscience research. In order to fully leverage the advances in multicore processors and parallel computing, we have developed a parallel data analysis tool for a cluster of computers. This tool can achieve high utilization of CPU cores on a cluster. On a system with 528 CPU cores, the tool is able to perform full-correlation study of one-hour fMRI dataset in 2.5 days, more than an order of magnitude improvement over a native parallel approach. We have also studied how to analyze and visualize massive amounts of full-correlation result data (petabytes) and built corresponding tools for the data analysis pipeline. In this talk, I will describe our approach and report the current status and future plans. This work is advised by Prof. Moses Charikar and Prof. Kai Li at Princeton Computer Science Department, and Prof. Nicholas Turk-Browne and Prof. Jonathan Cohen at Princeton Neuroscience Institute. Reading List: Book: Computer Architecture: A Quantitative Approach, 4th Edition, John Hennessy and David Patterson Paper: Goto, K. and Van De Geijn, R. 2008. Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw. 34, 3. J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters, Proc. 6th Symp. Operating System Design and Implementation (OSDI), Usenix Assoc., 2004, pp. 137-150. Pereira F, Mitchell T M and Botvinick M. Machine learning classifiers and fMRI: A tutorial overview Neuroimage. 2008 Norman, K. A., Polyn, S. M., Detre, G. J. and Haxby, J. V. Beyond mind-reading: multi-voxel pattern analysis of fMRI data. Trends Cogn. Sci. 10, 424-430 (2006). R. J. Bayardo, Y. Ma and R. Srikant. Scaling up all pairs similarity search. In WWW, 2007. R. Vernica, M. J. Carey and C. Li. Efficient Parallel Set-Similarity Joins Using MapReduce. In SIGMOD, 2010. J. Cheverud and G. Marriog. Comparing covariance matrices: Random skewers method compared to the common principal components model. Genetics and Molecular Biology, 2007.

1 0

S Yang general exam
by Melissa Lawson 12 May '11

12 May '11

Siyu Yang will present her research seminar/general exam on Monday May 16 at 2PM in Room 402. The members of her committee are: Bob Tarjan (advisor), Bernard Chazelle, and Sanjeev Arora. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------------- On the Competitiveness of Binary Search Trees Abstract: I will present two results related to the competitiveness problem of binary search trees. The first result is a heterogeneous finger search tree as a pure binary tree in which the desired access and update time bounds hold in the worst case. In a heterogeneous finger tree, two fingers pointing to the minimum and the maximum keys in the tree are maintained, and all operations on the binary search tree take running time logarithmic in the distance to the closer finger. We present a solution to this problem. This solution can be used to construct an O($\log\log n$)-competitive binary search tree with O($\log n$) worst-case running time, simplifying an improvement to previous data structures by Demaine et al. I will also present an approach to proving that splay trees are O(loglogn)-competitive. Such a result for splay trees would match the best competitive bound, which holds for types of search trees specifically designed to achieve the bound. The dynamic optimality conjecture for splay trees has been open for more than two decades, but no non-trivial results have yet been proved. My approach to a proof uses a divide-and-conquer framework. This is joint work with Robert Tarjan Reading List: [Book] Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. [Papers] Bose, P., Dou¨ieb, K., Dujmovi´c, V., Fagerberg, R.: An O(log log n)-competitive binary search tree with optimal worst-case access times. In: Proc. 12th Scandinavian Symp. and Workshop on Algorithm Theory. pp. 3849 (2010) R. Cole. On the dynamic Finger conjecture for splay trees. part ii: The proof. SIAM Journal on Computing, 30:2000. R. Cole, B. Mishra, J. Schmidt, and A. Siegel. On the dynamic Finger conjecture for splay trees. part i: Splay sorting log n-block sequences. SIAM Journal on Computing, 30:2000, 1995. E. D. Demaine, D. Harmon, J. Iacono, and M. Patrascu. Dynamic optimality - almost. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 484-490, Washington, DC, USA, 2004. IEEE Computer Society. L. J. Guibas, E. M. McCreight, M. F. Plass, and J. R. Roberts. A new representation for linear lists. In Proceedings of the ninth annual ACM symposium on Theory of computing, STOC '77, pages 49-60, New York, NY, USA, 1977. ACM. D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J. ACM, 32:652-686, July 1985. R. E. Tarjan. Sequential access in splay trees takes linear time. Combinatorica, 5:367-378, September 1985. C. C. Wang, J. Derryberry, and D. D. Sleator. 2006. O(log log n)-competitive dynamic binary search trees. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA '06). ACM, New York, NY, USA, 374-383. R. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput., 18:56-67, February 1989.

1 0

J Kroll general exam
by Melissa Lawson 06 May '11

06 May '11

Joshua Kroll will present his research seminar/general exam on Friday May 13 at 10 AM in Room 302 (note room!). The members of his committee are: Ed Felten 9advisor), Andrew Appel, and Mike Freedman. Everyone is welcome 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. -------------------------------------- Title: Portable, Verifiable Low-Level Memory Safety Abstract Operating systems can provide isolation between different programs running on the same computer. How- ever, this protection is too coarse or too slow for large applications with extensible functionality, such as browsers, database and web servers, device drivers, and document editors. It is thus necessary to have ro- bust, trustworthy protections that are valid below the process abstraction provided by the operating system. Here, we present two results in the area of Software Fault Isolation (SFI), a mechanism for just this sort of protection. First, we present BakerSFIeld, an SFI framework [1, 2, 3] for the x64 instruction set architecture [4]. SFI is an increasingly widely-used sub-process sandboxing technique in which applications are rewritten using special code-generation tools and augmented with dynamic guards that ensure policy compliance with minimal overhead. BakerSFIeld is derived from PittSFIeld [2], and retains the assembly language rewriting style of its predecessor. We measure the performance of BakerSFIeld on a modern 64-bit desktop machine and determine that it has significantly lower overhead than its 32-bit cousin. But such a scheme is not useful for security unless we are sure that its implementation can be trusted. Thus, we present a novel formally verified sandboxing solution built on top of the CompCert C compiler [9]. This tool generates sandboxed code by rewriting abstract syntax inside CompCert to ensure that all generated code complies with the sandboxing policy. Through a combination of static analysis and dynamic checking, we provide code which is provably policy-compliant at runtime but remains true to the SFI philosophy of ensure-don't-check. As traditional SFI makes use of very concrete aspects of a system's address structure for security, our most surprising result is that an SFI system can also be implemented in CompCert's more abstract setting. Reading List-Papers [1] R. Wahbe, S. Lucco, T. Anderson, and S. Graham, "Efficient software-based fault isolation", in Proceedings of the Fourteenth ACM symposium on Operating systems principles. ACM, 1994, p. 216. [2] S. McCamant and G. Morrisett, "Evaluating SFI for a CISC architecture", in 15th USENIX Security Symposium, 2006, pp. 209-224. [3] B. Yee, D. Sehr, G. Dardyk, J. Chen, R. Muth, T. Ormandy, S. Okasaka, N. Narula, and N. Fullagar, "Native client: A sandbox for portable, untrusted x86 native code", in Proceedings of the IEEE Symposium on Security and Privacy, 2009. [4] D. Sehr, R. Muth, C. Biffle, V. Khimenko, E. Pasko, K. Schimpf, B. Yee, and B. Chen. Adapting software fault isolation to contemporary CPU architectures. In Proceedings of USENIX Security, pages 1-11, 2010. [5] J.R. Douceur, J. Elson, J. Howell, and J.R. Lorch. Leveraging legacy code to deploy desktop applications on the web. In Proceedings of the 2008 Symposium on Operating System Design and Implementation, December 2008. [6] B.N. Bershad, S. Savage, P. Pardyak, E.G. Sirer, M.E. Fiuczynski, D. Becker, C. Chambers, and S. Eggers. Extensibility safety and performance in the SPIN operating system. In ACM SIGOPS Operating Systems Review, volume 29, pages 267-283. ACM, 1995. [7] G.C. Necula and P. Lee. Safe kernel extensions without run-time checking. In Proceedings of the Second Symposium on Operating Systems Design and Implementation. USENIX, 1996. [8] Andrew W. Appel. Foundational proof-carrying code. In Proceedings of the IEEE Symposium on Logic in Computer Science. IEEE Computer Society, 2001. [9] X. Leroy. A formally verified compiler back-end. Journal of Automated Reasoning, 43(4):363-446, 2009. [10] F.B. Schneider, G. Morrisett, and R. Harper. A Language-Based Approach to Security. 2000. Reading List-Textbooks [1] Ross Anderson. Security Engineering: A Guide to Building Dependable Distributed Systems, Second Edition. Wiley Publishing, Inc., 2008. [2] Benjamin C. Pierce. Types and Programming Languages. The MIT Press, 2002.

1 0

H Nguyen generals - correction
by Melissa Lawson 03 May '11

03 May '11

Correction: Huy's advisor is Moses Charikar, not Sanjeev Arora. Sorry for the error. --Melissa

1 0

Invitation to COS 333 Project Presentations
by Robert Dondero 02 May '11

02 May '11

On Thursday May 5 and Friday May 6 this year's COS 333 students will give public presentations of their class projects. It's likely that the presentations will be interesting and well done, as they have been in previous years. You're invited! Please feel free to attend as many presentations as you want. Friends are welcome too. The presentations will be in Computer Science Building 105. A schedule, along with a brief description of each project, is appended below. I hope you can attend some of the presentations. Bob Dondero Robert M. Dondero, Ph.D. Lecturer, Department of Computer Science Princeton University ----------------------------------- Thursday 5/5 1:00-1:30: PEOPLES PEOPLES Enables the Observation of Populations Living in Everyday Society Social Science research has traditionally required data that is difficult to gather; by using smartphones as data collection tools we can overcome the methodological limitations that have hampered social science research and kept important questions from being answered. We will design an open source Android application that will be distributed to over 100 reentering prisoners to track their job-search experience. The application will enable: collection of location-based data, collection of anonymized phone call information, distribution of short questionnaires to study participants, contact between study participants and researchers through audio or video messages. We aim to design an application that will outlive the initial study and that is general enough to allow other researchers to use it. We will design a simple web-based front-end that will allow researchers to download information, monitor subject participation, and access communications sent by participants. All together, this will be a powerful tool for sociologists, enabling them to conduct useful, targeted, and inexpensive research on almost any population. ----------------------------------- Thursday 5/5 1:30-2:00: SSH Startups Startups and growing companies are hungry for engineering talent. The truth is that quality developers are difficult and costly to find, let alone recruit. Companies often look to young college students for fresh minds to work over the summer and eventually move to full time, but many come away with summer experiences that don't make use of their true talents or align much with what they are interested in. The key to solving these problems lies in an effective way of matching up companies and student engineers. SSH Startups is a portal for connecting college students to technical internships. The site will feature a listing of students in addition to a listing of companies, so that both sides can reach out to one another. It will have methods for companies to assess the quality of interns without having to browse, open, and read through hundreds of resumes. It will provide means to match students with jobs based on their interests, without the need to search through countless pages of listings. Its sleek, simple interface will focus on the elements that matter, not flooding users with excess information or demanding massive amounts of time to be devoted to the discovery process. SSH Startups: We aim to provide engineering talent for companies, exciting internships for students, and a killer user experience that streamlines the matchmaking process as much as possible. ----------------------------------- Thursday 5/5 2:00-2:30: MealChecker Currently, the system for meal exchanges between members of different eating clubs operates in an outdated and inefficient manner. At the time of the meal, the member must fill out a slip recording the names and clubs of the host and guest, and at the end of every month the clubs sort through these slips, matching them up and charging those members who did not reciprocate meals. All of this is done manually, and is far less organized and efficient than a computerized system would be. We propose to automate this system, saving time for the clubs and providing valuable information to both the clubs and their members. With our system, members would simply enter their meal exchange information using a Web interface connected to a database that keeps track of all exchanges. At the end of the month, the system would automatically sort through the exchanges and send the results to the clubs. Members would also be able to check how many meals are owed, a functionality entirely absent in the current system. Most valuable to the clubs, our system will keep statistics on the exchanges, which would give them the information they need to plan ahead and anticipate trends. Our system would be highly beneficial to both clubs and their members, and would replace an antiquated manual system direly in need of revision. ----------------------------------- Thursday 5/5 3:30-4:00: PlayInPerson The goal of our project is to create an online, chatroom-based environment where people can meet and interact through video chat games. For example, two friends living in different countries can use our site to chat face to face while collaboratively working on a crossword puzzle. Similarly, 4 strangers can meet up and play a game of video poker - the game will be realistic because each person will be able to see his opponents' faces. The goal is to create an in-person like experiences online; hence, our website will be playinperson.com. ----------------------------------- Thursday 5/5 4:00-4:30: OneTree Princeton's student groups share certain commonalities that result in the formation of natural sub-communities within the Princeton community. Students could use such a hierarchical "tree" structure to find groups and events tuned to their liking, while groups benefit from increased exposure to a more targeted audience. We aim to create these "virtual group/community centers" where groups may publicly display information, announcements, special events, and more to the general public. The main competitor, Facebook, is user-centric rather than group-centric, limiting the potential for more complex group relationships. We propose a website that models each group or community as an aggregation of many smaller sub-communities. For example, each dance group is part of the dance community, which in turn is part of the performing arts community, which finally is part of the Princeton community as a whole. Students can thereby view any particular community's page and see an aggregation of events and announcements posted by each sub-community, and browse and navigate between pages with ease. Essentially, our website is offering an organized and interconnected platform which improves the interactions between groups and the general public. ----------------------------------- Thursday 5/5 4:30-5:00: The Commons The Commons is an interactive, multiplayer online implementation of the original board game by Sigrid Adriaenssens. The game is based on Settlers of Catan with added features that address the issue of community-driven sustainability. In The Commons, players compete to develop the most successful empire in an initially unsettled and unhospitable world. Players can build cities in different areas of the world and take advantages of the area's renewable and non-renewable natural resources--like lumber, water power, oil--to build their civilizations. Players must also make decisions about how their actions will affect the environmental health of the world as a whole. By cooperating, players can work together to improve the total quality of life in the world. However, failure to cooperate can lead to the loss of natural resources, the wrath of fellow players, and, eventually, the death of the world and end of the game. ----------------------------------- Friday 5/6 1:00-1:30: Manos The XBOX Kinect is an incredible new technology released towards the end of 2010 that combines an RGB camera and an infrared depth sensor that allows users to control the XBOX 360 gaming console with body motions, not just thumbs. Since its release, an ever growing community of developers has created ways to process the data produced by the Kinect through the use of a personal computer, allowing a computer to track skeletons and fingertips, or a user to control a robot with gestures. Another way this technology has been harnessed has been to allow a user to interact with an operating system. Using bodily gestures to move a mouse cursor around the screen to select files and folders, to browse the web, or to play a game are examples of various implementations. The common feature of all of them however is that the gestures required are predefined; there is no customizability. Our product, Manos, allows a user to develop custom mappings between gestures and actions. Each user can train our product to recognize a certain gesture and link that action to increasing or decreasing the computer's volume, or to launch a certain type of program. In sum, our product allows for a user to customize this new technology to his or her own needs, which we believe will believe will be a central technology in the living room and elsewhere in the coming months and years. ----------------------------------- Friday 5/6 1:30-2:00: Bigfoot Imagine that it's 10pm on Friday night, and you want to know where people are on campus. Wouldn't it be nice if you had a map that showed you this information? Well, Bigfoot is exactly that. Bigfoot is an iPhone application and web interface that shows the movement of Princeton students over time -- both on a personal and aggregate level. Log in with user ID and you can see where you've been spent most of your time today, last week, or maybe just on Tuesdays last month between the hours of 7 and 9pm. Switch to the aggregate map and you can view the location of all Princeton students. There's the answer to your question. You can even filter the map by gender, major, residential college, or class year, because maybe Rocky wants to throw a study break when most of its students are in the area. It's all available on a website and on your iPhone. ----------------------------------- Friday 5/6 2:00-2:30: TigerAlbum What many pop culture websites have proven is that a tight-knit community of frequent visitors can spring up from the simplest collaboration of short, witty, well-moderated text posts. With TigerAlbum, we want to take this to the next level with geotagged photography. Imagine being able to see what's happening, hip, funny, and new around Princeton at an instant, on a map. And not having to do much to add your own photographs on the go with a simple shoot and submit smart-phone apps. TigerAlbum will allow users to search for photographs on the map, share their favorites with friends and discuss them through comments with a very intuitive and appealing interface. ----------------------------------- Friday 5/6 3:30-4:00: Singaporean Bridge An Android app for all card loving players out there. Singaporean Bridge is a trick-winning game rising in popularity that is as simple to play as, but more enjoyable than, Hearts. Whether in single-player mode against AIs of variable difficulty or in multi-player mode against other human players, a groovy and easy-to-use user interface makes it accessible to anyone, regardless of age, level and experience. Play competitively against friends, or complete strangers, improve your ranking and become the new champion! Play anytime, anywhere, with anyone! ----------------------------------- Friday 5/6 4:00-4:30: PUrr Right now, reserving a residential college room for a meeting or event is a real pain. There is no one repository for information regarding attributes and possible booking hours for a room, and the websites for actually booking a room are likewise decentralized. Moreover, the system is poorly automated for college administrators who have to check individual emails to approve them as well as manually advertise when rooms will be unavailable. Our goal is to streamline the process on both sides as well as improve the search experience for users who need a specific type of room. We plan to do this by having a two sided server which will contain calendar information for all the residential college rooms which are available to be booked. Administrators will be able to specify how far in advance students will be able to book, block off days for college events and determine what sort of credentials will be needed to book a room. After a small set up period, administrators will rarely be required to actively approve/requests: although they will be able to see who has reserved when. Meanwhile, students will have booking, room information and search services for all buildings consolidated in one webpage. You can search for rooms based on capacity, equipment availability and time availability among other things. Each room will have an information page which lists these features along with a photo and recent usage history. Hopefully these features will lead to students using the room which suits their need best instead of being limited only to rooms they already know. Excluding some authentication and room searching details, this structure is very general and should very easily allows us to manage room reservation for all residential colleges as well as other places (such as the music building). We do require information on all the rooms which we plan to make available as well as the ability to interface with the university's authentication system but neither of these should be difficult to obtain. Ultimately, we hope that this project will greatly simplify an important task for both students and college officials. ----------------------------------- Friday 5/6 4:30-5:00: Room Scheduling System There is a problem on campus. People are needlessly wasting time and getting frustrated by a disorganized system for scheduling rooms on campus. Right now, the system involves looking up email addresses and sending requests to administrators without any certainty of availability. Depending on the administrator, it could take days before you even find out that the room is not available at that time, so you have just wasted time and now have to scramble to find an acceptable alternative. This uncertainty, wasting of time, and needless hassle can easily be avoided with a centralized service. Imagine, you want a certain type of room at a certain time. With our system, you merely have to open your browser, search for the type of room you want, and you instantly see when certain rooms are available. You click on the room at the right time to make a request, and then you are done. Simple. Intuitive. No uncertainty in your scheduling, and no wasted time. -----------------------------------

1 0

Yahoo! talk starting in 10 minutes (1pm) in CS 105
by Mike Freedman 02 May '11

02 May '11

Datacenter Network Architecture @ Yahoo!: Past, present, and challenges for the future Igor Gashinsky, Yahoo! As the number of people and applications on the internet grows exponentially, so do the complexities of serving vast amounts of information. From the progression to unlimited e-mail storage, 10+ MegaPixel photos and HD streaming video being stored and shared online, to semi-real-time page personalization and real time search applications, the storage and computing power requirements have grown by leaps and bounds over the past 15 years. Ever wonder what the datacenter networks supporting these applications look like? This talk will provide a basic overview of large-scale datacenter network design principles, stepping through a history of how those designs evolved at Yahoo! over the years, the challenges that were faced, their solutions, as well as the challenges we anticipate in the (near) future. Igor Gashinsky is a principal architect at Yahoo!, a global content provider, where he is involved in projects ranging from overall network design (including highly resilient switching and routing architecture, peering, MPLS, L4-7 load balancing), as well as scalable content delivery methodologies and DNS architecture. Prior to his 8.5 years with Yahoo!, Igor worked as a Senior Systems & Network Engineer for HotJobs.com, as well as consulted for a number of clients, working on network and systems architecture, network security, system clustering/HA, high-performance storage solutions, and general Unix system and network administration. Igor holds a BS in Computer Science from Stevens Institute of Technology.

1 0

H Nguyen general exam
by Melissa Lawson 02 May '11

02 May '11

Huy Nguyen will present his research seminar/general exam on Thursday May 5 at 2PM in Room 302. The members of his committee are Sanjeev Arora (advisor), Moses Charikar, and Bernard Chazelle. 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 Given a set of n points in \ell_{1}, how many dimensions are needed to represent all pairwise distances within a specific distortion ? This dimension-distortion tradeoff question is well understood for the \ell_{2} norm, where O((\log n)/\epsilon^{2}) dimensions suffice to achieve 1+\epsilon distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in \ell_{1}. A recent result shows that distortion 1+\epsilon can be achieved with O(n/\epsilon^{2}) dimensions. On the other hand, the only lower bounds known are that distortion \delta requires n^{\Omega(1/\delta2)} dimension and that distortion 1+\epsilon requires n^{1/2-O(\epsilon \log(1/\epsilon))} dimensions. In this work, we show the first near linear lower bounds for dimension reduction in \ell_{1}. In particular, we show that 1+\epsilon distortion requires at least n^{1-O(1/\log(1/\epsilon))} dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in \ell_{1}. This is joint work with Alexandr Andoni, Moses Charikar, and Ofer Neiman. Reading list Book Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. Papers Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David Woodruff. "Efficient Sketches for Earth-Mover Distance, with Applications," Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on , vol., no., pp.324-330, 25-27 Oct. 2009 Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. 2008. Earth mover distance over high-dimensional spaces. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 343-352. Bo Brinkman and Moses Charikar. 2005. On the impossibility of dimension reduction in l1. J. ACM 52, 5 (September 2005), 766-788. Moses Charikar, Amit Sahai, "Dimension Reduction in the \ell _1 Norm," Foundations of Computer Science, Annual IEEE Symposium on, p. 551, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002 Sariel Har-Peled, "A Replacement for Voronoi Diagrams of Near Linear Size," Foundations of Computer Science, Annual IEEE Symposium on, p. 94, 42nd IEEE symposium on Foundations of Computer Science (FOCS'01), 2001 Piotr Indyk. On Approximate Nearest Neighbors under l[infinity] Norm, Journal of Computer and System Sciences, Volume 63, Issue 4, December 2001 Piotr Indyk. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (May 2006), 307-323. James R. Lee, Assaf Naor, Embedding the diamond graph in L_p and dimension reduction in L_1. Geometric And Functional Analysis, Volume 14, Number 4, 745-747, DOI: 10.1007/s00039-004-0473-8 James R. Lee, Manor Mendel, Assaf Naor, Metric structures in L1: dimension, snowflakes, and average distortion, European Journal of Combinatorics, Volume 26, Issue 8, November 2005, Pages 1180-1190, ISSN 0195-6698, DOI: 10.1016/j.ejc.2004.07.002. Rafail Ostrovsky, Yuval Rabani. Low distortion embedding for edit distance, Preliminary version appeared in STOC '05. Full version JACM, 2008.

1 0

DH Lee General exam
by Melissa Lawson 29 Apr '11

29 Apr '11

Donghun Lee will present his research seminar/general exam on Wednesday May 4 at 1PM in Room 402. The members of his committee are: Warren Powell (ORFE, advisor), Rob Schapire, and Tom Funkhouser. 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 Value iteration and Q learning algorithms overestimate their value functions due to bias introduced by the maximum operator in the update rules. The bias can be substantial when these algorithms are applied to problems which contain large variances in rewards due to innate stochasticity in the cost function. This problem gets worse as the action space gets larger. We aim to bound the value function when there exist such bias introduced by the maximum operator in these algorithms. We seek to gain insights into the rate of convergence of the value function in the presence of high levels of noise in the cost function. Reading List Books . Powell,W. B. (2007). Approximate Dynamic Programming: Solving the Curses of Dimensionality, chapter 6, pages 179-224. Wiley-Interscience . Bertsekas, D. P. (2009). Dynamic Programming and Optimal Control, chapter 6 sections 6.1-6.5, pages 327-446. Athena Scientific . Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach, 2nd Edition, chapter 21, pages 763-789. Prentice Hall Papers . Even-Dar, E. and Mansour, Y. (2003). Learning rates for Q-learning. Journal of Machine Learning Research, 5:1-25. . Kearns, M. and Singh, S. (1999). Finite-sample convergence rates for Q-learning and indirect algorithms. In Neural Information Processing Systems, volume 12, pages 996-1002. MIT Press. . Kulkarni, S. R. and Horn, C. S. (1996). An alternative proof for convergence of stochastic approximation algorithms. IEEE Transactions on Automatic Control, 41(3):419-424. . Lim, S. H. and DeJong, G. (2005). Towards finite-sample convergence of direct reinforcement learning. In Proceedings of European Conference on Machine Learning, pages 230-241. . Strehl, A. L., Li, L., and Littman, M. L. (2009). Reinforcement learning in finite MDPs: PAC analysis. Journal of Machine Learning Research, 10:2413-2444. . Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:185-202. . Wang, I.-J., Chong, E. K., and Kulkarni, S. R. (1996). Equivalent necessary and sufficient conditions on noise sequences for stochastic approximation algorithms. Advances in Applied Probability, 28:1996.

1 1

C Schlesinger general exam
by Melissa Lawson 28 Apr '11

28 Apr '11

Cole Schlesinger will present his research seminar/general exam on Wednesday May 4 at 10AM in Room 402. The members of his committee are: David Walker (advisor), David August, and Andrew Appel. 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: Modern applications contain libraries and components written by different people at different times in different languages, often including unsafe languages like C or C++. As a result, one bug, such as a buffer overflow, in any component, can compromise the security and reliability of every other component. To help mitigate these problems, we introduce Yarra, a conservative extension to C with mechanisms for enforcing data integrity and partial safety, even when code is linked against unknown C libraries or binaries. Yarra programmers specify their data integrity requirements by declaring critical data types and ascribing these critical types to important data structures. Yarra guarantees that such critical data is only written through pointers with the given static type. Any attempt to write to critical data through a pointer with an invalid type (perhaps because of a buffer overrun) is detected dynamically. We formalize Yarra's semantics and prove the soundness of a program logic designed for use with the language. A key contribution is to show that Yarra's semantics are strong enough to support sound local reasoning and the use of a frame rule, even across calls to unknown, unverified code. We evaluate a prototype implementation of a compiler and runtime system for Yarra by using it to harden four common server applications against known non-control data vulnerabilities. We show that Yarra defends against these attacks with only a negligible impact on their end-to-end performance. Reading list: Textbooks: - Pierce, Benjamin. Types and Programming Languages. - Winskel, Glynn. The Formal Semantics of Programming Langauges. (Chapters 1 - 6). Formal methods papers: - S. Ishtiaq, P. O'Hearn. BI as an Assertion Language for Mutable Data Structures. In POPL, 2001. - P. O'Hearn, H. Yang, J. Reynolds. Separation and Information Hiding. In POPL, 2004. - S. K. Lahiri, S. Qadeer, D. Walker. Linear Maps. In PLPV, 2011. - G. Tan. JNI Light: An Operational Model for the Core JNI. In APLAS, 2010. - G. C. Necula, S. McPeak, and W. Weimer. CCured: Type-Safe Retrofitting of Legacy Code. In POPL, 2002. Systems papers: - S. Chen, J. Xu, E. C. Sezer, P. Gauriar, and R. K. Iyer. Noncontrol-data attacks are realistic threats. In Usenix Security (SSYM), 2005. - R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in C programs. In AADEBUG, 1997. - S. Nagarakatte, J. Zhao, M. M. K. Martin, and S. Zdancewic. SoftBound: Highly compatible and complete spatial memory safety for C. In PLDI, 2009. - E. D. Berger, T. Yang, and G. Novark. Grace: Safe multithreaded programming for C/C++. In OOPSLA, 2009. - R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham. Efficient software-based fault isolation. In SOSP, pages 203 - 216, 1993.

1 0

P Gopalan general exam
by Melissa Lawson 27 Apr '11

27 Apr '11

Prem Gopalan will present his research seminar/general exam on Wednesday May 4 at 9:30 AM in Room 302. The members of his committee are: Mike 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 Historically, Internet services provided clients with access to the resources of a particular host. However, today's services are no longer defined by a single host or confined to a fixed location. Yet, the network architecture continues to impose a coupling between hosts and services by binding connections to topology-dependent addresses, rather than topology-independent service names -- complicating everything from server replication, load balancing, and virtual-machine migration, to client mobility and multi-homing. We propose a new service access layer that redefines the interaction between the network and transport layers. This layer provides the "thin waist" needed to enable direct communication on service names, decouple service connections from network identifiers, and enhance the network's awareness of service availability. In this talk, we focus on how to rearchitect today's end-host network stack to include the service access layer while maintaining backwards compatibility with today's IP networks and requiring minimal changes to applications. We present the design of transport protocols running in this framework, and evaluate our Linux implementation. Reading list Books Andrew S. Tanenbaum. Computer Networks. Prentice Hall; 4th edition. Papers [1] H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica, and M. Walfish. A layered naming architecture for the internet. In ACM SIGCOMM '04, pages 343-352, New York, NY, USA, 2004. [2] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica. A data-oriented (and beyond) network architecture. In ACM SIGCOMM '07, pages 181-192, New York, NY, USA, 2007. [3] E. Kohler, M. Handley, and S. Floyd. Designing DCCP: congestion control without reliability. In SIGCOMM '06, pages 27-38, New York, NY, USA, 2006. [4] Gregory R. Ganger, Dawson R. Engler, M. Frans Kaashoek, Hector M. Briceno, Russell Hunt, and Thomas Pinckney. Fast and flexible Application-Level Networking on Exokernel Systems. In ACM Transactions on Computer Systems 20(1), February 2002, pages 49-83. [5] Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. The Click modular router. ACM Transactions on Computer Systems 18(3), August 2000, pages 263-297. [6] Raiciu, Costin and Pluntke, Christopher and Barre, Sebastien and Greenhalgh, Adam and Wischik, Damon and Handley, Mark. Data center networking with multipath TCP. In Hotnets '10: Proceedings of the Ninth ACM SIGCOMM Workshop on Hot Topics in Networks, pages 10:1-10:6, 2010. [7] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. Vl2: a scalable and flexible data center network. In SIGCOMM '09, pages 51-62, New York, NY, USA, 2009. [8] R. Niranjan Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, and A. Vahdat. Portland: a scalable fault-tolerant layer 2 data center network fabric. In SIGCOMM '09, pages 39-50, New York, NY, USA, 2009. ACM. [9] A.C. Snoeren, H.Balakrishnan. An End-to-End Approach to Host Mobility. In MobiCom, 2000. [10] B. Ford, J. Iyengar. Breaking Up the Transport Logjam, Bryan Ford and Janardhan Iyengar. In HotNets, 2008.

1 0