- talks - lists.cs.princeton.edu

Ohad Fried presents Generals Thursday, May 15, 2014 at 3pm in Rm. 402
by Nicki Gotsis 08 May '14

08 May '14

Ohad Fried will present his General Exam on Thursday, May 15, 2014 at 3pm in Rm. 402. The members of his/her committee are Adam Finkelstein (advisor), Szymon Rusinkiewicz, Jianxiong Xiao. 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: --------- Collections of objects such as images are often presented visually in a grid because it is a compact representation that lends itself well for search and exploration. Most grid layouts are sorted using very basic criteria, such as date or filename. We present a method to arrange collections of objects respecting an arbitrary distance measure. Pairwise distances are preserved as much as possible, while still producing the specific target arrangement which may be a 2D grid, the surface of a sphere, a hierarchy, or any other shape. We show that our method can be used for infographics, collection exploration, summarization, data visualization, and sound exploration. We present a fast algorithm that can work on large collections and quantitatively evaluate how well distances are preserved. Reading List: ------------- Book: Computer Graphics with OpenGL, 4th Ed., Hearn, Baker, and Carithers. Prentice Hall, 2010. ISBN: 978-0136053583. Papers: TENENBAUM, J. B., DE SILVA, V., AND LANGFORD, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science (New York, N.Y.) 290, 5500 (Dec.), 2319–23. ROWEIS, S. T., AND SAUL, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500 (Dec.), 2323–6. XING, E. P., NG, A. Y., JORDAN, M. I., AND RUSSELL, S. 2003. Distance metric learning, with application to clustering with side-information. Advances in Neural Information Processing Systems 15, 505–512. QUADRIANTO, N., SMOLA, A. J., SONG, L., AND TUYTELAARS, T. 2010. Kernelized sorting. Transactions on Pattern Analysis and Machine Intelligence 32, 10 (Oct.), 1809–21. KUHN, H. 1955. The Hungarian Method for The Assignment Problem. Naval research logistics quarterly 2, 83–87. HUANG, S.-S., SHAMIR, A., SHEN, C.-H., ZHANG, H., SHEFFER, A., HU, S.-M., AND COHEN-OR, D. 2013. Qualitative organization of collections of shapes via quartet analysis. ACM Transactions on Graphics, 32(4). PLANT, W., AND SCHAEFER, G. 2010. Image Retrieval On The Honeycomb Image Browser. 17th IEEE International Conference on Image Processing (ICIP). SCHOEFFMANN, K., AND AHLSTROM, D. 2011. Similarity-Based Visualization for Image Browsing Revisited. International Symposium on Multimedia (Dec.), 422–427. TZANETAKIS, G., BENNING, M. S., NESS, S. R., MINIFIE, D., AND LIVINGSTON, N. 2009. Assistive music browsing using self-organizing maps. Proceedings of the 2nd International Conference on Pervasive Technologies Related to Assistive Environments - PETRA ’09, 1–7.

1 0

Yingfei Wang Generals: Thursday, May 15, 2014 at 1pm in Room 402
by Nicki Gotsis 08 May '14

08 May '14

Yingfei Wang will present the general exam on Thursday, May 15, 2014 at 1pm in Room 402 . Yingfei Wang's committee members are Warren Powell, Robert Schapire and David Blei. Everyone is invited to attend the talk and those faculty wishing to remain for the oral exam following are welcome to do so. Yingfei's abstract and reading list follow below: Abstract： We consider theoretical analysis, algorithm development and real world applications on optimizing sequential design-of-experiments problems. One goal can be to find the alternative with the best underlying average performance within a limited measurement budget, which is often addressed in online Bayesian Ranking and Selection Problems. We derived the first finite-time bound of the knowledge-gradient policy for ranking and selection problems under the condition that the value of information is submodular. We build a new, public-domain, Matlab-based testing environment for comparing a number of policies on a wide range of learning problems, providing the most comprehensive testbed that has yet appeared in the literature. We then consider decision making problems, motivated by applications in experimental science, in which the learner has the ability to repeatedly select a batch, that is, a multi-set of size B over M possible alternatives or a nested batch with the B alternatives sharing the same values of several controllable parameters, and then receives the payoffs for just the selected alternatives. The goal is to find out the one set of tunable control parameters that maximizes some utility function. We extend the sequential ranking and selection problem into a general framework for batch-mode learning and nested-batch-mode learning. By formulating the problem within a dynamic programming framework, we derive the Knowledge-Gradient variants to tackle both batch and nested-batch measurements. A Monte Carlo sampling procedure is applied to tackle intractable expectations computation. Readings: Stuart Russell and Peter Norvig, Artificial intelligence: a modern approach (Chapters 3, 4.1, 5, 7, 13-15, 17-18, 21), Sebastien Bubeck and Nicolo Cesa-bianchi, Regret Analysis of Stochastic and Non-stochastoc Multi-armed Bandit Problems (Chapters 1-5). Robert Schapire’s lecture notes for the course Theoretical Machine Learning. http://www.cs.princeton.edu/courses/archive/spring13/cos511/index.html John Gittins, Kevin Glazebrook, and Richard Weber, Multi-armed Bandit Allocation Indices end Edition (Chapter 2). Ilya Ryzhov, Warren Powell, and Peter Frazier, The knowledge gradient algorithm for a general class of online learning problems. Operations Research, 2012, 60(1): 180-195. Martijn Mes, Warren Powell, and Peter Frazier, Hierarchical knowledge gradient for sequential sampling. The Journal of Machine Learning Research, 2011, 12: 2931-2974. Peter Frazier, and Warren Powell, Consistency of sequential Bayesian sampling policies. SIAM Journal on Control and Optimization, 2011, 49(2): 712-731. Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer, Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002, 47(2-3): 235-256. Daniel Golovin and Andreas Krause, Adaptive submodularity: A new approach to active learning and stochastic optimization. COLT. 2010: 333-345. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The non-stochastic multi-armed bandit problem. SIAM Journal on Computing, 2002, 32(1): 48-77.

1 0

Linpeng Tang: General Exam Monday, May 12, 2014 at 10am in Room 402
by Nicki Gotsis 06 May '14

06 May '14

Linpeng Tang will present the General Exam on Monday, May 12, 2014 at 10am in Room 402. The members of Linpeng's committee are Kai Li, Mike Freedman and Vivek Pai. Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Linpeng's abstract and reading list follow below. Abstract An effective approach to improve the throughput of a static content delivery system, such as the Facebook’s photo-serving stack, is to build read-only storage caches on flash devices because they provide much higher random read throughput than disk drives and much larger capacity than DRAM. The key design challenge for these flash-based static content caches is that advanced caching algorithms generate many small random writes, even though all requests are reads, and the Flash Translation Layer on flash devices performs poorly with random writes, lowering throughput and decreasing device life- time. Coping strategies include under-utilizing the space on the device, which yields a smaller cache, or only using simple caching algorithms like FIFO, which yields lower hit ratios and decreases the utility of the cache. In this paper, we propose the novel RIPQ (Restricted Insertion Priority Queue) framework that solves this dilemma, allowing advanced caching algorithms with large cache sizes, high throughput, and long de- vice lifetime. RIPQ maintains an approximate priority queue efficiently on flash by aggregating small random writes into large writes to a restricted set of insertion points, lazily moving items, and co-locating items with similar priorities. We show that two families of advanced caching algorithms, Segmented-LRU and GDSF (Greedy-Dual-Size-Frequency), can be easily implemented with RIPQ. Our evaluation results on traces from Facebook’s photo-serving stack show that GDSF algorithms with RIPQ can improve cache hit ratios by ~20% over the current production system. Reading List Papers Beaver, Doug, et al. "Finding a Needle in Haystack: Facebook's Photo Storage." OSDI. Vol. 2010. 2010. Huang, Qi, et al. "An analysis of Facebook photo caching." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM, 2013. Zhou, Yuanyuan, James Philbin, and Kai Li. "The Multi-Queue Replacement Algorithm for Second Level Buffer Caches." USENIX Annual Technical Conference, General Track. 2001. Min, Changwoo, et al. "SFS: Random write considered harmful in solid state drives." Proc. of the 10th USENIX Conf. on File and Storage Tech. 2012. Badam, Anirudh, et al. "HashCache: Cache Storage for the Next Billion." NSDI. Vol. 9. 2009. Lim, Hyeontaek, et al. "SILT: A memory-efficient, high-performance key-value store." Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011. Lee, Sang-Won, et al. "A log buffer-based flash translation layer using fully-associative sector translation." ACM Transactions on Embedded Computing Systems (TECS) 6.3 (2007): 18. Breslau, Lee, et al. "Web caching and Zipf-like distributions: Evidence and implications." INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 1. IEEE, 1999. Rosenblum, Mendel, and John K. Ousterhout. "The design and implementation of a log-structured file system." ACM Transactions on Computer Systems (TOCS) 10.1 (1992): 26-52. Cao, Pei, and Sandy Irani. "Cost-Aware WWW Proxy Caching Algorithms."Usenix symposium on internet technologies and systems. Vol. 12. No. 97. 1997. Book Tanenbaum, Andrew S. Modern operating systems. Prentice Hall Press, 2007. Chapter 2 Processes and Threads Chapter 3 Memory Management Chapter 4 File Systems Chapter 5 Input/Output

1 0

Sharva Pathak General Exam: Monday, May 12th, 2014 at 2pm in Room 402 (RESCHEDULED)
by Nicki Gotsis 05 May '14

05 May '14

Sharva Pathak's general exam has been RESCHEDULED to Monday, May 12th, 2014 at 2pm in Room 402. Committee members: Vivek Pai (advisor), Kai Li, Mike Freedman Everyone is invited to the 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: While many applications may benefit from better control over the network stack, existing options, such as developing a new protocol, changing the kernel, or customizing a user-level TCP stack, are unattractive for many domains. We introduce ModNet, a system to allow modular customization of the networking stack, enabling the development of per-application and per-service behaviors with low developer effort and low system overhead. ModNet introduces a small amount of mechanism into the existing networking stack: enabling interposition, exposing finer-grained network processing status and allowing manipulation of socket buffer content. We demonstrate ModNet’s utility across a range of tasks that exercise fine-grained customization of different parts of the network stack’s behavior. In response to changing connection bandwidth, ModNet modules can adaptively compress data and images. Fine control over network socket buffers allows selective swapping of network data to SSDs, enabling resource-heavy dynamically-generated content applications to handle more throughput. Likewise, manipulating socket buffer content allows video applications to adapt bitrate at a finer granularity with server-side cooperation, reducing rebuffering times and improving playback over purely client-side approaches. All of these modules can operate at scale, often providing gigabits per second of throughput with low performance overheads. Reading list: Books: " Modern Operating Systems", Andrew S. Tanenbaum " Computer Networks : A Systems Approach", Larry L. Peterson and Bruce S. Davie. Papers: "Mach: A New Kernel Foundation For UNIX Development", Mike Accetta, Robert Baron, William Bolosky, David Golub, Richard Rashid, Avadis Tevanian and Michael Young. In Usenix Summer Conference, 1986. "Exokernel: An Operating System Architecture for Application-Level Resource Management", Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr. In SOSP '95. "The Packet Filter: An Efficient Mechanism for User-level Network Code", Jeffrey C. Mogul. In SOSP '87. "Kqueue: A generic and scalable event notification facility", Jonathan Lemon. In Usenix ATC '01. "Flash: An Efficient and Portable Web Server", Vivek S. Pai, Peter Druschel, and Willy Zwaenepoel. In Usenix ATC '99. "Implementing Network Protocols at User Level.", Chadramohan A. Thekkath, Thu D. Nguyen, Evelyn Moy and Edward D. Lazowska. In ACM Transactions on Networking '93. "Connection Conditioning: Architecture-Independent Support for Simple, Robust Servers", KyoungSoo Park and Vivek S. Pai. In NSDI '06. "Netmap: a novel framework for fast packet I/O", Luigi Rizzo. In Usenix ATC '12. "MegaPipe: A New Programming Interface for Scalable Network I/O", Sangjin Han, Scott Marshall, Byung-Gon Chun and Sylvia Ratnasamy. In OSDI '12. "A toolkit for user-level file systems", David Mazières. In Usenix ATC '01.

1 0

David Shue FPO Monday, May 12, 2014 at 1pm in 402 Computer Science
by Nicki Gotsis 05 May '14

05 May '14

David Shue will present his FPO on Monday, May 12, 2014 at 1pm in 402 Computer Science. The members of his committee are Michael Freedman, advisor; Jennifer Rexford and Anees Shaikh (Google), readers; and Vivek Pai and Margaret Martonosi, nonreaders. A copy of his thesis, "Multi-tenant Resource Allocation For Shared Cloud Storage" is available in room 310. Everyone is invited to attend his talk. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609) 258-5387 ngotsis(a)cs.princeton.edu

1 0

Speaker: Thomas Dreibholz, Thursday May 8 at 3pm in 301
by Andy Bavier 05 May '14

05 May '14

Everyone is invited to attend this talk. Thomas Dreibholz (Simula Research Laboratory) Thursday, May 8, 3pm Computer Science 301 The NorNet Testbed for Multi-Homed Systems -- Introduction and Status Multi-homing denotes the simultaneous connection of endpoints to multiple Internet Service Providers (ISP). That is, such endpoints should remain reachable even when some of the ISPs have problems. Besides the redundancy aspect, multi-homing can also make load sharing by multi-path transport possible, i.e. increasing the application throughput by utilizing multiple paths simultaneously. The growing need for and deployment of multi-homed applications makes large-scale testing and evaluation in realistic Internet setups necessary. For instance, different paths can have very different characteristics with regard to bandwidth, packet loss rate, congestion, delay and jitter. Therefore, the Simula Research Laboratory is building up the NorNet testbed, which is an open platform for such experiments. NorNet consists of two parts, the wireless part NorNet Edge as well as the wired part NorNet Core, providing researchers the possibility to use programmable, multi-homed nodes at different locations in Norway as well as at some international sites. This talk gives an overview over the NorNet testbed, with a special focus on the usage of the PlanetLab/Linux Containers-based software that is used to run NorNet Core. NorNet homepage: https://www.nntb.no

1 0

Scott Erickson will present his MSE thesis talk on Thursday, May 8th, 2014 at 1:30pm in room 302
by Nicki Gotsis 05 May '14

05 May '14

Scott Erickson will present his MSE thesis talk on Thursday, May 8th, 2014 at 1:30pm in room 302 of the Computer Science Building. His committee is: Michael Freedman, adviser and Vivek Pai as reader. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Abstract: There are an increasing number of users consuming more and more data through mobile apps on their carrier’s metered 3G and 4G connections. However, a certain percentage of this traffic is duplicated, and is thus wasteful. If this duplicated data were to be eliminated, consumers could use their data connections more comfortably while lightening the load on the network. This work presents a system that deduplicates HTTP traffic, and experimentally evaluates its performance. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609) 258-5387 ngotsis(a)cs.princeton.edu

1 0

Gordon Stewart: Pre-FPO talk announcement (5/12 at 9:30 in Room 302)
by Nicki Gotsis 05 May '14

05 May '14

Gordon Stewart will present his Pre-FPO on Monday, May 12 at 9:30am in Room 302 in the Computer Science Building. The members of his committee are: Andrew Appel (advisor); Zhong Shao and David Walker (readers); David August and Sharad Malik (nonreaders). Everyone is invited to attend his talk. The talk title and abstract follow below: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Title: Verified Separate Compilation for C ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Verified separate compilation is the process of independently translating a program's components in a way that preserves correctness of the program as a whole. In the most general case, a verified separate compiler supports heterogeneous source programs, in which some modules are in C or another high-level language while others are written in a lower-level language like x86 assembly, as is common in systems software such as operating systems. A verified separate compiler in this context is one that preserves the behavior of the entire source program, comprising the C and x86 modules, when the C code is compiled to assembly. Separate compilation has numerous practical benefits. It speeds up development cycles by enabling re-compilation of just those source modules that have been edited by the programmer. It enables shared libraries---separately compiled modules mapped at runtime into the virtual address spaces of multiple processes. It promotes modularity in the large, by enabling programmers to write applications containing logically distinct translation units, each composed at a different level of abstraction or even in a different programming language altogether. But perhaps equally important are applications of verified separate compilers to /modular verification/, the act of reasoning independently about each module in a program (with respect to specifications of the other modules) in order to prove whole program correctness. A modular verification approach means the programmer can break the task of proving correctness of large programs into smaller, more manageable steps: First provide specifications of the modules that form the program, then prove independently of each module that the module meets its specification. When modules proved correct in this way are compiled by a semantics-preserving separate compiler, one gets not only that each module is translated correctly to assembly and then machine code, but also that the target whole program---linked and running on the machine---has the same behavior as the source whole program about which the programmer proved a correctness specification. The result is an end-to-end system: Whole program properties proved modularly at the source level are true also of the whole program that results from separate compilation and linking. In this thesis, I present techniques that address the verified separate compilation problem in the context of C-like languages. My work extends state-of-the-art verified compilers for C such as CompCert (http://compcert.inria.fr/)---the correctness proof of which is currently limited to whole programs---to support verified separate compilation. Major results of the thesis are the proof of a separate compilation theorem for C and the novel semantics of inter-language linking on which the statement of the separate compilation theorem depends. I also address applications to verified compilation of coarse-grained concurrent programs, revealing surprising connections between separate compilation and concurrency in the process. To validate the separate compilation result, I show that it supports modular verification of source programs in the Verified Software Toolchain program logic for C (http://vst.cs.princeton.edu/).

1 0

Adrian Soviani's FPO has been rescheduled to 12pm on Friday May 2
by Joseph Crouthamel 02 May '14

02 May '14

Adrian Soviani's FPO has been rescheduled to 12pm on Friday May 2 in Room 402. The members of his committee are: JP Singh, advisor; Kai Li and David August, readers; Brian Kernighan and Andrea LaPaugh, nonreaders. A copy of his thesis, "A Hybrid SPMD - Coarse Grain Dataflow Parallel Programming Model" is available in Room 310. Everyone is invited to attend his talk. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609)258-5387 ngotsis(a)cs.princeton.edu

2 1

B Hristov general exam
by Melissa M. Lawson 29 Apr '14

29 Apr '14

Borislav Hristov will present his research seminar/general exam on Tuesday May 6 at 10AM in Room 402. The members of his committee are: Mona Singh (advisor), Olga Troyanskaya, 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. ----- Original Message ----- Abstract: The improvement and the decreased cost of next generation DNA sequencing have enabled genome wide measurements in large numbers of individuals. This allows researchers to compare the genome variations in both healthy and sick individuals in order to help uncover the genetic underpinnings of human disease. However, complex diseases are caused by a combination of genetic perturbations- often the same phenotypic outcome (a disease case) can result from a different set of possible mutations, possibly in different loci. Cancer is a disease which exhibits such a great genetic heterogeneity. This makes studying it and identifying causal variants extremely difficult. We combine knowledge of biological interactions with genome sequencing data from The Cancer Genome Atlas to perform an integrated analysis of several types of cancer. Our hypothesis is that even though different patients could have entirely disjoint sets of somatic variants, these variants disturb similar cell processes and hence are closely connected in the biological network. We phrase the problem precisely in mathematical terms and devise an efficient greedy heuristic to solve it. We use a robust framework of cross validation tests to demonstrate the soundness of our approach. We are able to recover well known cancer genes as well as to highlight possible new ones. We show that our method yields both efficient and biologically relevant results. Reading List: Yona, Golan. Introduction to Computational Proteomics . CRC Press, 2011. Chapters: 1-7, 10, 13.2 Dand, Nick, et al. "BioGranat-IG: a network analysis tool to suggest mechanisms of genetic heterogeneity from exome-sequencing data." Bioinformatics 29.6 (2013): 733-741. Vandin, Fabio, Eli Upfal, and Benjamin J. Raphael. "Algorithms for detecting significantly mutated pathways in cancer." Journal of Computational Biology 18.3 (2011): 507-522. Ulitsky, Igor, et al. "DEGAS: de novo discovery of dysregulated pathways in human diseases." PLoS One 5.10 (2010): e13367. Navlakha, Saket, and Carl Kingsford. "The power of protein interaction networks for associating genes with diseases." Bioinformatics 26.8 (2010): 1057-1063. Wang, Peggy I., and Edward M. Marcotte. "It's the machine that matters: Predicting gene function and phenotype from protein networks." Journal of proteomics 73.11 (2010): 2277-2289. Gosline, Sara JC, et al. "SAMNet: a network-based approach to integrate multi-dimensional high throughput datasets." Integrative Biology 4.11 (2012): 1415-1427. Lee, Insuk, et al. "Prioritizing candidate disease genes by network-based boosting of genome-wide association data." Genome research 21.7 (2011): 1109-1121. Hofree, Matan, et al. "Network-based stratification of tumor mutations." Nature methods (2013). Jiang, Peng, and Mona Singh. "SPICi: a fast clustering algorithm for large biological networks." Bioinformatics 26.8 (2010): 1105-1111.

1 0