April 2007 - talks - lists.cs.princeton.edu

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

Speaker Today
by Ginny Hogan 25 Apr '07

25 Apr '07

Tapan Parikh, University of Washington, will present His talk "Designing Appropriate Computing Technologies for the Rural Developing World" at 4:15pm today ,Computer Science Room 105 -

1 0

Andrew Birrell's talk in room 105 this monday at 1:30-3pm
by Kai Li 21 Apr '07

21 Apr '07

Dr. Andrew Birrell will be giving a talk at the parallel architecture and programming course in room 105 this Monday from 1:30 to 3pm. This talk is open to everyone (see the talk abstract below). Andrew is an early key member of the Xerox Parc CSL where Altos PC was invented. His best known projects and publications include Grapevine (1981, which included the first distributed naming system); his paper with Bruce Nelson about implementing RPC (1983, for which they received the 1994 ACM Software System Award); and his paper on programming with threads (1989). ------------------ Mutual Exclusion: Some History, Some Problems, and a Glimmer of Hope Andrew Birrell and Michael Isard Microsoft Research In common with many system researchers, we have been worrying about how mainstream programmers will be able to write concurrent programs: concurrent programs that work correctly, that take appropriate advantage of multiple processors, and that will continue to work correctly after the superstar programmers move on to their next project. Obviously, the motivation for this comes from the increasing use of interactive applications that use web-based services, and from the advent and prospect of increasingly parallel mainstream computers. Our worry has taken two forms, both of which will be explored in the talk. First, we have looked back at the historical development of concurrent programming, to try to understand the decisions that led us to our present state-of-the-art. Second, we are looking forward to techniques that have promise to correct the present dismal state. We hypothesize that by reducing or eliminating the requirement for programmers to write explicit mutual exclusion code, we can make progress. We present techniques that hold promise in this direction, including a new proposal that we call "Automatic Mutual Exclusion".

1 0

refreshments
by Ginny Hogan 18 Apr '07

18 Apr '07

Cookies are now available in the tea room -

1 0

Speaker Today
by Ginny Hogan 18 Apr '07

18 Apr '07

Junfeng Yang, Stanford, will present his talk "Explode: a lightweight, General System for Finding Serious Storage System Errors", at 4:15pm today - Computer Science Room 105 - Tea will be at 3:45pm -

1 0