- talks - lists.cs.princeton.edu

Y Shao FPO
by Melissa M Lawson 03 May '07

03 May '07

Yilei Shao will present her FPO on Thursday May 10 at 10:30AM in Room 402. The members of her committee are: Andrea LaPaugh, advisor; J.P. Singh and Moses Charikar, readers; Kai Li and Jennifer Rexford, nonreaders. A copy of her thesis "Exploring Social Networks in Computer Science" is on display in Room 310. Everyone is invited to attend her talk.

1 0

T O'Connor general exam
by Melissa M Lawson 03 May '07

03 May '07

Tim O'Connor will present his research seminar/general exam on Thursday May 10 at 2PM in Room 302 (note room!). The members of his committee are: Manuel Llinas (Molecular Biology, advisor), Olga Troyanskaya, and David Blei. 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 Plasmodium falciparum is the causative agent of the most virulent strain of malaria, a disease that causes over one million deaths per year. Recently, this organism's genome was sequenced, but only a minority of the genes have known function, with an even smaller proportion having any detailed functional description. While manual examination of individual genes continually expands this functional knowledge base, it is a both slow and expensive way to tackle the roughly 3000 uncharacterized genes. By identifying functionally described genes related to an unknown query gene, the biological processes in which that query gene is involved can be elucidated. Several computational methods that integrate multiple, genome-wide data sets have been developed to identify functional relationships between pairs of genes. The problem of identifying functional relationships turns into a supervised machine learning problem with two class labels. Several methods can address the problem, including logistic regression, kernel methods and support vector machines, neural networks, and Bayesian networks. Our method of data integration is through the use of statistical inference with Bayesian networks, permitting multiple datasets of different types to be integrated in a way that can incorporate prior knowledge. To train the network, a benchmark gold standard of known or high confidence interactions was developed for P. falciparum. The class labels in the gold standard were obtained first from the Gene Ontology (GO) consortium using GRIFn's expert-derived approach. Secondly, labels were derived from the Malaria Parasite Metabolic Pathways (MPMP) database, which is a manually curated version of the Kyoto Encyclopedia of Genes and Genomes (KEGG) Pathways database specifically for P falciparum. Forty-th ree diverse datasets including features based on DNA sequence, comparative genomics, RNA expression profiles, and growth perturbation experiments were used as input with the predictor's parameters trained using the expectation-maximization algorithm. Functional relationship prediction accuracy was estimated using cross validation with an ROC curve of comparable to accuracy to a similar approach for yeast, which is a much more well characterized organism. The resulting predictions have been analyzed to assess the scope of the uncharacterized genome fraction which can be shown to be related to known biological processes. These predictions have also been compared to those done in yeast showing only two highly similar processes of protein synthesis and protein degradation. The predictions will be made accessible through a graphical web interface. Prior work Date, S.V. & Stoeckert, C.J., Jr. Computational modeling of the Plasmodium falciparum interactome reveals protein function on a genome-wide scale. Genome Res. 2006 Apr;16(4):542-9. Epub 2006 Mar 6. Wuchty S, Ipsaro JJ. A Draft of Protein Interactions in the Malaria Parasite P. falciparum. J Proteome Res. 2007 Feb 15 Data Integration Troyanskaya OG, Dolinski K, Owen AB, Altman RB, and Botstein D. A Bayesian framework for combining heterogeneous data sources for gene function prediction (in S. cerevisiae). Proc Natl Acad Sci USA 100(14): 8348-53, 2003. Myers CL, Robson D, Wible A, Hibbs MA, Chiriac C, Theesfeld CL, Dolinski K, Troyanskaya OG. Discovery of biological networks from diverse functional genomic data. Genome Biology6(13):R114, 2005. Russell S, Norvig P (1995) Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Englewood Cliffs, New Jersey. Chapter 20:Statistical Learning Methods Hastie T, Tibshirani R, Friedman J (2001). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Chapter 8:Model Inference and Averaging. Gold Standard & Data Processing Myers CL, Barrett D, Hibbs MA, Huttenhower C, Troyanskaya OG. Finding function: evaluation methods for functional genomic data. BMC Genomics 2006, 7:187. Ginsburg H. Progress in in silico functional genomics: the malaria Metabolic Pathways database. Trends Parasitol. 2006 Jun;22(6):238-40. Storey JD, Xiao W, Leek JT, Tompkins RG, and Davis RW. (2005) Significance analysis of time course microarray experiments. Proceedings of the National Academy of Sciences, 102: 12837-12842. Plasmodium Gardner MJ, Hall N, Fung E, White O, et al. Genome sequence of the human malaria parasite Plasmodium falciparum. Nature. 2002 Oct 3;419(6906):498-511. Bozdech Z, Llinas M, Pulliam BL, Wong ED, Zhu J, DeRisi JL. The transcriptome of the intraerythrocytic developmental cycle of Plasmodium falciparum. PLoS Biol. 2003 Oct;1(1):E5.

1 0

W Dong general exam
by Melissa M Lawson 03 May '07

03 May '07

Wei Dong will present his research seminar/general exam on Wednesday May 9 at 2PM in Room 301 (note room!) The members of his committee are: Kai Li (advisor), Moses Charikar, and Andrea LaPaugh. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His final abstract and reading list appear below. ---------------------------------------- Abstract K-Nearest Neighbor (K-NN) search on high dimensional feature vectors is the principal problem underlying content based similarity search systems. The recently developed Locality Sensitive Hashing approach has advantages over traditional space partitioning methods, which suffer from the curse of dimensionality. In this project we aim at addressing some practical issues when applying LSH to a real system. First, we propose an LSH based compact representation of feature vectors (aka sketch). We have been using main memory indices of feature vectors to reduce access time. By keeping sketches in place of the original feature vectors, we can significantly reduce the memory overhead and maintain high precision and low query time. Second, we study the geometric and statistical characteristics of different data sets and identify some common properties with a set of associated parameters. Basing on that we build a performance model of LSH, making it possible to tune the parameters of LSH automatically. Finally, we show that local geometric properties have a non-trivial impact on query results. A fixed set of parameters optimized for the global average can still yield poor results on some of the queries. We address this problem by adaptively guiding the search process of each query using partial results seen so far. Reading List Text book: Tanenbaum, Modern Operating Systems Hector Garcia, Jeffrey Ullman, Jennifer Widom, Database Systems The Complete Book, Chapter 11-14 Papers: Bohm, C.; Berchtold, S. & Keim, D. A. (2001), 'Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases', /ACM Comput. Surv./ *33*(3), 322--373. Bawa, M.; Condie, T. & Ganesan, P. (2005),LSH forest: self-tuning indexes for similarity search, /in /'WWW '05: Proceedings of the 14th international conference on World Wide Web', ACM Press, New York, NY, USA, pp. 651--660. Datar, M.; Immorlica, N.; Indyk, P. & Mirrokni, V. S. (2004),Locality-sensitive hashing scheme based on p-stable distributions, /in /'SCG '04: Proceedings of the twentieth annual symposium on Computational geometry', ACM Press, New York, NY, USA, pp. 253--262. Indyk, P. & Motwani, R. (1998),Approximate nearest neighbors: towards removing the curse of dimensionality, /in /'STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing', ACM Press, New York, NY, USA, pp. 604--613. Lv, Q.; Josephson, W.; Wang, Z.; Charikar, M.; Li, K.(2006) Efficient Filtering with Sketches in the Ferret Toolkit. In Proceedings of the 8th ACM SIGMM International Workshop on Multimedia Information Retrieval (MIR). Santa Barbara, CA, USA. October 2006. Lv, Q.; Josephson, W.; Wang, Z.; Charikar, M.; Li, K.(2006) A Time-Space Efficient Locality Sensitive Hashing Method for Similarity Search in High Dimensions. Technical report. ftp://ftp.cs.princeton.edu/techreports/2006/759.pdf Panigrahy, R. (2006),Entropy based nearest neighbor search in high dimensions, /in /'SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm', ACM Press, New York, NY, USA, pp. 1186--1195. Weber, R.; Schek, H. & Blott, S. (1998),A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, /in /'VLDB '98: Proceedings of the 24rd International Conference on Very Large Data Bases', Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 194--205. Henzinger, M. 2006. Finding near-duplicate web pages: a large-scale evaluation of algorithms. In Proceedings of the 29th Annual international ACM SIGIR Conference on Research and Development in information Retrieval

1 0

Princeton Neuroscience Seminar Thursday May 3 4:30pm, by Fei-Fei Li
by Fei-Fei Li 02 May '07

02 May '07

Hi all, I'm giving a Neuroscience Seminar tomorrow (Thursday) at 4:30pm (details below). I'd like to invite all of you to come. There will be a reception afterward. Fei-Fei p.s. According to the email below, I'll try to dress up like a man. ;) -------- Original Message -------- Subject: Fei Fei Li TOMORROW Date: Wed, 2 May 2007 09:06:48 -0400 From: Burnham, Leland <lburnham(a)Princeton.EDU> Reply-To: Burnham, Leland <lburnham(a)Princeton.EDU> To: neuroscience(a)Princeton.EDU Dr. Fei-Fei Li, Department of Computer Science, Princeton University, is the Neuroscience speaker *TOMORROW*, *_Thursday, _* *_May 3_* in Green Hall, Room O-S-6. Seminar time is 4:30 p.m. The title of his presentation is "Natural Scene Categorization: attention, recognition and neural decoding." A reception will follow the seminar in Green Hall 2-C-18. -- --------------------------------------------- Li, Fei-Fei Ph.D. (publish under L. Fei-Fei) Assistant Professor Computer Science Dept. Princeton University 35 Olden St. Princeton, NJ 08540 Tel: (609)258-8130 Office: Room 211, CS Building Website: http://vision.cs.princeton.edu ---------------------------------------------

1 0

W Mulzer general exam
by Melissa M Lawson 27 Apr '07

27 Apr '07

Wolfgang Mulzer will present his research seminar/general exam on Wednesday May 2 at 2PM in Room 402. The members of his committee are Bernard Chazelle (advisor), Bob Tarjan, 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: In recent years, algorithm designers have been confronted with the task of developing algorithms that must be able to cope with larger and larger amounts of data. Traditional algorithms based on worst-case analysis show limitationsand new approaches, more focused on data are called for. The data we encounter in practice tends to have more structure than is usually assumed by traditional worst-case approaches, and it might be possible to exploit this additional structure to design better algorithms for classical problems. As an example, we consider the classical UNION-SPLIT-FIND-problem in which we need to maintain a dynamic set S of elements from an ordered universe and to efficiently find the successor in S of any given element in the universe. This problem has been widely studied in the literature and there are optimal algorithms for it both in the pointer-machine and the RAM model of computation. We add the following twist: Instead of allowing arbitrary operations on the set S, we are given a directed graph G of constant degree whose nodes are labeled with queries to the data structure. Any query sequence is generated by a walk in G. We give a simple algorithm that answers all queries in constant time with sub-quadratic space for the case that G is a path. We investigate whether, for more complicated graphs, the classical lower bounds might still hold. Reading List: K. Mehlhorn, S. Naeher, H. Alt. A lower bound on the complexity of the union-split-find problem. SICOMP 17(6), 1988 H. Gabow, R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union. JCSS 30(2), 1985. J. La Poutre. Lower bounds for the union-find and split-find problem on pointer machines. STOC 1990 C. Kenyon and V. King. On boolean decision trees with faulty nodes. Random Structures and Algorithms 5(3), 1994. M. Fredman. How good is the information theory bound in sorting. Theoretical Computer Science 1, 1976. M. Mitzenmacher, E. Upfal, Probability and Computing, Chapters 7, 9, 11 R. Motwani, P. Raghavan, Randomized Algorithms, Chapters 6, 8, 13 M. de Berg, M. van Kreveld, M. Overmars, O. Scharzkopf, Computational Geometry: Algorithms and Applications, Chapter 11

1 0

cookies
by Ginny Hogan 26 Apr '07

26 Apr '07

Cookies are now available in the tea room -

1 0

K Makarychev preFPO
by Melissa M Lawson 26 Apr '07

26 Apr '07

Konstantin Makarychev will present his preFPO on Tuesday, May 1 at 11am in room 302 (note room). The members his committee are: Moses Charikar (advisor), Boaz Barak and Assaf Naor (NYU) (readers), Bernard Chazelle and Robert Tarjan (non-readers). Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------------- Title: Quadratic Forms on Graphs and Their Applications Abstract: We introduce a new graph parameter, called the Grothendieck constant of a graph, which is defined as the (worst case) integrality gap of the semidefinite relaxation for the problem of maximizing of a certain quadratic form (which depends on the graph). This problem arises in several applications including the study of correlation clustering and the investigation of the spin glass model. We give upper and lower estimates for the Grothendieck constant of a graph G: We show that it is less than O(log T(G)), where T(G) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also prove that the Grothendieck constant is always at least c.log w(G), where w(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices is c.log n. The lower bound for the complete graph also improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions. I will also show how similar methods can be used for finding approximate solutions of constraint satisfaction and graph arrangements problems.

1 0

Speaker Today
by Ginny Hogan 26 Apr '07

26 Apr '07

Ed Nightingale, University of Michigan, will present his talk "Improving the Performance of Highly Reliable Software Systems" at 4:15pm today in Computer Science Room 105 -

1 0

refreshments
by Ginny Hogan 25 Apr '07

25 Apr '07

Refreshments are now available in the tea room

1 0

Y Makarychev preFPO
by Melissa M Lawson 25 Apr '07

25 Apr '07

Yury Makarychev will present his preFPO on Monday April 30 at 2:30PM in Room 402. The members of his committee are: Moses Charikar, advisor; Bernard Chazelle and Assaf Naor (NYU), readers; Boaz Barak and Rob Schapire, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ================================================================== Title: Approximation Algorithms for Constraint Satisfaction Problems Constraint satisfaction problems (CSP) are very basic and natural combinatorial optimization problems. Given a set of variables and constraints on them, our goal is to satisfy as many constraints as possible. Our interest in constraint satisfaction problems is twofold. First of all, CSPs are good model problems. They are well suited for developing new algorithmic techniques, which can potentially be applied to other problems of interest. Another reason to study CSPs is their importance to complexity theory. Many problems arising in complexity theory such as 3SAT, Unique Games, and Label Cover (which is closely related to PCPs) are constraint satisfaction problems. I will describe approximation algorithms for two constraint satisfaction problems. First, I will talk about the Unique Games Problem. A unique game is a CSP with a "uniqueness" property: each constraint involves two variables and the value of one variable uniquely determines the value of the other. The Unique Games Problem generalizes such problems as MAX CUT and MAX-2-LIN (linear equations mod p with two variables per equation). This problem has recently attracted a lot of attention since hardness of approximation for many problems, such as Sparsest Cut and Vertex Cover, was proved assuming the Unique Games Conjecture. Roughly speaking, this conjecture says that even if almost all constraints in a unique game are satisfiable it is NP-hard to satisfy a small constant fraction of constraints. Unique games pose a great challenge for our existing techniques: Typically, semidefinite programming (SDP) relaxations are well suited for optimization problems involving boolean variables (e.g. MAX CUT). But little is known about how to analyze SDP solutions for problems with larger domains. I will describe several nearly optimal approximation algorithms for the Unique Games Problem. Then I will talk about the Maximum k-CSP problem. In this problem, each constraint is an arbitrary predicate on at most k variables. I will describe approximation algorithms for different ranges of parameters (k and the fraction of unsatisfied constraints in the optimal solution). The algorithms are almost optimal assuming the Unique Games Conjecture. ==================================================================

1 0