- talks - lists.cs.princeton.edu

S Nadimpalli general exam
by Melissa M. Lawson 03 May '13

03 May '13

Shilpa Nadimpalli will present her research seminar/general exam on Thursday May 9 at 1PM in Room 402. The members of her committee are: Mona Singh, advisor, Olga Troyanskaya, and Kai Li. 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. ------------------ Abstract ======== Gene regulatory networks control where, when, and in what amount genes are expressed. Interestingly, these networks appear to be highly malleable, despite the fact that changes in gene regulation hugely impact organisms' phenotypic characteristics. For instance, gene regulation changes can explain the differentiation between closely-related species, such as humans and chimps, or among subpopulations of the same species. How do regulatory networks change? We explore one hypothesis, that changes can occur in transcription factors (TFs), which bind to DNA to change the expression of groups of genes. We have curated a high-quality dataset of Cys2-His2 zinc finger (ZF) genes, the largest group of TFs in tetrapods, across the 12 sequenced Drosophila species. Somewhat surprisingly, we see evidence of significant change due to transcription factors. Analysis of the DNA-binding ZF domains within these genes reveals patterns of divergence related to phylogeny, gene conservation, domain organization, and gene function. We also show that the ZF domains within these TF genes are functionally important, and that sections of these genes are under positive selective pressure. This suggests that the ZF transcription factors are a source of new regulatory activity in Drosophila. Reading List ========== [1] Jones, NC & Pevsner, PA (2004). "An Introduction to Bioinformatics Algorithms (Computional Molecular Biology). 1st ed. MIT Press, Cambridge, MA. [2] Przytycka, TM, Singh, M, & Slonim, DK (2009). "Toward the dynamic interactome: it's about time." Briefings in Bioinformatics, 2(1): 15-29. [3] Johnson, AD & Li, H (2010). "Evolution of Transcription Networks -- Lessons from Yeast." Current Biology, 20(17): R746-R753. [4] Wagner, GP & Lynch, VJ (2008). "The gene regulatory logic of transcription factor evolution." Trends in Ecology and Evolution, 23: 377-385. [5] Hsia, CC & McGinnis, W (2003). "Evolution of transcription factor function." Current Opinion in Genetics and Development, 13(2): 199-206. [6] Emerson, RO & Thomas, JH (2009). "Adaptive Evolution in Zinc Finger Transcription Factors." PLoS Genetics, 5(1). [7] Singh, LN & Hannenhalli, S (2008). "Functional diversification of paralogous transcription factors via divergence in DNA binding site motif and in expression." PLoS ONE, 3(6): e2345. [8] Persikov, AV, Osada, R, & Singh, M (2009). "Predicting DNA recognition by Cys2-His2 zinc finger proteins." Bioinformatics, 25(1): 22-29. [9] Enuameh, SE et al. (2013). "Global analysis of Drosophila Cys2-His2 zinc finger proteins reveals a multitude of novel recognition motifs and binding determinants." Genome Research. [10] Tadepally, HD, Burger, G, & Aubry, M (2008). "Evolution of C2H2-zinc finger genes and subfamilies in mammals: species-specific duplication and loss of clusters, genes, and effector domains." BMC Evolutionary Biology, 8: 176.

1 0

Sasha Koruga MSE thesis talk
by Melissa M. Lawson 03 May '13

03 May '13

Sasha Koruga will present his MSE thesis talk on Wednesday May 8 at 4PM in room 402. The members of his committee are Olga Troyanskaya (advisor) and Kai Li. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- A biological pathway can be modeled as a network of sparsely connected proteins, where network paths correspond to a sequence of protein-protein interactions leading to higher-level changes within the cells in the human body. A deeper understanding of how proteins interact to carry out biological goals can lead to insights in human disease research and the proposal of new drug targets. However, the number of pathways we currently understand is limited, and these pathways are incomplete. Although experimental evidence for many protein interactions and protein-pathway affiliations exist in research literature, only relatively few have been manually curated. We propose using crowd-sourcing to aggregate published biological research in order to construct new pathways and augment existing ones. We hope to use these pathways to enable accurate prediction of yet more pathway components and drug targets based on functional genomics data. We developed a web application ( http://bioturk.princeton.edu ) where untrained users can answer simple biological questions by using their ability to deconstruct sentences. By deciphering sentences from PubMed, these users will help us support biomedical research. At the same time that the users learn more about biology and biological pathways involved in disease, our approach can also leverage participation by expert biologists. These biologists are given contested questions, have their answers up-weighed, and utilize an expert user interface that allows them to provide corrections to the pathways.

1 0

K Wolf generals
by Melissa M. Lawson 02 May '13

02 May '13

KatieAnna Wolf will present her research seminar/general exam on Wednesday May 8 at 2PM in Room 402. The members of her committee are: Rebecca Fiebrink, advisor, Adam Finkelstein, and Szymon Rusinkiewicz. 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. ------------------------- Abstract Sonification refers to the technique of “rendering sound in response to data and interactions” (Hermann et al. 2011). Sonification has been used in both the field of auditory displays as a means of conveying information and the field of computer music as a form of music composition. While these two domains both use sonification to transform data to sound, their objectives are not the same. The goal of sonification in auditory displays is to render the sound in such a way that a trained listener is able to interpret the data based on the sound. In musical composition the goal of sonification is to create music, where the data does not necessarily need to be interpretable through the sound, and individual composers may have different objectives depending on their creative motivations. Toolkits have been developed to help support sonification for auditory displays by allowing users to input their own data and specify the mapping of the data to sound parameters. Tools related to supporting sonification for music composition have been limited to domain-specific data. The goal of our project is to make the process of creative sonification easier for composers by developing more general tools. To accomplish this goal we first seek to understand why people use sound (to convey information) and data (for musical compositions) as opposed to other mediums, and how they currently utilize tools and technologies to design sonifications. In this talk we present the motivations for using sound and data and review current sonification tools. We also present our own sonification tool, SonNet, which supports music composition using computer network data. Through a pilot evaluation of SonNet with computer music composers we concluded that being able to understand the behaviour of the network data was an important step in developing musical sonifications. In addition to reviewing and gathering information on current creative sonification tools, we are conducting structured interviews with several computer music composers who have experience using data to drive their compositions. Through these interviews we intend to gather information on how composers actually utilize creative sonifications in their compositions and the challenges that composers face when working with data. We hope to gain insights into the relationship between the composers and the data, including why composers choose a certain set of data, how closely composers know the data, and what tools composers use to interact and learn about the data. By combining the analysis of these interviews with our work on domain-specific sonification applications and literature on creativity support tools we intend to develop sonification tools for composers as a step towards our goal of making creative sonification easier. Texts: [1] T. Hermann, A. Hunt, and J. G. Neuhoff, editors. The Sonification Handbook. Logos Publishing House, 2011. (Chapters: 1-16) [2] J. Lazar, J. Feng, and H. Hochheiser. Research Methods in Human-Computer Interaction. John Wiley & Sons, 2010. (Chapters: 1-5, 7-11) Papers: [3] M. Edwards. Algorithmic composition: Computational thinking in music. Communications of the ACM, 54(7):58-67, July 2011. [4] R. Fiebrink, D. Trueman, C. Britt, M. Nagai, K. Kaczmarek, M. Early, M. Daniel, A. Hege, and P. R. Cook. Toward understanding human-computer interaction in composing the instrument. In Proceedings of the International Computer Music Conference, 2009. [5] A. Hunt and M. M. Wanderley. Mapping performer parameters to synthesis engines. Organised Sound, 7:97-108, 2002. [6] S. K. Lodha, D. Whitmore, M. Hansen, and E. Charp. Analysis and user evaluation of a musical-visual system: Does music make any difference? In Proceedings of the International Conference on Auditory Display, 2000. [7] C. McKinney and A. Renaud. Leech: Bittorrent and music piracy sonication. In Proceedings of the Sound and Music Computing Conference, 2011. [8] A. McLean and G. Wiggins. Computer Programming in the Creative Arts. In Computers and Creativity, pages 235-252. Springer, 2012. [9] B. Shneiderman. Creating creativity: User interfaces for supporting innovation. ACM Transactions on Computer-Human Interaction, 7(1):114-138, 2000. [10] B. N. Walker and J. T. Cothran. Sonification sandbox: A graphical toolkit for auditory graphs. In Proceedings of the International Conference on Auditory Display, 2003.

1 0

Bring Your Own Device and Sandboxing Technology- Friday May 10th, 12:30pm
by Nicole E. Wagenblast 02 May '13

02 May '13

Bring Your Own Device and Sandboxing Technology Date: Friday, May 10, 2013 Location: 306 Sherrerd Hall Streaming Live: https://www.youtube.com/user/citpprinceton Food and discussion begins at 12:30 pm. Everyone invited . CLE credit expected – details to follow. Join us for a panel discussion on the evolving legal, policy, and technical issues associated with the use of personal mobile devices for work. The panelists will explore the tension between the need to protect business information (including personal information for which businesses are responsible) and respect for users’ privacy and personal content. The current advantages and limitations of “sandboxing” technology will be covered, focusing on opportunities for enhanced information security (on the business side) and privacy (on the personal side). The panelists will be Keith Epstein, General Attorney & Associate General Counsel Advanced Mobility Solutions, AT&T Services, Inc.; Bart Huffman, Privacy & Data Security Practice, Locke Lord LLP; and Andy Aiello, Chief Operating Officer, OpenPeak, Inc., which provides multimedia touch-screen device and device management platforms.

1 0

Tobechukwu Nwanna MSE thesis talk
by Melissa M. Lawson 01 May '13

01 May '13

Tobechukwu Nwanna will present his MSE thesis talk on Monday May 6 at 1PM in Room 402. The members of his committee are: Szymon Rusinkiewicz, advisor and Margaret Martonosi, reader. Everyone is invited to attend his talk. His abstract follows below. -------------------- Real time three dimensional motion sensing using sensor fusion on smartphones The need for users to explore three dimensional spaces is becoming increasingly common. Currently most input devices for interfacing with these environments try to map two dimensional movement to a three dimensional space. This means that to fully explore the environment, either mode switching or other combinations of inputs are required. While this works, it is unintuitive and unnatural. There have been a number of natural user interfaces that provide more intuitive controls through a wide variety of methods including inertial navigation and visual odometry. Inertial navigation tracks the relative position and orientation of an object with dead reckoning, using the objects' internal motion sensors. Visual odometry, on the other hand, tracks the optical flow of features identified using a camera and attempts to estimate the camera pose and movement from that. While each method has its advantages, each also has weaknesses that usually require the use of an external sensor for correction. We propose a solution that does not require an external sensor and instead uses each method to correct for errors in the other. We chose smartphones as a medium as they are sensor rich devices and ubiquitous enough to most users are comfortable using them. Our method tracks the orientation of the device using internal motion sensors while tracking the linear motion using camera data. Both types of input are placed into a kalman filter that attempts to minimize the effects of noise and reduce the accumulation of errors in each using data from the other. In addition to explaining the system, we will detail some potential uses and how this interface improves over existing ones.

1 0

Profiling big data systems at google- Talk today at 3:30pm
by Nicole E. Wagenblast 01 May '13

01 May '13

Profiling Latency in Deployed Distributed Systems Gideon Mann , Google Wednesday, May 1, 2013, 3:30pm Computer Science 105 Understanding the sources of latency within a deployed distributed system is complicated. Asynchronous control flow, variable workloads, pushes of new backend servers, and unreliable hardware all can make significant contribution to a job's performance. In this talk, I'll present the work of the Weatherman effort to build a profiling tool for deployed distributed systems. The method uses distributed traces to estimate the code control flow and predict/explain observed performance. I'll then illustrate how this method has been applied to understand and tune large distributed systems at Google and how it has been used in a differential profiling fashion to understand the sources of latency changes. To provide another view of latency, I'll quickly discuss our recent work on distributed convex optimization with an emphasis on the interface between the algorithm and the computing substrate performing the computation. In particular, I'll show that data center architecture, in particular network architecture, should have a significant impact on machine learning algorithm design. Gideon is a Staff Research Scientist at Google NY. He attended Brown University as an undergraduate where he hung out in the AI lab and drank too much Mountain Dew. He then attended graduate school at Johns Hopkins University, worked in CLSP, and graduated in 2006 with a Ph.D. He still misses Charm City. He then spent a post-doc at the UMass/Amherst with Andrew McCallum working on weakly-supervised learning. In 2007, he joined Google. At Google, his team works on applied machine learning. The Weatherman effort leverages statistical methods to data center management. The team also is responsible for the Prediction API (https://developers.google.com/prediction/). Publicly released in 2010, Prediction was an early machine learning as a service offering and remains an ongoing research project.

1 1

A Garg general exam
by Melissa M. Lawson 30 Apr '13

30 Apr '13

Ankit Garg will present his research seminar/general exam on Monday may 6 at 2PM in Room 402. The members of his committee are: Mark Braverman (advisor), Zeev Dvir, 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. ---------------------------- Title : Communication Complexity of Small-Set Disjointness Abstract : We obtain a tight bound of $\frac{2}{\ln 2}k \pm o(k)$ on the randomized communication complexity of disjointness of sets of size $\le k$. An asymptotic bound of $\Theta(k)$ was previously shown by H{\aa}stad and Wigderson. One of the key components is the tight analysis for the zero-error information complexity of the 2-bit $AND$ function. This is obtained using a new local characterization of the zero-error information complexity function for two party communication problems. The lower bound for small-set disjointness requires an additional continuity argument for information complexity. It is trickier than disjointness, since we have to deal with very small information costs. Also the upper bound requires a nontrivial application of the ``information equals amortized communication" theorem. This is joint work with Mark Braverman, Denis Pankratov and Omri Weinstein. Reading List : Book : Computational Complexity - Sanjeev Arora and Boaz Barak Papers : 1. Information equals amortized communication - Mark Braverman, Anup Rao, FOCS 2011. 2. How to compress interactive communication - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao, STOC 2010 3. Interactive information complexity - Mark Braverman, STOC 2012 4. Communication lower bounds using directional derivatives - Alexander Sherstov, ECCC 2013 5. Direct products in communication complexity - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff, ECCC 2013. 6. Rounding Parallel Repetitions of Unique Games - Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev and David Steurer, FOCS 2008. 7. Lower bounds on information complexity via zero-communication protocols and applications - I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. FOCS 2012. 8. Parallel Repetition in Projection Games and a Concentration Bound - Anup Rao, STOC 2008. 9. Algebrization: A New Barrier in Complexity Theory - S. Aaronson, A. Wigderson, STOC 2008. 10. On proving Super-Logarithmic Depth Lower Bounds via the Direct sum in Communication Complexity, M.Karchmer, R.Raz, A.Wigderson, Journal of Computational Complexity, 1995. 11. On ACC, R. Beigel and J. Tarui, Computational Complexity, 1994.

1 0

R Oda general exam
by Melissa M. Lawson 30 Apr '13

30 Apr '13

Reid Oda will present his research seminar/general exam on Monday May 6 at 10AM in Room 402. The members of his committee are: Rebecca Fiebrink (advisor), Adam Finkelstein, 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: The Internet allows musicians and other artists to collaborate remotely with one another. However, network latency presents a fundamental challenge for remote collaborators who need to coordinate and respond to each other's performance in real time. Latencies of more than 55 ms round-trip make it difficult for performers to synchronize with one another. Each performer slows down to keep in time with the other, causing the performance to fall apart. Researchers have optimized client software in order to reduce latency as far as possible, but the leading cause of the latency, the architecture of the Internet, is beyond the control of the user. Recently a system was developed to recognize patterns in the music being played, and to synthesize those same classes of patterns on the far end of the connection. This allows musicians to "play" in synchrony, but because of the pattern-level granularity of the synthesis algorithm, the receiver will not hear actual notes being played by the sender. I present a system which attempts note-level prediction. The system predicts percussion hits before they have occurred, so that information about the predicted drum hit can be sent over a network, and the sound can be synthesized at a receiver's location at approximately the same moment the hit occurs locally. The system uses a high-speed camera to track a percussion mallet. It uses regression and pattern matching to predict the note, timing and velocity of the percussion hit. In order to synchronize music events in real-time, it uses a modified version of Marzullo's clock synchronization algorithm. I show that it is possible to predict a percussion note within the bounds of perceptual synchrony, 30-40 ms before the event occurs. A 40 ms lead time means that two artists in Boston and New York city could potentially play together with perfect synchrony. TEXT: E. R. Miranda and M. M. Wanderley, New Digital Musical Instruments. A-R Editions, Inc., 2006. (Chapter 3) J. P. Caceres, “Synchronization Of Rhythmic Performance With Delay,” 2013. (Chapters 6 & 7) A. Greenbaum and T. P. Chartier, Numerical Methods. Princeton University Press, 2012. S. Dahl, “Striking movements: A survey of motion analysis of percussionists,” Acoust. Sci. & Tech., vol. 32, no. 5, pp. 168–173, 2011. J. P. Caceres and C. Chafe, “JackTrip: Under the hood of an engine for network audio,” Journal of New Music Research, vol. 39, no. 3, pp. 183–187, 2010. P. Oliveros, S. Weaver, M. Dresser, J. Pitcher, J. Braasch, and C. Chafe, “Telematic music: six perspectives,” Leonardo Music Journal, vol. 19, no. 1, pp. 95–96, 2009. (Chapter 3) M. Sarkar, “Tablanet: a real-time online musical collaboration system for indian percussion,” Massachusetts Institute of Technology, 2007. J. P. Lewis, “Fast template matching,” vol. 95, no. 120123, pp. 15–19, 1995. M. V. Mathews, “The radio baton and conductor program, or: Pitch, the most important and least expressive part of music,” Computer Music Journal, pp. 37–46, 1991. K. Marzullo and S. Owicki, “Maintaining the time in a distributed system,” pp. 295–305, 1983. V. Cerf and R. Kahn, “A Protocol for Packet Network Intercommunication,” Communications, IEEE Transactions on, vol. 22, no. 5, pp. 637–648, 1974.

1 0

Seminar speaker tomorrow: Prof. Josep Torrellas, UIUC
by Margaret Martonosi 30 Apr '13

30 Apr '13

Hello all-- A final reminder: Prof. Josep Torrellas from UIUC will be visiting Princeton and giving a seminar on Tuesday April 30. The seminar will be from 12:30-1:30 in CS Room 302, with pizza beforehand starting at noon. Title/abstract below. I have reserved a 1-hour slot for him to meet with grad students from 2:30-3:30pm that day. That will occur in CS room 401. Any interested grad students can feel free to just show up for that. Thanks, Margaret ----------------------------------------------------------------- Toward Programmable High-Performance Multicores Josep Torrellas University of Illinois, Urbana-Champaign http://iacoma.cs.uiuc.edu/~torrellas One of the biggest challenges facing us today is how to design parallel architectures that attain high performance while efficiently supporting a programmable environment. In this talk, I describe novel organizations that will make the next generation of multicores more programmable and higher performance. Specifically, I show how to automatically reuse the upcoming transactional memory hardware for optimized code generation. Next, I describe a prototype of Record&Replay hardware that brings program monitoring for debugging and security to the next level of capability. I also describe a new design of hardware fences that is overhead-free and requires no software support. Finally, if time permits, I will outline architectural support to detect sequential consistency violations transparently. BIO: Josep Torrellas is a Professor of Computer Science and Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). He is a Fellow of IEEE and ACM. He is the Director of the Center for Programmable Extreme-Scale Computing, a center funded by DARPA, DOE, and NSF that focuses on architectures for extreme energy and power efficiency. He also directs the Intel-Illinois Parallelism Center (I2PC), a center created by Intel to advance parallel computing in clients. He has made contributions to parallel computer architecture in the areas of shared-memory multiprocessor organizations, cache hierarchies and coherence protocols, thread-level speculation, and hardware and software reliability. He received a Ph.D. from Stanford University. ------------------------------------------------------------ Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

2 1

N Kang general exam
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Nanxi Kang will present her research seminar/general exam on Friday May 3 at Noon in Room 301 (note room!). The members of her committee are: Jennifer Rexford (advisor), David Walker, and Vivek Pai. 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. ----- Original Message ----- Abstract Software Defined Networking (SDN) supports diverse network policies by offering direct, network-wide control over how the switches handle traffic. However, today’s controller platforms force applications to grapple with the space limits on each switch and the interaction between the packet-handling rules at different hops in a path. Instead, we believe SDN applications should specify high-level policies, and rely on the controller to generate the rules for each switch. A high-level policy defines the handling of traffic on a single abstract switch (indicating how packets should be modified, and dropped or forwarded to egress ports), as well as the routing of traffic across the “switching fabric.” Transforming the high-level policy into an equivalent set of switch-level rules is computationally difficult, since the policy may route traffic on arbitrary paths and match traffic on multiple dimensions of packet-header fields. We present a family of efficient rule-placement algorithms, starting with the simple case of policies matching one packet-header field along a chain, and building up to the general case which involves arbitrary routing, multi-dimensional patterns and the need to enable dynamic, incremental update of policies. Our experiments with synthetic benchmarks, and real firewall and routing policies, demonstrate that our algorithms can support realistic policies using the small rule tables available in commodity switches. ---------------------------------- Reading List [1] L. L. Peterson and B. S. Davie, Computer networks: a systems approach. Morgan Kaufmann, 2007. [2] J. H. Saltzer, D. P. Reed, and D. D. Clark, “End-to-end arguments in system design,” ACM Transactions on Computer Systems (TOCS), vol. 2, no. 4, 1984. [3] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker, “Rethinking enterprise network control,” IEEE/ACM Trans. Networking, vol. 17, August 2009. [4] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Computer Communications Review, vol. 38, no. 2, 2008. [5]C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker, "Composing software dened networks," in NSDI, Apr 2013. [6] M. Yu, J. Rexford, M. J. Freedman, and J. Wang, "Scalable ﬂow-based networking with DIFANE," In ACM SIGCOMM, pp. 351-362, Sep 2010. [7] M. Moshref, M. Yu, A. Sharma, and R. Govindan, "VCRIB: Virtualized rule management in the cloud," in NSDI, Apr 2013. [8] Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-dened networks," in IEEE INFOCOM Mini-conference, Apr 2013. [9] C. R. Meiners, A. X. Liu, and E. Torng, "TCAM Razor: A systematic approach towards minimizing packet classiers in TCAMs," IEEE/ACM Trans. Netw., vol. 18, pp. 490-500, Apr 2010. [10] P. Gupta and N. McKeown, "Packet classication on multiple fields," in ACM SIGCOMM, pp. 147-160, 1999. [11] S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet classication using multidimensional cutting," in ACM SIGCOMM, pp. 213-224, 2003. [12] Y. Ma and S. Banerjee, "A smart pre-classier to reduce power consumption of tcams for multi-dimensional packet classication," in ACM SIGCOMM, pp. 335-346, Aug 2012.

1 0