- talks - lists.cs.princeton.edu

Matvey Arye is presenting his Pre FPO titled "Data Processing Across Continents" on April 30, 2015 at 3pm in CS 401
by Nicki Gotsis 24 Apr '15

24 Apr '15

Matvey Arye is presenting his Pre FPO April 30, 2015 at 3pm in CS 401. The members of his/her committee are: Mike Freedman(advisor), Kai LI (reader), Andrea Lapaugh(reader), Jen Rexford (non-reader), Nick Feamster(non-reader) Everyone is invited to attend his talk. The talk title and abstract follow below: Title: "Data Processing Across Continents" Abstract: An increasing number of data sources create data across the globe. These include everything from server logs owned by Internet-scale companies to military intelligence systems. This thesis addresses the question of how to enable near-real-time analytical queries on such data. Existing systems tend to centralize such data into a single datacenter before analyzing it. However, in light of low and asymmetric bandwidth provisioning in and between certain geographic regions, centralizing all data can be both slow and costly. I have addressed this problem with three complementary research directions. First, I describe a system that queries the data in a distributed manner and centralizes only the data that is needed to fulfill the query. It dynamically adjusts the accuracy of its answers to tradeoff data quality versus responsiveness. Second, I explore some challenges due to the interaction between an application-level dynamic quality adaptation control loop and TCP (which has its own control loop). These two control loops can create negative feedback effects and propose a way to overcome this. We translate these insights into the domain of Internet video streaming, and show improvements in streaming performance over leading industry players. Finally, I present a case study of how to optimize the top-k query for wide-area analysis. The top-k query addresses questions of popularity and is thus ubiquitous in modern computer systems. My algorithms reduce both the bandwidth usage and number of rounds used by such queries.

1 0

Young-suk Lee will present his Pre FPO on 4/28 at 4pm in CS 401
by Nicki Gotsis 24 Apr '15

24 Apr '15

Young-suk Lee will present his Pre FPO on 4/28 at 4pm in CS 401. His committee members are: Olga Troyanskaya (advisor), Barbara Engelhardt , Kai Li, Thomas Funkhouser, and John Storey (MOL). Everyone is invited to attend his talk. The talk title and abstract follow below: Targeted analyses of very large genomic data collections. Genome-scale experiments provide an overwhelming amount of molecular information for biologist. New computational methods are needed for specific analysis and interpretation of such high-dimensional data. Here we take advantage of the massive public repositories to quantify the tissue-specific signals in gene expression profiles, characterize distinctive molecular features of human diseases, deconvolve the latent cell-type-specific factors in mixed clinical samples, and automatically integrate heterogeneous data sources in the context of a specific genome-wide dataset. We present Unveiling RNA Sample Annotation (URSA) that incorporates the known tissue/cell-type relationships to better estimate the specific tissue/cell-type signal in any given gene expression profile. Our ontology-aware method combines independent discriminative classifiers in a Bayesian framework, outperforming other machine learning methods. URSA can also predict the correct tissue-type for cross-platform samples including RNASeq data without re-training URSA. Finally, we provide a molecular interpretation for the tissue and cell-type models learned by URSA, enabling a data-driven view of molecular processes specific to particular tissues and cell types. Complex diseases are driven by multiple genetic changes and characterized by genome-wide perturbations of cellular pathways and functions. We developed a unified framework to quantify distinctive functional and anatomical characteristics of human diseases from thousands of clinical disease-specific profiles from public repositories. Our data-driven analysis, in conjunction with known biology, can be used to repurpose drugs for rare disease with no prior genetic knowledge. Clinical samples are heterogeneous and consist of many different cell-types, and so genome-scale experiments for these samples result as an admixture of these cell-types and their proportions. Assuming that clinical samples share the same cell-types, we designed a Bayesian nonparametric model to deconvolve the latent cell-type-specific signal in gene expression profiles of clinical samples. Our method estimates the number of cell-types, the cell-type-specific expression profiles, and the sample-specific cell-type proportions from large clinical datasets without relying on any additional information beyond the gene expression data. Integration of heterogeneous genome-wide data sources has been used to generate functional networks, predict gene function, and study human disease. Most biomedical researchers have specific questions they want to answer with such integrations, and these questions are usually accompanied by a user-produced genome-scale dataset they want to analyze in the context of these big public data collections. However, currently no approach exists to enable such user-guided integration. Here we develop an automatic integration method that constructs functional networks specific to a genome-scale dataset, and show that the resulting integrations reflect the biological context of the user-provided dataset, while providing accurate functional predictions.

1 0

Huiwen Chang will present her General Exam April 30, 2015 at 1pm in CS401
by Nicki Gotsis 23 Apr '15

23 Apr '15

Huiwen Chang will present her General Exam April 30, 2015 at 1pm in CS401. The members of her committee are: Adam Finkelstein (adviser), Jianxiong Xiao, Thomas Funkhouser. 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: Color manipulation is a key process in photo enhancement, and professional image editing suites incorporate an array of tools to support it. Some of these tools are easy to understand but offer a limited range of expressiveness. Other more powerful tools are difficult and time consuming to use, and inscrutable to novices. Researchers have described a variety of more sophisticated methods but these are typically not interactive, which is crucial for creative exploration. This paper introduces a simple, intuitive and interactive tool that allows non-experts to recolor an image colors by editing a color palette. This system is comprised of several components: a GUI that is easy to learn and understand, a new efficient algorithm for creating a color palette from an image, and a new efficient color transfer algorithm that recolors the image based on a user-modified palette. We evaluate our approach via a user study, showing that it is faster and easier to use than two alternatives. It also shows that untrained users can quickly achieve results comparable to those of experts using professional software. Reading List: Bychkovsky, V., Paris, S., Chan, E., & Durand, F. (2011, June). Learning photographic global tonal adjustment with a database of input/output image pairs. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on (pp. 97-104). IEEE. Cohen-Or, D., Sorkine, O., Gal, R., Leyvand, T., & Xu, Y. Q. (2006, July). Color harmonization. In ACM Transactions on Graphics (TOG) (Vol. 25, No. 3, pp. 624-630). ACM. Lin, S., & Hanrahan, P. (2013, April). Modeling how people extract color themes from images. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 3101-3110). ACM. Lin, S., Ritchie, D., Fisher, M., & Hanrahan, P. (2013). Probabilistic color-by-numbers: Suggesting pattern colorizations using factor graphs. ACM Transactions on Graphics (TOG) , 32 (4), 37. Shapira, L., Shamir, A., & Cohen‐Or, D. (2009, April). Image Appearance Exploration by Model‐Based Navigation. In Computer Graphics Forum (Vol. 28, No. 2, pp. 629-638). Blackwell Publishing Ltd. Wang, B., Yu, Y., Wong, T. T., Chen, C., & Xu, Y. Q. (2010, December). Data-driven image color theme enhancement. In ACM Transactions on Graphics (TOG) (Vol. 29, No. 6, p. 146). ACM. Wang, X., Jia, J., & Cai, L. (2013). Affective image adjustment with a single word. The Visual Computer , 29 (11), 1121-1133. Tai, Y. W., Jia, J., & Tang, C. K. (2005, June). Local color transfer via probabilistic segmentation by expectation-maximization. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on (Vol. 1, pp. 747-754). IEEE. O'Donovan, P., Agarwala, A., & Hertzmann, A. (2011, August). Color compatibility from large datasets. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 4, p. 63). ACM. Chang, Y., Saito, S., Uchikawa, K., & Nakajima, M. (2006). Example-based color stylization of images. ACM Transactions on Applied Perception , 2 (3), 322-345. Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002). An efficient k-means clustering algorithm: Analysis and implementation. Pattern Analysis and Machine Intelligence, IEEE Transactions on , 24 (7), 881-892. Hearn, D. D., Baker, M. P., & Carithers, W. (2010). Computer graphics with open gl . Prentice Hall Press.

1 0

Young Kun Ko will present his Generals April 29, 2015 at 10am in CS 302
by Nicki Gotsis 23 Apr '15

23 Apr '15

Young Kun Ko will present his Generals on April 29, 2015 at 10am in CS 302. The members of his committee are: Mark Braverman (adviser), Zeev Dvir, and Elad Hazan 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 celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O(log n) in the random graph G(n, 1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it would imply a 2O˜(n1/2) algorithm for SAT. Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. Reading List Textbooks • Computational Complexity (Arora & Barak) Papers • How hard is it to approximate the best Nash Equilibrium? by Elad Hazan and Robert Krauthgamer • Inapproximability of NP-complete variants of Nash equilibrium by Per Austrin, Mark Braverman, Eden Chlamtac • Playing large games using simple strategies by Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta • AM with multiple Merlins by Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz • Quantum de finetti theorems under local measurements with applications by Fernando G. S. L. Brandao and Aram Harrow • Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, and Mario Szegedy • Inapproximability of densest k-subgraph from average case hardness by Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein • Graph expansion and the unique games conjecture by Prasad Raghavendra and David Steurer • Finding endogenously formed communities by Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng • The PCP theorem by gap amplification by Irit Dinur

1 0

Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401
by Nicki Gotsis 20 Apr '15

20 Apr '15

Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401. His committee is as follows: Zeev Dvir (advisor), Sanjeev Arora, and Bob Tarjan. 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. ============================================ 2-Server PIR with sub-polynomial communication ------ A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i'th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost sub polynomial in n. This improves over the currently known 2-server protocols which require n^{1/3} communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives. Reading list: References [1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. [2] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 519–528. ACM, 2011. [3] Richard Beigel and Jun Tarui. On ACC [circuit complexity]. In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 783–792. IEEE, 1991. [4] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In FOCS, pages 41–50, 1995. [5] Zeev Dvir. Incidence theorems and their applications. Foundations and Trends R in Theoretical Computer Science, 6(4):257–393, 2010. [6] Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 705–714. IEEE, 2010. [7] Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC, pages 39–44, 2009. [8] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In 32nd ACM Symposium on Theory of Computing (STOC), pages 80–86, 2000. [9] David A Mix Barrington, Richard Beigel, and Steven Rudich. Representing boolean functions as polynomials modulo composite numbers. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 455–461. ACM, 1992. [10] Alexander A Razborov and Sergey Yekhanin. An Ω(n 1/3 ) lower bound for bilinear group based private information retrieval. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages 739–748. IEEE, 2006. 1 [11] Gabor Tardos and DA Mix Barrington. A lower bound on the MOD 6 degree of the OR function. Computational Complexity, 7(2):99–108, 1998. [12] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008.

1 0

Jordan Ash will present his masters thesis talk Wednesday, April 22, 2015 at 3:30 in rm 401
by Nicki Gotsis 20 Apr '15

20 Apr '15

Jordan Ash will present his masters thesis talk Wednesday, April 22, 2015 at 3:30 in rm 401 His readers are Rob Schapire (adviser) and Barbara Engelhardt. Everyone is invited to attend his talk. His abstract follows below. Title: A Novel Domain Adaptation Solution to the Transductive Transfer Learning Problem Abstract: Most classification algorithms rely on the assumption that training and testing data come from the same distribution. When this assumption is violated, classification performance can be seriously affected. Transfer learning, a new and increasingly popular branch of machine learning, seeks to solve this problem. In this thesis, we introduce a novel transductive transfer learning technique that functions by aligning the training and testing datasets before classification. Our method is motivated by a particular problem involving Magnetoencephalography ( MEG) data classification, but can be used for other transfer learning problems as well.

1 0

Quan Zhu will present his Pre-FPO Friday, April 24, 2015 in rm 401 at 10am
by Nicki Gotsis 17 Apr '15

17 Apr '15

Quan Zhu will present his Pre-FPO Friday, April 24, 2015 in rm 401 at 10am. The members of his committee are: Olga Troyanskaya (adviser), Mona Singh, Kai Li, Moses Charikar, and Vessela Kristensen (University of Oslo, Norway) Title: Exploring gene similarities in large-scale compendia Public gene expression datasets have been rapidly accumulating, yet there is currently a lack of effective tools in reusing existing datasets and exploring them for targeted analyses. One of the most central analyses is discovering similar genes in a data-driven way through clustering, biclustering, and query-search approaches. This thesis explores these issues and is divided into three parts. In the first part, we describe a fast, content-based, query-based search solution for discovering gene similarities in large data collections. The second part of this thesis then explores different applications of the search tool, including the role of coexpression in leading to regulatory factor discovery and biological network inference when it is being integrated with secondary data. Lastly, we extend work from a recently developed biclustering approach that discovers low-rank submatrix from a large matrix, and we explore its usage and describe a modification that can enumerate all coregulated genes and conditions. We first present the developed system SEEK, a web-based tool and a novel algorithm for exploring and visualizing gene expression patterns from thousands of datasets. Through flexible multi-gene queries, the system uses gene “hubbiness” correction procedure for balancing well-coexpressed genes in the results. It uses an automatic, data-driven dataset weighting algorithm for filtering irrelevant datasets, up-rank datasets which may be relevant to the user’s query, on the basis of coexpression of query genes. This algorithm thus eliminates the need to manually find relevant datasets (which is impossible), and at the same time achieves query-sensitivity. Notably, through robust search of thousands of human datasets, the retrieval of functionally co-annotated genes always improves with the inclusion of more datasets, showing the promise of the large compendia. We extend the function of SEEK to 5 other model organisms, in a new system called modSEEK, with the goal of enabling accurate searches in a wider experimental variety. In terms of the applications, we show that SEEK and modSEEK, when integrated with secondary Chip-seq compendia, are accurate in uncovering upstream transcription factor (TF) and their relationships. These are summarized in a TF regulatory network which carries value in hypothesis generations and directing follow-up studies. Regulatory associations between TF’s are accurate according to in vitro motif evidence. Biclustering is a problem that involves computationally intensive calculations. Prior work operates on binary version of the matrix, which may incur a small loss of resolution. Finding multiple biclusters usually involves masking the data with random values which prevents finding overlapping biclusters. At the same time, this solution is computationally inefficient since masking the data and repeating the procedure does not reduce problem size. I thus develop a recursive, divide-and-conquer approach that extends the recently developed algorithm on finding low-rank submatrix (see Aaditya V. Rangan et al). The proposed algorithm applies his algorithm on large-scale and finds multiple low-rank biclusters. The approach finds high-resolution small biclusters and combines them through post-processing. This algorithm is fast and capable of enumerating all biclusters in the dataset.

1 1

Marcela Melara will present her General Exam Tuesday, April 21, 2015 at 10am in Rm 301
by Nicki Gotsis 14 Apr '15

14 Apr '15

Marcela Melara will present her General Exam Tuesday, April 21, 2015 at 10am in Rm 301 The members of her committee are: Ed Felten (advisor), Mike Freedman, Arvind Narayanan. 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: We present CONIKS, an end-user key verification service capable of integration in end-to-end encrypted communication systems. CONIKS builds on related designs for transparency of web server certificates but solves several new challenges specific to key verification for end users. In comparison to prior designs, CONIKS enables more efficient monitoring and auditing of keys, allowing small organizations to effectively audit even very large key servers. CONIKS users can efficiently monitor their own key bindings for consistency, downloading less than 20 kB per day to do so even for a provider with billions of users. CONIKS users and providers can collectively audit providers for non-equivocation, and this requires downloading a constant 2.5 kB per day regardless of server size. Unlike any previous proposal, CONIKS also preserves the level of privacy offered by today’s major communication services, hiding the list of usernames present and even allowing providers to conceal the total number of users in the system. Reading List: J. Li, M. Krohn, D. Mazieres and D. Shasha, “Secure Untrusted Data Repository (SUNDR).” OSDI, 2004. R. C. Merkle, “A digital signature based on a conventional encryption function.” CRYPTO, 1987. S.Micali, M. Rabin and S. Vadhan, “Verifiable Random Functions.” FOCS, 1999. D. Wendlandt, D. G. Andersen, A. Perrig, “Perspectives: Improving SSH-style Host Authentication with Multi-Path Probing.” USENIX Security Symposium, 2008. B. Laurie, “Certificate Transparency.” ACM Queue, 2014. M. D. Ryan, “Enhanced Certificate Transparency and End-to-End Encrypted Mail.” NDSS, 2014. A. Ulrich, R. Holz, P .Hauck and G. Carle, “Investigating the OpenPGP web of trust.” ESORICS, 2011. C. Ellison, “Establishing identity without certification authorities.” Usenix Security, 1996. D. Mazieres, M. Kaminsky, M. F. Kaashoek and E. Witchel, “Separating key management from file system security.” SOSP, 1999. N. Borisov, I. Goldberg and E. Brewer, “Off-the-Record Communication, or, why not to use PGP.” WPES, 2004. A. Whitten and J. D. Tygar, “Why Johnny Can’t Encrypt: A Usability Evaluation of PGP 5.0.” Usenix Security, 1999. T. Perrin, “Axolotl Ratchet.” https://github.com/trevp/axolotl/wiki R. Andersen, “Security Engineering,” 2nd Ed., 2008. Chapters 3, 5, 6, 21. J. Katz and Y. Lindell, “Introduction to Modern Cryptography”, 1st Ed., 2007.

1 0

Fwd: EE Department Seminar-Prof. Muriel Medard - April 20, 2015 4:30pm
by Jennifer Rexford 13 Apr '15

13 Apr '15

> From: "Cynthia L. Menkes" <cmenkes(a)Princeton.EDU> > Date: April 13, 2015 at 4:26:51 PM EDT > To: ee-seminar(a)Princeton.EDU > Subject: EE Department Seminar-Prof. Muriel Medard - April 20, 2015 4:30pm > Reply-To: "Cynthia L. Menkes" <cmenkes(a)Princeton.EDU> > > > > >

1 0

Colloquium Speaker Kyle Jamieson today, 12:30pm
by Nicole E. Wagenblast 13 Apr '15

13 Apr '15

Colloquium Speaker Kyle Jamieson, University College, London Monday, April 13, 12:30pm Computer Science 105 Leveraging Array Signal Processing in the Wireless Internet of Things Phased array signal processing has long been employed outdoors in radar, underwater in sonar, and underground in seismic monitoring. Today, it has the potential to revolutionize the Internet of Things (IoT) by giving us the ability to track every one of the billions of IoT devices indoors, and meet their exploding bandwidth requirements. But to make the shift to indoor wireless networks, it must cope with strong multipath radio reflections, packetized data transmissions, and commodity hardware platforms. In this talk I will describe two relevant systems through the lens of system-building and experimentation. First, I will describe an indoor location system that uses solely the existing Wi-Fi infrastructure to achieve a median location accuracy of 23 centimeters, and sub-second response time, allowing Wi-Fi-enabled devices to be tracked in real-time. Next, I will present a MIMO-based Sphere Decoder system that leverages novel search algorithms and geometric reasoning to increase wireless throughput, the first of its kind that scales to 256-QAM constellation densities with computational demands that are practically realizable in current ASIC hardware. Finally, I will conclude with a vision of how these techniques will support exciting IoT applications such as video analytics over billions of indoor wireless cameras. Kyle Jamieson is a Senior Lecturer (U.S. equivalent: Assistant Professor) in the Department of Computer Science at University College London (UCL). His research interests are in building wirelessly networked systems for the real world that cut across the boundaries of digital communications and networking. Prior to joining UCL, he received the B.S., M.Eng., and Ph.D. (2008) degrees in Computer Science from the Massachusetts Institute of Technology. He then received a Starting Investigator fellowship from the European Research Council in 2011, Best Paper awards at USENIX 2013 and CoNEXT 2014, and a Google Faculty Research Award in 2015. He regularly serves on the program committees of the ACM MobiCom, USENIX NSDI, and ACM SIGCOMM conferences.

1 0