- talks - lists.cs.princeton.edu

K Edwards general exam
by Melissa M. Lawson 06 May '13

06 May '13

Katherine Edwards will present her research seminar/general exam on Friday May 10 at 2PM in room 302. The members of her committee are: Paul Seymour (Math) advisor, Moses Charikar, and Mark Braverman. 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. ----------------------------- Edge-coloring 7- and 8-regular planar graphs In 1974, Seymour conjectured the following: Let G be a k-regular planar (multi)graph, such that for every odd set X of vertices of G, at least k edges of G have one end in X and the other in V (G) nX. Then G is k-edge-colorable. For k = 3 this is equivalent to the four-color theorem. The cases k = 4; 5 were solved by Guenin, the case k = 6 by Dvorak, Kawarabayashi and Kral, and the case k = 7 by Edwards and Kawarabayashi. In joint work with Chudnovsky and Seymour, we now have a proof for the case k = 8, and that is the topic of this talk. Reading list [1] Paolo Codato, Michele Conforti, and Claudia Sera ni. Packing t-joins. Journal of Graph Theory, 22(4):293{296, 1996. [2] WJ Cook, WH Cunningham, WR Pulleyblank, and A Schrijver. Combinatorial Opti- mization. 1998. New York, NY: Wiley-Interscience. [3] Bertrand Guenin. Packing t-joins and edge colouring in planar graphs. 2003. [4] Penny Haxell and Jessica McDonald. On characterizing vizing's edge colouring bound. Journal of Graph Theory, 69(2):160-168, 2012. [5] Takao Nishizeki and Kenichi Kashiwagi. On the 1.1 edge-coloring of multigraphs. SIAM Journal on Discrete Mathematics, 3(3):391-410, 1990. [6] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B, 70(1):2 -44, 1997. [7] P.D. Seymour. The matroids with the max-flow min-cut property. Journal of Combina- torial Theory, Series B, 23(2-3):189-222, 1977. [8] P.D. Seymour. On multi-colourings of cubic graphs, and conjectures of fulkerson and tutte. Proc. London Math. Soc, 38(3):423-460, 1979. [9] P.D. Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London Mathematical Society, 3(1):178-192, 1981.

1 0

Y Naamad general exam
by Melissa M. Lawson 06 May '13

06 May '13

Yonatan Naamad will present his research seminar/general exam on Friday May 10 at 1o:30 AM in room 302 (note time and room!). The members of his committee are: Moses Charikar (advisor), Mark Braverman, and Zeev Dvir. 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. ----------------------- One measure of the complexity of a problem is its query complexity, or the number of queries an algorithm must make to the input in order to output a provably-correct solution. In this talk, I'll discuss my work on establishing the query complexity of the generalized sorting problem, where we wish to establish a total order on a collection of n elements when the set of possible pairwise comparisons is restricted to a certain subset of the C(n,2) pairs of elements. If the subset is complete -- containing all C(n,2) pairs -- then the query complexity of the problem is well known to be Omega(n log n). In 2011, Huang, Kannan, and Khanna gave the first nontrivial result in the more general setting, establishing a (randomized) query complexity upper-bound of O(n^(3/2) log n). We discuss recent improvements upon their work. Based on joint work with Moses Charikar and Sampath Kannan. -- and my reading list is 1. (Book) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. 2. Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky: Matching Nuts and Bolts. SODA 1994: 690-696 3. Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query Strategies for Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002) 4. Anupam Gupta, Amit Kumar: Sorting and Selection with Structured Costs. FOCS 2001: 416-425 5. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna: Algorithms for the Generalized Sorting Problem. FOCS 2011: 738-747 6. Jeff Kahn, Jeong Han Kim: Entropy and Sorting. J. Comput. Syst. Sci. 51(3): 390-399 (1995) 7. Jeff Kahn, Nathan Linial: Balancing extensions via Brunn-Minkowski. Combinatorica 11(4): 363-368 (1991) 8. Jeff Kahn, Michael E. Saks, Dean Sturtevant: A topological approach to evasiveness. Combinatorica 4(4): 297-306 (1984) 9. Sampath Kannan, Sanjeev Khanna: Selection with monotone comparison cost. SODA 2003: 10-17 10. Krzysztof Onak, Pawel Parys: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS 2006: 379-388 11. Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput. 17(3): 517-520 (1988)

1 0

G Hu general exam
by Melissa M. Lawson 03 May '13

03 May '13

Guangda Hu will present his research seminar/general exam on Thursday May 9 at 3PM in Room 402. The members of his committee are: Zeev Dvir, advisor, Moses Charikar, and Mark Braverman. 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: Locally decodable code (LDC) is an error-correcting code that every bit of the original message can be recovered by reading only a small number of bits in the code. A major question is about the minimum length of constant query LDCs. It is known that 2-query LDC has length at least exponential of the message length. However, there is a huge gap between the lower and upper bounds if the query number is greater than 2. The lower bound for 3-query LDC is only quadratic while the best known construction has super-polynomial length. The constructions of constant query LDCs all had exponential length until a very recent breakthrough. The sub-exponential, although still super-polynomial, constructions of LDCs are based on matching vector (MV) families. An MV family is defined as two lists of n-dimensional vectors in Z_m, where only the corresponding vectors of the two lists have inner product 0. A larger MV family implies a shorter code. MV families also arise in other combinatorial contexts as well, where a large MV family can also imply new results. Therefore it is interesting to figure out the maximum size of MV families. For prime m, the upper bound of MV families are already tight. However, the question was not well understood for general composite m. In [DGY11], an upper bound m^{n-1+o(1)} was proved and m^{n/2} was conjectured. In [BDL13], the bound was improved to m^{n/2+O(log m)}. Inspired by previous works, we proved a new upper bound m^{n/2+O(1)}. Comparing to the known MV constructions, this is almost tight for m>>n. Reading List: Textbook: Computational Complexity: A modern approach. [ARORA-BARAK] [Yek08] Towards 3-query locally decodable codes of subexponential length. Sergey Yekhanin. [Efr09] 3-query Locally Decodable Codes of Subexponential Length. Klim Efremenko. [DGY11] Matching Vector Codes. Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin. [KT00] On the efficiency of local decoding procedures for error-correcting codes. Jonathan Katz, Luca Trevisan. [GKST02] Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan. [Woo07] New Lower Bounds for General Locally Decodable Codes. David P. Woodruff. [Woo10] A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. David P. Woodruff. [DS06] Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Zeev Dvir, Amir Shpilka. [BDWY11] Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff. [BDL13] New Bounds for Matching Vector Families. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett.

1 0

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