- talks - lists.cs.princeton.edu

A Agarwal preFPO
by Melissa M Lawson 08 May '07

08 May '07

Amit Agarwal will present his preFPO on Monday May 14 at 3:30PM in Room 302 (note room!). The members of his committee are: Moses Charikar, advisor; Rob Schapire and Sanjeev Khanna (U Penn), readers; Ken Steiglitz and Bob Tarjan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Optimization has emerged as a field of central importance for its practical applications in operations research, physics, chemistry, applied mathematics, and computer science. As our understanding of optimization has deepened, it has emerged that several important optimization problems are difficult to solve exactly in reasonable amount of time, assuming widely believed complexity assumptions. The natural approach in such cases is to obtain approximate solutions. There is a huge body of work towards designing algorithms with provable guarantees about their sub-optimality. In general, two kinds of error estimation techniques have been evolved for such problems: multiplicative and additive. In the study of approximation algorithms one typically looks for multiplicative approximation to problems which are NP-hard. On the other hand, results in the field of online optimization typically have additive errors. The latter work also has connections to machine learning and statistics. I will present three results in the broad area of approximate optimization: (i) The first result is on improved approximation for directed cut problems from joint work with Noga Alon and Moses Charikar. (ii) The second result bridges the field of approximation algorithms and network coding theory. We show that certain integrality gaps studied by the approximation algorithms community are the same as certain parameters in network coding. This is joint work with Moses Charikar. (iii) Finally we present faster algorithms for online optimization with applications to portfolio management. This is based on papers with Elad Hazan, Robert Schapire, Satyen Kale, and Adam Kalai.

1 0

Q Xi general exam
by Melissa M Lawson 08 May '07

08 May '07

Qian Xi will present her research seminar/general exam on Monday May 14 at 10:30AM in Room 402. The members of her committee are JP Singh (advisor), David August, 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. ----------------------------------------------------------------------------- Abstract: Writing multi-threaded programs on chip multi-processors is a challenge. Because of the runtime unpredictability, access to shared data should be arranged carefully to guarantee correctness and efficiency. Lock-based mechanisms are conventional ways to provide mutual exclusion, but locks aren't easy to manage and they can cause serious problems such as deadlock. Maurice Herlihy et al. proposed a lock-free data structure called Transactional Memory (TM) to eliminate the problems induced by locks. TM systems have received a lot of interest recently due to advent of multi-core processors, and due to a widespread belief that TM provides a higher-level and less error-prone parallel programming model than locks, while still achieving comparable performance. Most TM implementations have used toy or kernel benchmarks to measure performance, and almost exclusively small data structures. This benchmarks gave little insight into how real applications will behave with TM. In this project, we present a CMP benchmark suite implemented in software TM (STM), containing both kernel and real application level programs, from scientific computing and multimedia domains. We aim not only to understand performance profiles under STM relative to the more conventional threads+locks programming model, but more importantly, to understand whether STM is a preferable interface for programming on CMP. In the current experimental study, we find that STM achieves good performance, nearly the same as lock-based mechanisms, for small sizes of shared data. On the other hand, programs with large shared data size incur a loss of performance for several reasons in STM. Then, from a programmer's aspect of view, we summarize the benefits and drawbacks of current STM systems while writing parallel programs. We also compare interfaces of different STM implementations and comment on appropriate STM primitives for parallel programming. Readling list: Book: David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach (2nd edition) Papers: - Maurice Herlihy, J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. Proceedings of the 20th International Symposium in Computer Architecture, 1993, pp. 289300. - Nir Shavit, Dan Touitou. Software Transactional Memory. Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing , 1995, pp. 204-213. - Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang. The Case for a Single-Chip Multiprocessor. ACM SIGOPS Operating Systems Review, 1996, pp. 2-10. - Austen McDonald et al. Characterization of TCC on Chip-Multiprocessors. Proceedings of the 14th International Conference on Parallel Architecture and Compilation Techniques, 2005. - Kevin E. Moore et al. LogTM: Log-based Transactional Memory. Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture, 2006. - Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. Composable Memory Transactions. ACM Conference on Principles and Practice of Parallel Programming 2005. - Maurice Herlihy, Victor Luchangco, Mark Moir, William Scherer. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2003. - Austen McDonald et al. Architectural Semantics for Practical Transactional Memory. Proceedings of the 33rd annual international symposium on Computer Architecture, 2006.

1 0

X Ma general exam
by Melissa M Lawson 03 May '07

03 May '07

Xiaojuan Ma will present her research seminar/general exam on Wednesday May 9 at 10 AM in Room 301 (note room!). The members of her committee are Fei-Fei Li, Szymon Rusinkiewicz, Tom Funkhouser. Her advisor is Perry Cook. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------------------- Abstract: Assistive devices and tools for persons with aphasia, a debilitating condition that robs an individual of the ability to communicate, have traditionally depended on icons to convey the meaning of words that the individuals have lost. Despite the predominant use of icons, which are created by artists, speech language pathologists suggest that personal digital photographs may be easier for people to map to the real phenomena. Also, compared to other visual art resources such as icons, images are cheaper, ubiquitous, numerous, and varied. A concept of picture-as-language, which uses digital photographs as a language has shown some significant and long-lasting effects on the learning for people with mental retardation, developmental disabilities, or learning disabilities. Designing for a population that relies heavily on picture representations, it is important to understand to what extent the choice of icons and images affects the adoption and usability of assistive technology. A study with unimpaired members of an older demographic likely to be affected by aphasia shows that, for sentences with words replaced by either images or icons, the word-level and sentence-level meaning are retained equally well for both images and icons. It is also supported by a further study with our target group, people with aphasia, on the effectiveness of icons and images on conveying noun concepts. However, compared to concrete nouns, both studies showed that neither icons or images performed as well on abstract nouns. What's more, the study with senior citizens revealed that both icons and images did a poor job of embodying verbs and attributes. A third study evaluating the efficacy of four different visual representations of verbs for subjects from the general population addressed the question of the best representation of both motion and abstract verbs. Related video and image database for verb illustrations is under construction. Books: Preece, J., Rogers, Y., and Sharp, H. Interaction Design: Beyond Human-Computer Interaction. New York: John Wiley & Sons, Inc., 2002. Shneiderman, B. Designing the User Interface: Strategies for Effective Human-Computer Interaction. Boston: Addison Wesley, 1997. Chapters: 1-4, 10, 11 Papers: Newell A.F., Carmichael, A., Gregor, P., and Alm, N. Information Technology for Cognitive Support. The Human-Computer Interaction Handbook, Jacko, J. and Sears, A. (Editors). Mahwah, NJ: Lawrence Erlbaum Associates, Inc, 2002. 464-481. R. D. Steele, M. Weinrich, R. T. Wertz, M. K. Kleczewska, and G. S. Carlson. Computer-Based Visual Communication in Aphasia. Neuropsychologia, 27(4):409-426, 1989. van de Sandt-Koenderman, M. W. M. E. High-tech AAC and aphasia: widening horizons? Aphasiology (2004), 18 (3), 245-263. Baecker, R., Small, I., and Mander, R. Bringing Icons to Life. Proceedings of CHI '91 Human Factors in Computing Systems. New York: ACM, 1991, pp. 1-6. J. L. Boyd-Graber, S. S. Nikolova, K. A. Moffatt, K. C. Kin, J. Y. Lee, L.W. Mackey, M. M. Tremaine, and M. M. Klawe. Participatory design with proxies: Developing a desktop-PDA system to support people with aphasia. In Proc. CHI2006, pages 151-160. ACM Press, 2006. K. Tee, K. Moffatt, L. Findlater, E. MacGregor, J. Mc-Grenere, B. Purves, and S. S. Fels. A visual recipe book for persons with language impairments. In Proc. CHI 2005, pages 501-510. ACM Press, 2005. Danielsson, H. and Svensk. A. Digital Pictures as Cognitive Assistance. In Proceedings of the 6th European Conference for the Advancement of Assitive Technology, 2001. (5 pages) R. Mihalcea and B. Leong. Toward communicating simple sentences using pictoral representations. In Proc. of the Conf. of the Assoc. for Machine Translation in the Americas 2006, Boston, MA, 2006. T. Takasaki. Pictnet: Semantic infrastructure for pictogram communication. In P. Sojka, K.-S. Choi, C. Fellbaum, and P. Vossen, editors, Proc. Global WordNet Conference 2006, pages 276-289. GlobalWordNet Association, January 2006. Pettersson, Rune. Interpretation of Image Content. Educational Communication and Technology Journal, v36 n1 p45-55 Spr 1988.

1 0

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