May 2008 - talks - lists.cs.princeton.edu

J Deng general exam
by Melissa M Lawson 02 May '08

02 May '08

Jia Deng will present his research seminar/general exam on Thursday May 8 at 1PM in Room 402. The members of his committee are: Kai Li (advisor), Fei-Fei Li, 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: Constructing ImageNet Data sets are essential in computer vision and content based image retrieval research. We present the work in progress for constructing ImageNet, a large scale image data set based on the Princeton WordNet. The goal is to associate more than 1000 clean images with each node of WordNet, which consists of ~30,000 ( estimated ) imagable nodes. We build a prototype system for constructing ImageNet, as a first step toward large scale deployment. For each node of WordNet, which is a synonym set (synset) for a single concept, we collect candidate images from the Internet and clean up them with semi-automatic labeling. We train boosting classifiers from human labeled data and use active learning to substantially speed up the labeling process. We also developed a web interface for massive online human labeling. We demonstrate the effectiveness of our system with results from a subset of synsets. Reading list: Text book: Pattern Recognition and Machine Learning, Christopher M. Bishop, 2006. Chapter 1,2,8,14. Modern Operating System, Tanenbaum. Papers: Animals on the Web, Berg, Forsyth, CVPR06 OPTIMOL: automatic Online Picture collecTion via Incremental MOdel Learning, Li, Wang, Fei-Fei, CVPR07 Learning Object Categories from Google's image Search, Fergus, Fei-Fei, Perona, Zissermaman, ICCV05 Harvesting Image Databases from the Web, Scroff, Zisserman, ICCV07 >From Aardvark to Zorro: A Benchmark of Mammal Images, Fink, Ullman, >NIPS05 Tiny Images, Torralba, Fergus, Freeman, TechReport MIT, 2007 Labeling Images with a Computer Game. Luis von Ahn and Laura Dabbish, CHI04 LabelMe: a database and web-based tool for image annotation, Russell, Torralba, IJCV07 Introduction to a large scale general purpose groundtruth dataset: methodology, annotation tool, and benchmarks, Z.Y. Yao, X. Yang, and S.C. Zhu, EMMCVPR07 Combining active and semi-supervised learning for spoken language understanding, Tur, Hakkani-Tur, Schapire, Speech Communication, 05 Online boosting and vision, CVPR06

1 0

4-5pm Wed May 14 talk on Building a Strong Foundation for the Future Internet
by Jennifer Rexford 02 May '08

02 May '08

[Note: In a couple of weeks, I'm giving an invited talk on "building a strong foundation for the future Internet" at the 2008 Symposium on the Theory of Computing (http://webhome.csc.uvic.ca/~stoc2008/). The talk below is a dry-run of that talk. I'd be very happy to hear your feedback on the presentation.] Title: Building a Strong Foundation for the Future Internet Speaker: Jennifer Rexford, Princeton University Date/time: 4-5pm Wednesday May 14 Location: COS 105 (small auditorium) Abstract: The Internet is unquestionably a tremendous success---a research experiment that truly escaped from the lab. However, the Internet faces many technical challenges that, while deeply rooted in early design decisions, have grown even more complex as the network has evolved into a world-wide commercial infrastructure. In this talk, we argue that perhaps the most important goal for a future Internet is the ability to define, model, and analyze it precisely, so we can make stronger statements about its basic properties. Using Internet routing as a driving example, we discuss the research challenges in designing protocols that are simultaneously programmable (so they are flexible and can evolve over time) and perform well in a competitive economic environment (where different parts of the system are controlled by parties with different, sometimes conflicting, objectives). We believe that answering these fundamental questions presents a wonderful opportunity for theoretical research in computer science, electrical engineering, economics, and mathematics.

1 0

M Bateni general exam
by Melissa M Lawson 01 May '08

01 May '08

Mohammad Hossein Bateni will present his research seminar/general exam on Thursday May 8 at 3PM in room 402. The member of his committee are: Moses Charikar (advisor), Bob Tarjan, and Sanjeev Arora. 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---------- Consider a resource allocation problem where we have a set of $m$ indivisible items to be distributed amongst $n$ players, each item going to exactly one person. The value of item $j$ for player $i$ is given by a nonnegative quantity $p_{ij}$, and let us assume that the values for sets of items are additive. The problem of minimizing the maximum value received by a player corresponds to the classic makespan minimization problem. Recently, this problem has received renewed attention under the MaxMin objective function, the goal being to find an allocation that maximizes the minimum value received by a player. There is a large gap in our current understanding of this problem. The best known algorithm achieves a $\tilde{O}(\sqrt{n})$ approximation ratio, but only a factor $2$ hardness result is known. Better algorithms are known when each item has an intrinsic value and a player is only interested in a subset of items, i.e., $p_{ij} \in \{0,p_j\}$. In this work, we consider the bounded-degree case when each item has nonzero value for at most $B$ players. We show that $B = 3$ is as hard as the general problem. We give a factor $4$ approximation algorithm when $B=2$. This is the only case we know of when items can have different nonzero valuations that admits better than a $\tilde{O}(\sqrt{n})$-approximation. The degree two case remains factor $2$ inapproximable, even if each item has the same value for both players interested in it. We also give a simpler LP that is equivalent in power to the Configuration LP that has been instrumental in recent progress on the problem. We identify a non-trivial special case where the Configuration LP still has a large $n^{\Omega(1)}$ integrality gap, but for which we are able to get a polylogarithmic approximation ratio via a careful strengthening and rounding of the LP. ========== And this is my reading list. ------------Books------------------ (1) Algorithm Design by Jon Kleinberg and Eva Tardos. The whole book. (2) Approximation Algorithms by Vijay V. Vazirani. Chapters 1-17. 1 Introduction Part I. Combinatorial Algorithms 2 Set Cover 3 Steiner Tree and TSP 4 Multiway Cut and k-Cut 5 k-Center 6 Feedback Vertex Set 7 Shortest Superstring 8 Knapsack 9 Bin Packing 10 Minimum Makespan Scheduling 11 Euclidean TSP Part II. LP-Based Algorithms 12 Introduction to LP-Duality 93 13 Set Cover via Dual Fitting 14 Rounding Applied to Set Cover 15 Set Cover via the Primal-Dual Schema 16 Maximum Satisfiability 17 Scheduling on Unrelated Parallel Machines (3) Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Chapters 1-6. 1 Introduction 2 Game-Theoretic Techniques 3 Moments and Deviations 4 Tail Inequalities 5 The Probabilistic Method 6 Markov Chains and Random Walks ----------Research Papers------------- [1] Noga Alon and Yossi Azar and Gerhard J. Woeginger and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Computing, 1(1):55-66, 1998. [2] Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. STOC 2007. [3] Nikhil Bansal and Maxim Sviridenko. The santa claus problem. STOC 2006. [4] Ivona Bezakova and Varsha Dani. Allocating indivisible goods. SIGecom Exchange, 5(3):11-18, 2005. [5] Tomas Ebenlendr, Marek Krcal and Jiri Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. SODA 2008. [6] Uriel Feige. On allocations that maximize fairness. SODA 2008. [7] Subhash Khot and Ashok Kumar Ponnunswami. Approximation algorithms for the max-min allocation problem. APPROX 2007. [8] David Golovin. Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, 2005. [9] Jan Karel Lenstra, David B. Shmoys and Eva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259-271, 1990. [10] David B. Shmoys and Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming 62:461-474, 1993. =============================

1 0

B Guo FPO
by Melissa M Lawson 01 May '08

01 May '08

Bolei Guo will present her FPO on Thursday May 8 at 9AM in Room 302 (note room). The members of her committee are: David August, advisor; Andrew Appel and Michael Hind (IBM), readers; Brian Kernighan and Vivek Pai, nonreaders. A copy of her thesis, "Shape Analysis with Inductive Recursion Synthesis", is on display in Room 310. Everyone is invited to attend her talk.

1 0