- talks - lists.cs.princeton.edu

B Kapicioglu preFPO
by Melissa M. Lawson 16 Feb '12

16 Feb '12

Berk Kapicioglu will present his preFPO on Wednesday February 22 at 11AM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Tony Jebara (Columbia), readers; Jennifer Rexford and Andrea LaPaugh, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Applications of Machine Learning to Location Data. Abstract: First, we introduce a new graphical model for tracking radio-tagged animals and learning their movement patterns. The model provides a principled way to combine radio telemetry data with an arbitrary set of user-deﬁned, spatial features. We describe an efﬁcient stochastic gradient algorithm for ﬁtting model parameters to data and demonstrate its eﬀectiveness via asymptotic analysis and synthetic experiments. We also apply our model to real datasets, and show that it outperforms the most popular radio telemetry software package used in ecology. We conclude that integration of different data sources under a single statistical framework, coupled with appropriate parameter and state estimation procedures, produces both accurate location estimates and an interpretable statistical model of animal movement. Second, we present the “Place Discovery” problem, where the goal is to provide a context-dependent and personalized ranking of nearby places. To the best of our knowledge, we are the first to pose this as a machine learning problem. We provide a new matrix approximation algorithm that leverages implicit bipartite ranking and spatial constraints. We demonstrate on real location datasets that our methods significantly improve on the amount of personalization achieved by state-of-the-art matrix approximation methods, such as Maximum-Margin Matrix Factorization. Lastly, we talk about “Location Prediction”. Here, the goal is to predict the coordinates (i.e. latitude and longitude) of a user at an arbitrary time in the future. We design an unsupervised hierarchical Bayesian graphical model for location prediction that learns natural topics such as home and work from unlabeled location data. We apply our model both to data gathered from mobile applications, where there are many users but each user has sparse location points, and to data gathered from cellular carriers. Our model outperforms existing methods in both cases.

1 0

P Jiang preFPO
by Melissa M. Lawson 13 Feb '12

13 Feb '12

Peng Jiang will present his preFPO on Friday February 17 at Noon in Lewis Thomas Lab 118 (note location). The members of his committee are: Mona Singh, advisor; Hilary Coller (MOL) and Olga Troyanskaya, readers; Leonid Kruuglyak (Genomics) and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Computational Analysis of Transcriptional and post-Transcriptional regulation Abstract: Transcription factors (TFs) and miRNAs are regulators for a wide range of biological processes. While binding speciﬁcities for numerous D. melanogaster TFs have been experimentally determined, the genomic binding targets for the majority of them are unknown, with even less known about the transcriptional regulators of miRNAs and the network-level interplay between TFs and miRNAs. We computationally constructed a large-scale transcriptional regulatory network for D. melanogaster. Based on several lines of experimental data, we annotated the transcription start sites for 37 integenic miRNAs. We uncovered conserved binding sites for TFs with known speciﬁcities in promoters of miRNAs and protein-coding genes. The inferred D. melanogaster transcriptional network is the largest to date, and consists of regulatory targets for 267 TFs, covering 56 intergenic miRNA loci and 11,232 protein-coding genes. Using this network, we predicted GO biological processes for miRNAs based upon their upstream regulators and downstream targets. Finally, we found that the network exhibits a surprisingly diverse array of network motifs consisting of both miRNAs and TFs. On the level of post-Transcriptional regulation, transcript degradation is a widespread and important mechanism for regulating protein abundance. Two major regulators of transcript degradation are RNA Binding Proteins (RBPs) and microRNAs (miRNAs). We computationally explored whether RBPs and miRNAs cooperate to promote transcript decay. We defined five RBP motifs based on the evolutionary conservation of their recognition sites in 3' UTRs as the binding motifs for Pumilio (PUM), U1A, Fox-1, Nova, and AU-rich element (ARE) binding proteins. Recognition sites for some of these RBPs tended to localize at the beginning or end of 3' UTRs. A specific group of miRNA recognition sites were enriched within 50 nts upstream and downstream of the RBP recognition sites of PUM, ARE, Fox-1 and U1A. The presence of both a PUM recognition site and a recognition site for preferentially co-occurring miRNAs was associated with faster decay of the associated transcripts. For PUM and its co-occurring miRNAs, binding of the RBP to its recognition sites was predicted to rescue nucleotides within nearby miRNA recognition sites from hybridization with other nucleotides at a higher rate than expected. miRNAs that preferentially co-occur with PUM binding sites tended to have recognition sites that are reverse complements to the PUM recognition motif. These sites have the potential to form hairpin secondary structures that would normally limit RISC accessibility, but would be more accessible to miRNAs in response to the binding of PUM. In sum, our computational analyses suggest that PUM can coordinately fine-tune the accessibility of multiple microRNA recognition sites.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 07 Feb '12

07 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems. Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression. Bio: Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

1 0

W Jiang FPO
by Melissa M. Lawson 06 Feb '12

06 Feb '12

Joe Wenjie Jiang will present his FPO on thursday February 9 at 1:15PM in Room 402. The members of his committee are: Jennifer Rexford, advisor. Mung Chiang co-advisor; Andrea LaPaugh and Augustin Chaintreau (Columbia) readers; Michael Freedman and Mung Chiang, nonreaders. A copy of his thesis, "Wide-Area Traffic Management for Cloud Services", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Colloquium speaker Tim Roughgarden Wed Feb 8, 4:30pm
by Nicole E. Wagenblast 03 Feb '12

03 Feb '12

Porting the Computer Science Toolbox to Game Theory and Economics Tim Roughgarden , Stanford University Wednesday, February 8, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Theoretical computer science has brought new ideas and techniques to game and economic theory. A primary signature of the computer science approach is {em approximation} --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. We explain two of our recent contributions in this area, one motivated by networks and one by auctions. We first discuss the "price of anarchy": how well does decentralized (or "selfish") behavior approximates centralized optimization? This concept has been analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. We highlight a new theory of robust price of anarchy bounds, which apply even to systems that are not in equilibrium. Second, we consider auction design: for example, what selling procedure should be used to maximize the revenue of a seller? On the analysis side, we highlight a new framework that explicitly connects average-case (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worst-case analysis approach common in computer science. On the design side, we provide a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the distribution-specific optimal auction. Tim Roughgarden received his Ph.D. from Cornell University in 2002 and joined the Stanford CS department in 2004, where he is currently an associate professor. His research interests are in theoretical computer science, especially its interfaces with game theory and networks. He wrote the book "Selfish Routing and the Price of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007). His significant awards include the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003 Tucker Prize, the 2003 INFORMS Optimization Prize for Young Researchers, speaking at the 2006 International Congress of Mathematicians, a 2007 PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society, and the 2009 ACM Grace Murray Hopper Award. He's currently developing a free online course on the design and analysis of algorithms, which has over 50,000 students.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 01 Feb '12

01 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems. Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression. Bio: Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

1 0

11am Wed Jan 18 talk on information-centric networking
by Jennifer Rexford 14 Jan '12

14 Jan '12

Speaker: Yan Shvartzshnaider, NICTA Title: A Case for a Global Information Network Date/time: 11am-noon Wed Jan 18 Location: CS 302 Abstract There is an ever increasing gap between how the “common man” would describe the Internet and how a network researcher would. This is not surprising, as the “packet with a label identifying the receiver” model seems to be an ill fitting abstraction for popular services provided by companies such as Google, Facebook, YouTube, or Twitter. These services are primarily about information dissemination and a suitable network service abstraction should really do more than deliver individual packets with minimal latency. We argue that we should adopt an information-centric system model instead of the current service oriented one. Instead of dealing with information exchange between specific services on a case by case bases, we should instead consider a global information storage and dissemination network on which individual applications and services are built. In this talk I will discuss our vision the future architecture and give a brief overview on our progress so far. Bio: Yan Shvartzshnaider is a PhD Candidate in the school of Engineering and Information Technologies in the University of Sydney and a graduate researcher in National ICT Australia (NICTA), Networking Group in ATP lab. His research focus is on large scale networking systems, in particular, developing a fully distributed information-centric networking abstraction.

1 0

S Narayana general exam
by Melissa M. Lawson 12 Jan '12

12 Jan '12

Srinivas Narayana will present his research seminar/general exam on Thursday Jan 19 at 10AM in Room 402. The members of his committee are: Jen Rexford (advisor), Mung Chiang, and Moses Charikar. 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: The end-to-end performance of user-facing online services (e.g., Facebook, Amazon) is critical to their operation, as small increases in user-perceived latencies can have significant impact on revenue. Such services typically run out of a number of geographically distributed data centers, each connected by multiple ISPs to the Internet, and a geographically distributed set of mapping nodes directing user requests to data centers (e.g., based on proximity). Together, request-mapping (i.e., assigning user requests to data centers) and response-routing decisions (i.e., choosing an ISP to send responses) determine the wide-area paths traversed by user traffic--which are a significant contributor to end-to-end service latency. Yet in today's systems, request-mapping and response-routing decisions are made almost independently with coarse-grained, if any, coordination--due to concerns of administrative separation and operational scale. In this work, we investigate the benefits of coordinating request-mapping and response-routing decisions, through an optimization framework. We identify how suboptimal performance or costs can result if (1) the mapping and routing systems have incompatible objectives, or (2) if they are not sharing their decisions, and even if (3) mapping and routing systems have compatible objectives, share decisions, and optimize on top of each other. To overcome these difficulties, we show how to perform jointly optimized mapping and routing decisions while retaining their administrative separation. In particular, we construct a provably optimal distributed algorithm implemented through local computations at mapping nodes and data center edge routers, with a lightweight exchange of decisions. Evaluations of our solution using traffic traces from an operational content distribution network shows that our system converges quickly in practice, and offers much better performance and lower costs than today's solutions. and reading list: (1) The Design Philosophy of the DARPA Internet Protocols D. D. Clark (2) End-to-end arguments in system design J.H. Saltzer, D.P. Reed and D.D. Clark (3) DONAR: Decentralized server selection for cloud services P. Wendell, J. W. Jiang, M. J. Freedman, and J. Rexford (4) Characterizing roles of front-end servers in end-to-end performance of dynamic content distribution Y. Chen, S. Jain, V. K. Adhikari, and Z. L. Zhang (5) Optimizing cost and performance for multi-homing D. K. Goldenberg, L. Qiu, H. Xie, Y. R. Yang, and Y. Zhang (6) Optimizing cost and performance in online service provider networks Z. Zhang, M. Zhang, A. Greenberg, Y. C. Hu, R. Mahajan, and B. Christian (7) Cooperative content distribution and traffic engineering in an ISP network J. W. Jiang, R. Zhang-Shen, J. Rexford and M. Chiang (8) Traffic engineering vs. Content distribution: A game theoretic perspective D. DiPalantino and R. Johari (9) A Tutorial on Decomposition Methods for Network Utility Maximization D. P. Palomar and M. Chiang (10) Democratizing content publication with Coral M. J. Freedman, E. Freudenthal and D. Mazieres (11) iPlane: An information plane for distributed services H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy and A. Venkataramani (12) Computer networks: a systems approach Larry L. Peterson and Bruce S. Davie

1 0

J Dodds general exam
by Melissa M. Lawson 11 Jan '12

11 Jan '12

Joey Dodds will present his research seminar/general exam on Tuesday January 17 at 1PM in Room 402. The members of his committee are: Andrew Appel (advisor), David Walker, and Zeev Dvir. Everyone is invited to attend his talk and those faculty members wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------ Title: Machine-Checked Proofs of Conditional Information Flow Abstract: Previous work proposed a compositional framework for stating and automatically verifying complex conditional information flow policies using a relational Hoare logic. The framework allows developers and verifiers to work directly with the source code using source-level code contracts. In this work, we extend that approach so that the algorithm for verifying code compliance to an information flow contract emits formal certificates of correctness that are checked in the Coq proof assistant. This framework is implemented in the context of SPARK -- a subset of Ada that has been used in a number of industrial contexts for implementing certified safety and security critical systems. This work puts in place a crucial element of our larger vision for end-to-end security assurance -- namely, the ability to leverage a formally verified compiler to provide a tool chain that enables us to prove that deployed executable code conforms to complex information flow policies stated as source-level contracts. The Coq code consists of a definition for the core SPARK language, operational semantics for the language, definitions for the form of certificates, and soundness proofs of the certificates with respect to the operational semantics. We will discuss these definitions and proofs, along with the challenges of formalizing a paper proof. Certificates for analyses such as ours can often blow up to an unmanageable size. We have taken steps towards mitigating this contract explosion including beginning an implementation of the analysis in Coq. We can prove that evidence always exists, guaranteeing that any precondition generated by the function is correct with respect to the operational semantics of the language without requiring the transmission of a large contract. Text books: A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 * B. Pierce. Types and Programming Languages. 2002. Papers * A. W. Appel. VeriSmall: Veriﬁed Smallfoot Shape Analysis. In First International Conf. on Certiﬁed Programs and Proofs Dec. 2011 * G. Necula. Proof-Carrying Code. In POPL'97: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1997. * T. Amtoft, S. Bandhakavi, and A. Banerjee. A logic for information flow in object-oriented programs. In POPL 2006. ACM Press, 2006. * T. Amtoft, J. Hatcliff, and E. Rodrıguez. Precise and automated contract-based reasoning for verification and certification of information flow properties -of programs with arrays. In ESOP’10, volume 6012 of LNCS, pages 43–63, March 2010. * X. Leroy. A formally verified compiler back-end. In Journal of Automated Reasoning, 2009 * A. Sabelfeld, A. C. Myers. Language-Based Information-Flow Security. In IEEE Journal on Selected Areas in Communications, 2003 * Boettcher, C., DeLong, R., Rushby, J., and Sifre, W. 2008. The mils component integration approach to secure information sharing. In 27th IEEE/AIAA Digital Avionics Systems Conference 2008.

1 0

Y Wang general exam
by Melissa M. Lawson 06 Jan '12

06 Jan '12

Yida Wang will present his research seminar/general exam on Friday January 13 at 9:30AM in Room 302 (note room). The members of his committee are: Kai Li (advisor), Moses Charikar, and Nicholas Turk-Browne (Psychology, Neuroscience) . Everyone is invited to attend his talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------- Computing and decoding brain full pairwise correlation matrices 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.Realizing that the processes in the brain may depend on widely distributed interactions among regions, we propose a novel method of analyzing the brain by its full correlation structure and show the effectiveness of the correlation analysis. The full correlation matrices lead to dramatic increase of data amount by at most extracting 7 orders of magnitude more information. With careful data computing, allocating and appropriate feature selection, we design a parallel tool to get the full correlation matrices in distribution and analyze them efficiently via classification to show the effectiveness of connectivity analysis. The critical voxels picked by our tool well match the existing theory of cognitive neuroscience in terms of location. And based on the selected voxels, experimental results demonstrate that the correlation based classification gets a comparable accuracy as traditional activation based classification within a subject, and is able to attain substantially higher accuracy than activation when analyzing across subjects, which, for the first time, shows the stability of brain correlation structures among different subjects. 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: Modern Operating Systems, 3rd Edition, Andrew Tanenbaum. 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. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. Technical Report UCB/EECS-2011-82, EECS Department, University of California, Berkeley, Jul 2011. 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). Jacob Y, Rapson A, Kafri M, Baruchi I, Hendler T, Jacob EB. Revealing voxel correlation cliques by functional holography analysis of fMRI. Journal of Neuroscience Methods 2010; 191: 126-137. Smith SM. Overview of fMRI analysis. The British Journal of Radiology, 77 (2004), 167-175. Kriegeskorte N, Goebel R, Bandettini P. Information-based functional brain mapping. Proceedings of the National Academy of Sciences 2006; 103(10): 3863-3868. Haxby JV, Guntupalli JS, Connolly AC, Halchenko YO, Conroy BR, Gobbini MI, Hanke M, Ramadge PJ. A Common, High-Dimensional Model of the Representational Space in Human Ventral Temporal Cortex. Neuron, 72(2), 2011.

1 0