- talks - lists.cs.princeton.edu

Z Khan FPO
by Melissa Lawson 26 Jul '11

26 Jul '11

Zia Khan will present his FPO on Tuesday August 2 at 2PM in Carl Icahn Labs Room 101 (note location!). The members of his committee are: Mona Singh, advisor; Leonid Kruglyak and Benjamin Garcia, readers; Hilary Coller and Saeed Tavazoie, nonreaders. A copy of his thesis, "Efficient Algorithms for Liquid Chromatography Coupled Mass Spectrometry Based Protein Quantification", is on display in Room 310. Everyone is invited to attend his talk.

1 0

11am Mon Jul 11 talk by Robin Kravets (UIUC) on mobility and disconnected networks in CS 402
by Jennifer Rexford 11 Jul '11

11 Jul '11

Speaker: Professor Robin Kravets, UIUC Title: Connecting the Disconnected Date/time: 11am-12pm on Monday July 11 Location: room 402 in the Computer Science building Abstract: Mobility, in all of its forms, results in networks with varying degrees of connectivity. Providing communication services in such networks relies on solutions that treat these disconnections as an expected part of the system, instead of as an exception to be handled out of band. However, handling disconnectivity breaks most architectures for more stable and connected networks. Instead of a standard layered approach to communication services, communication in such intermittently connected networks depends on three key components: contacts, or knowing who we meet, context, knowing what is in our neighborhood, and content, knowing how to find and deliver data. In this talk, I will present some of our current research on support for communication in intermittently connected networks, vehicular networks and mobile social networks, as well as the target applications and deployment testbeds. Bio: Robin Kravets is an Associate Professor at the University of Illinois at Urbana-Champaign and the head of the Mobius group at UIUC, which researches communication issues in all types of networks that are challenged by mobility, including wireless LANs, ad hoc networks, sensor network, delay and disruption tolerant networks, vehicular networks, mobile social networks and personal area networks. Her research focuses on solutions that enable effective power management, connectivity management, data transport, congestion management, location management, routing and security. For more information, visit http://mobius.cs.illinois.edu.

1 1

MohammadHossein Bateni FPO
by Nicole E. Wagenblast 03 Jun '11

03 Jun '11

MohammadHossein Bateni will present his FPO on Thursday June 9 at 1PM in Room 402. The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and MohammadTaghi Hajiaghayi (Maryland), readers; Bernard Chazelle and Rob Schapire, nonreaders. A copy of his thesis, "A Primal-Dual Clustering Technique with Applications in Network Design" is on display in Room 310. Everyone is invited to attend his talk.

1 0

Martin Suchara FPO
by Nicole E. Wagenblast 03 Jun '11

03 Jun '11

Martin Suchara will present his FPO on Wednesday June 15 at 1PM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mung Chiang (ELE) and Gordon Wilfong (Bell Labs), readers; Michael Freedman and Ed Felten, nonreaders. A copy of his thesis, "Reliable Internet Routing" is on display in Room 310. Everyone is invited to attend his talk.

1 0

Z Wang preFPO
by Melissa Lawson 23 May '11

23 May '11

Zhe Wang will present his preFPO on Friday May 27 at 2PM in Room 402. The members of his committee are: Kai Li, advisor; Moses Charikar and Olga Troyanskaya, readers; Jennifer Rexford and Andrea LaPaugh; nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------- Title: Designing similarity search systems for multimodal data As images, videos and all kinds of non-text sensory data have taken the majority of the storage space, how to efficiently index and search them becomes an issue. The query by example kind of content based search method has become more popular and often can be used to compliment the existing search method. We have designed multiple search system to demonstrate the content based search capability and would discuss our experience about building such systems. First we describe VFerret system where we combine the image visual feature with audio features for personal video search. Second, we explore different aggregation methods to aggregate results from multiple features in a system to detect image spam emails. In the last system, we design a new method to combine image similarity search with product navigation to help user to find desired product in the product category tree. One of the common problem for the similarity search system is the space utilization for the feature vectors used to represent objects. Our group had developed sketch as a compact data structure to alleviate such problem. In order to use the sketch effectively, I have worked out a method to model the sketch and predict the best parameters to use given a sample dataset. Our experience in integrating the similarity search capability into different kinds of system show that the content based search can be an effective method to enhance the existing systems. By creatively exploit multiple modality from the data, we demonstrate much better performance than the traditional systems.

1 0

Monday, 11AM: Geoff Hinton on neural networks
by Nicole E. Wagenblast 16 May '11

16 May '11

hi cs faculty and graduate students, geoff hinton from U of T is speaking tomorrow at 11am in the small auditorium. geoff is one of the founders of modern machine learning and artificial intelligence. (and, he's an incredibly witty and engaging speaker.) see the full announcement below. best dave ---------- Forwarded message ---------- From: David Mimno < mimno(a)cs.princeton.edu > Date: Thu, May 12, 2011 at 2:57 PM Subject: [Ml-stat-talks] Monday, 11AM: Geoff Hinton on neural networks To: ml-stat-talks < ml-stat-talks(a)lists.cs.princeton.edu > For those not familiar with his work: "Geoffrey Hinton talks about neural networks" is roughly equivalent to "J.S. Bach talks about fugues". This is not to be missed. Drag your friends. Geoff's schedule is filling up, but if you would like to meet with him before the talk or in the afternoon, please let me know. Monday, May 16, 11AM (note the change), CS105 ============================= How to force unsupervised neural networks to discover the right representation of images Geoffrey Hinton University of Toronto One appealing way to design an object recognition system is to define objects recursively in terms of their parts and the required spatial relationships between the parts and the whole. These relationships can be represented by the coordinate transformation between an intrinsic frame of reference embedded in the part and an intrinsic frame embedded in the whole. This transformation is unaffected by the viewpoint so this form of knowledge about the shape of an object is viewpoint invariant. A natural way for a neural network to implement this knowledge is by using a matrix of weights to represent each part-whole relationship and a vector of neural activities to represent the pose of each part or whole relative to the viewer. The pose of the whole can then be predicted from the poses of the parts and, if the predictions agree, the whole is present. This leads to neural networks that can recognize objects over a wide range of viewpoints using neural activities that are ``equivariant'' rather than invariant: as the viewpoint varies the neural activities all vary even though the knowledge is viewpoint-invariant. The ``capsules'' that implement the lowest-level parts in the shape hierarchy need to extract explicit pose parameters from pixel intensities and these pose parameters need to have the right form to allow coordinate transformations to be implemented by matrix multiplies. These capsules are quite easy to learn from pairs of transformed images if the neural net has direct, non-visual access to the transformations, as it would if it controlled them. (Joint work with Sida Wang and Alex Krizhevsky)

1 0

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