- talks - lists.cs.princeton.edu

R Manokaran general exam
by Melissa M Lawson 29 Apr '08

29 Apr '08

Rajsekar Manokaran will present his research seminar/general exam on Monday May 5 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and Boaz Barak. Everyone is welcome 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 appear below. Abstract -------- Mathematical relaxations are one of the most powerful tools used in designing approximation algorithms for hard combinatorial optimization problems. For example, linear programming relaxations have provided the best approximation algorithms known for a huge number of optimization problems. More recently, for some optimization problems, semidefinite relaxations have been used to obtain breakthrough improvements in the approximation factor. This work investigates the limits on approximations achieved by mathematical relaxations of combinatorial optimization problems and their relation to the computation hardness of approximating them. For a small yet quite general set of problems, a direct way to convert integrality gaps for a linear programming relaxation of the problem into a computational hardness result under a certain conjecture is shown. This problem, known as metric labeling is a generalization of classification problems with pairwise constraints. In this work, it is shown that a certain linear programming relaxation gives the best approximation one can expect, assuming the unique games conjecture. Continuing in the same theme, a similar computational hardness result is shown for the maximum acyclic subgraph problem. Here, a trivial algorithm obtains a half approximation and obtaining a better approximation algorithm has been an open problem for quite some time. Assuming the UG conjecture, this work shows that it is computationally hard to approximate the maximum acyclic subgraph problem by a better factor is hard. This result also, unconditionally, rules out a simple semi-definite programming approach to obtain a better approximation. Reading List ------------ 1. Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak Chapters 1-8, 16-19. 2. Approximation Algorithms by Vijay Vazirani Chapters 1-4, 12-21. 3. Expander Flows, Geometric Embeddings, and Graph Partitionings by Sanjeev Arora, Satish Rao, and Umesh Vazirani ACM Symposium on Theory of Computing, 2004. 4. A tight bound on approximating arbitrary metrics by tree metrics by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar ACM Symposium on Theory of Computing, 2003 5. Some Optimal Inapproximability Results by Johan Hastad STOC 1997. 6. Proving integrality gaps without knowing the linear program. by Sanjeev Arora, Bela Bollobas and Laszlo Lovasz. Proc. IEEE Foundations of Computer Science, 2002. 7. Local Global Tradeoffs in Metric Embeddings, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, FOCS 2007, pp. 713-723. 8. On the power of unique 2-prover 1-round games by Subhash Khot STOC '02. 9. Optimal inapproximability results for max-cut and other 2-variable csps? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. FOCS '04. 10. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $L_1$. by Subhash Khot and Nisheeth Vishnoi. FOCS '05. 11. Noise stability of functions with low influences: Invariance and optimality. by Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. FOCS '05. 12. Vertex cover might be hard to approximate to within 2-$\epsilon$. by Subhash Khot and Oded Regev. J. Comput. Syst. Sci. 13. Near-Optimal Algorithms for Unique Games, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, STOC 2006, pp. 205-214. 14. Approximation algorithms for the metric labeling problem via a new linear programming formulation. Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin. SIAM J. Disc. Math. 15. On the advantage over random for maximum acyclic subgraph. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. FOCS 2007, pp. 625-633.

1 0

R Pang FPO
by Melissa M Lawson 28 Apr '08

28 Apr '08

Ruoming Pang will present his FPO on Monday May 5 at 10AM in Room 402. The members of his committee are: Larry Peterson, advisor; Jen Rexford and Vern Paxson (ISCI), readers; Vivek Pai and Brian Kernighan, nonreaders. A copy of his thesis, "Towards Understanding Application Semantics of Network Traffic", is on display in Room 310. Everyone is invited to attend his talk.

1 0

4:30pm Tue Apr 29 talk by Robert Nowak on network inference
by Jennifer Rexford 25 Apr '08

25 Apr '08

*Speaker: *Robert Nowak, Professor of Engineering at the University of Wisconsin-Madison *Date: *Tuesday, April 29th *Time: *4:30pm *Room: *B205 ~ Equad *Title: *Network Inference from Co-Occurrences *Abstract: *The discovery of networks is a fundamental problem arising in numerous fields of science and engineering, including communication systems, biology, sociology, and neuroscience. Unfortunately, it is often difficult to obtain data that directly reveal network structure, and so one must infer a network from incomplete data. This paper considers inferring network structure and transmission pathways from ``co-occurrence'' data; observations that identify which network components (e.g., routers, proteins) carry each transmission but do not indicate the order in which they handle the transmission. Without order information, the number of networks that are consistent with the data grows exponentially with the size of the network. Yet, the basic engineering/ evolutionary principles underlying most networks strongly suggest that not all data-consistent networks are equally likely. In particular, network components that co-occur in many observations are probably closely connected. With this in mind, we model the co-occurrence observations as independent realizations of a random walk on the network graph, subjected to random permutations which account for the lack of order information. The network can be estimated using this model and the Maximum Likelihood (ML) criterion. The computational complexity of direct ML estimation is combinatorial in the size of the network, and so we derive a more efficient approach using an Expectation-Maximization (EM) algorithm. The EM algorithm complexity is combinatorial in the length of the transmission pathways, rather than the size of the entire network. This is a significant improvement, but the computational cost of the EM algorithm is still prohibitive for large networks. For large-scale network inference, we propose a polynomial-time Monte Carlo version of the EM algorithm which is guaranteed to converge with high probability. Applications arising in telecommunications, natural language processing, and systems biology will be discussed. * * *Bio: *Robert Nowak received the B.S. (with highest distinction), M.S., and Ph.D. degrees in electrical engineering from the University of Wisconsin-Madison in 1990, 1992, and 1995, respectively. He was a Postdoctoral Fellow at Rice University in 1995-1996, an Assistant Professor at Michigan State University from 1996-1999, held Assistant and Associate Professor positions at Rice University from 1999-2003, and was a Visiting Professor at INRIA in 2001. Dr. Nowak is now the McFarland-Bascom Professor of Engineering at the University of Wisconsin-Madison. He has served as an Associate Editor for the IEEE Transactions on Image Processing, and is currently an Associate Editor for the ACM Transactions on Sensor Networks and the Secretary of the SIAM Activity Group on Imaging Science. He has also served as a Technical Program Chair for the IEEE Statistical Signal Processing Workshop and the IEEE/ACM International Symposium on Information Processing in Sensor Networks. Dr. Nowak received the General Electric Genius of Invention Award in 1993, the National Science Foundation CAREER Award in 1997, the Army Research Office Young Investigator Program Award in 1999, the Office of Naval Research Young Investigator Program Award in 2000, and IEEE Signal Processing Society Young Author Best Paper Award in 2000. His research interests include statistical signal processing, machine learning, imaging and network science, and applications in communications, bio/medical imaging, and systems biology.

1 0

B Brown FPO
by Melissa M Lawson 24 Apr '08

24 Apr '08

Benedict Brown will present his FPO on Thursday May 1 at 10:30AM in Room 402. The members of his committee are; Szymon Rusinkiewicz, advisor; David Dobkin and Tom Funkhouser, readers; Adam Finkelstein and Ken Steiglitz, nonreaders. A copy of his thesis, "Registration and Matching of Large Geometric Datasets for Cultural Heritage Applications" is on display in Room 310. Everyone is invited to attend his talk.

1 0

1-2pm Wed May 7 talk on learning structured bayesian networks in room 302
by Jennifer Rexford 23 Apr '08

23 Apr '08

Title: *Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Speaker: **Marie desJardins*, University of Maryland Date/time: 1-2pm Wed May 7 Location: room 302 in the CS building Abstract: In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies. BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory. Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj(a)cs.umbc.edu,(410) 455-3967.

1 0

Refreshments
by Ginny Hogan 23 Apr '08

23 Apr '08

Are now available in the tea room - Followed by Umesh Vazirani's talk At 4:30 -

1 0

Talk today - 4:30 - COS 105
by Ginny Hogan 23 Apr '08

23 Apr '08

Umesh Vazirani, UC Berkeley, will present his talk "The Truth about Quantum Computers", at 4:30pm today COS 105 - Tea will be at 3:30pm

1 0

Zhiyan Liu FPO
by Melissa M Lawson 21 Apr '08

21 Apr '08

Zhiyan Liu will present her FPO on Friday April 25 at 1:30PM in Room 302 (note room). The members of her committee are: Kai Li, advisor; Adam Finkelstein and Olga Troyanskaya, readers; Tom Funkhouser and Szymon Rusinkiewicz, nonreaders. A copy of her thesis, "Scalable Isosurface Visualization", is on display in Room 310. Everyone is invited to attend her talk.

1 0

C Huttenhower preFPO
by Melissa M Lawson 18 Apr '08

18 Apr '08

(Please note - talk is in Carl Icahn Lab, Room 200) Curtis Huttenhower will present his preFPO on Friday April 25 at 10AM in Carl Icahn Lab Room 200. The members of his committee are: Olga Troyanskaya, advisor; Mona Singh and Hilary Coller (MOL), readers; Kai Li and David Botstein (MOL/Genomics), nonreaders. Everyone is invited to attend his talk. ----- TITLE: Data mining in large biological data collections ABSTRACT: Modern biology has developed a wealth of high-throughput experimental techniques. Many of these, like whole-genome sequencing, produce measurements simultaneously for every gene in an organism's genome. This means that a single assay can produce tens or hundreds of thousands of structured data points; some assays detect pairwise interactions between genes, squaring the amount of data. Each such genome-scale dataset represents a highly descriptive snapshot of cellular biology. As the number of such datasets reaches the thousands for many organisms, however, new opportunities arise to understand systems-level biology by means of very large scale data integration and analysis. My thesis focuses on three areas of opportunity presented by this situation. First, analysis of single high-throughput datasets is by no means a solved problem: as new experimental assays become available, each resulting dataset reveals new aspects of molecular biology. I will discuss results examining the yeast phosphoproteome by electron transfer dissociation mass spectrometry, which allows global profiling of phosphorylation signaling, as well as a statistical model of the transcriptional response to changes in growth rate. This model is descriptive of yeast biology and can be applied to predict instantaneous growth rates from arbitrary expression measurements (e.g. from other experimental platforms or unicellular organisms). Second, it is critical to extend functional genomic analyses to higher organisms, particularly human beings. This presents both computational and biological challenges: the amount of available experimental data is orders of magnitude larger, the amount of pre-existing biological knowledge is smaller, and the biology of higher eukaryotes is itself substantially more complex. I will discuss HEFalMp, a machine learning system that builds off of our success in yeast to integrate hundreds of genome-scale datasets for functional genomic analysis in human beings. This has enabled new views of gene function, functional relationships, and pathway interactions in human biology. We are currently in the process of experimental followup for several predictions in the human autophagy pathway, and we are planning to extend HEFalMp to more specifically investigate human disease. Finally, the process of experimental data integration for functional genomics can be extended beyond single gene interactions or single organisms. By mining a sufficiently large body of experimental results, purely data-driven relationships can be derived between entire cellular pathways. This captures the complex interplay between pathways and processes at a systems level and can help to describe biological results in terms of their specific functional activity. Furthermore, all of these results can be extended across multiple organisms to study gene and pathway functional changes over the course of evolution. All of these results are made possible by a novel synthesis of large-scale machine learning with genome-scale biological data.

1 0

R. Dondero talk Friday 12:30
by Andrew W. Appel 15 Apr '08

15 Apr '08

Special PLC Seminar on a topic in Software Engineering: Robert Dondero will talk Friday April 18, room 302, at 12:30. [next door to the usual PLC room] Pizza will be provided. If you plan to attend AND you do not usually attend the PLC lunch, e-mail cbell(a)cs.princeton.edu so we order enough food. Predicting Software Change Coupling Robert Dondero Abstract: This project was an exploratory study of techniques for predicting future change coupling among a program's source code files. Two source code files are change coupled if programmers edit them together frequently, and separately infrequently. Specifically, this project investigated the predictive power of three approaches: mining of software change logs, software similarity detection, and software proximity detection. "Software mining" extracts patterns from source code databases, that is, version control systems containing source code and change histories. This project explored whether identification of past change coupling among source code files can predict future change coupling among those files. "Software similarity detection" finds files that contain similar, alias cloned, code. This project explored whether identification of similar code among source code files can predict future change coupling among those files. Finally, "software proximity detection" finds files that reference each other heavily. This project explored whether identification of proximity among source code files can predict future change coupling among those files. This project performed the study applied a software miner (created specifically for this project), three preexisting similarity detectors, and two proximity detectors (created specifically for this project) to four large open source code databases at multiple points in time. It determined that software mining generally generated the best predictions of the three approaches, followed by similarity detection, followed by proximity detection. Excessive source code change coupling can be a serious maintenance problem. So the prediction of future change coupling is an important challenge in software engineering. The results of this project shed light on the abilities of the three approaches, both in the absolute and relative senses, to predict change coupling. So the results of this project hold promise for decreasing program maintenance costs.

1 0