- talks - lists.cs.princeton.edu

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

11am Tue Apr 17 talk on large alphabet probability estimation in B205 in the E-Quad
by Jennifer Rexford 16 Apr '07

16 Apr '07

Speaker: Narayana P.Santhanam, UC Berkeley Date: Tuesday, April 17, 2007 Time: 11:00am Room: B205 ~ EQuad Title: New solution for old problems: Large alphabet probability estimation Abstract: Modern advancements in communication, computation, and storage has made possible complex systems like the Internet as well as helped scientific advances like the Genome project, none of which would have been conceivable when I was born. New advancements bring about new problems. Two aspects of some of these problems have captured my interest. First, a fair number of these problems require solutions for very large alphabets. For instance, language models for speech recognition estimate distributions over English words; thousands of genes are clustered by their expression levels for applications in diagnosis and drug response prediction using the limited number of samples that can be obtained from test subjects. On the other hand, a lot of results in both statistics and information theory assumes that we operate in a regime where the data size is much larger than the alphabet size. We are therefore forced to rework problems where conventional approaches no longer apply. Second, problems posed by different systems are interconnected. For example, consider text compression on the one hand, along with language modeling for speech recognition on the other. The former tries to compress as well as the unknown underlying distribution, the latter estimates word probabilities associated with the unknown underlying distribution. The talk will examine some recent results in the related areas of large alphabet probability estimation and data compression. These results should be seen as a first step towards new solutions for classification, entropy estimation and inference problems arising from modern finance, biology, and data mining. Bio Narayana Santhanam obtained his MS and PhD from the University of California, San Diego in 2003 and 2006 respectively. He currently holds a postdoctoral position in the University of California, Berkeley. He is the recepient of the 2003 Capocelli Prize for student authored papers at the Data Compression Conference and the 2006 IEEE Best Paper Award along with Prof. Alon Orlitsky and Dr. Junan Zhang. His research interests include large alphabet problems, the intersection of information theory and machine learning, and their applications.

1 0