- talks - lists.cs.princeton.edu

reminder: 1-2pm talk today in room 302 on Learning Structured Bayesian Networks by Marie desJardins
by Jennifer Rexford 07 May '08

07 May '08

Speaker: Professor Marie desJardins, University of Maryland Title: Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Date/time: 1-2pm Wednesday May 7 Location: 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

Indranil Gupta talk at 12:30pm today, room 402
by Michael J Freedman 06 May '08

06 May '08

Today, Indranil Gupta from UIUC will be visiting us and speaking at Systems Lunch in room 402 (food at 12:00pm, talk at 12:30pm). The title and abstract of his talk is below. Cheers, --mike ========= Title: Wizards and Fruitflies -- Using Eternal and Ephemeral Overlays for Monitoring Distributed Systems Speaker: Indranil Gupta, Assistant Professor, Department of Computer Science, University of Illinois at Urbana-Champaign Abstract: Many distributed applications running over emerging large-scale distributed infrastructures, such as p2p systems, PlanetLabs and Grids, require the capability to monitor and manage a large distributed set of nodes at run-time. While many solutions exist for network and infrastructure-level monitoring, there is a scarcity of management solutions that work at the level of the distributed application, e.g., for monitoring node availability, count, top-k loaded nodes, querying log-files, etc. At the same time, much work has been done in the community on both persistent overlays such as distributed hash tables (DHTs), as well as unstructured overlays (e.g., Gnutella). However, we find that two alternative, unexplored, and opposing extremes of the design spectrum - eternal and ephemeral overlays - are better suited to solving the above management tasks. We present two systems -- AVMON and MON -- that seek to provide to distributed applications (and deployers) the ability to both monitor long-term availability histories of nodes in a distributed application, as well as to query the group of nodes on the fly. AVMON is a scalable availability monitoring overlay that is resilient to selfish and colluding nodes. AVMON imbues the concept of an eternally persistent (hence eternal) overlay, where peering relationships between nodes, once established, remain forever. Our other system, called MON, allows instant monitoring and management tasks, using the novel concept of an on-demand and short-lived (hence ephemeral) overlay, which survives only for the purpose of an individual management command. Both AVMON and MON are lightweight and fast in terms of memory, computation, bandwidth, and response time. Our mathematical analysis, trace-based simulations, and deployment atop PlanetLab, all demonstrate the practical performance characteristics of these two approaches in systems containing hundreds to thousands of nodes. We touch briefly upon how to use AVMON for building availability-aware services, the usage of MON in PlanetLab, as well as on other instances of eternal and ephemeral overlays we have studied. Speaker Bio: Indranil Gupta is an assistant professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his PhD in Computer Science from Cornell University in 2004. He is a recipient of the NSF CAREER award in 2005. His research group DPRG works on distributed protocols and systems, with applications to large-scale distributed systems such as peer-to-peer systems and sensor networks. DPRG research is funded by several NSF grants, including multi-disciplinary ones. For more information on DPRG, visit http://dprg.cs.uiuc.edu

1 0

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

05 May '08

Qian Xi will present her research seminar/general exam on Tuesday May 13 at 2PM in Room 402. The members of her committee are: David Walker (advisor), David Blei, and Andrea LaPaugh. 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. --------------------------- Ad hoc data sources are semi-structured data sources that are widely used in many research fields, but lack useful data analysis and transformation tools. The goal of the PADS system is to help programmers manipulate ad hoc data sources by providing automatic support for the generation of data processing tools. The tool generation infrastructure has multiple parts in it: (1) a simple tokenization phase (2) a rough data format inference phase (3) a data format refinement phase (4) a tool generation phase One serious limitation of the current implementation involves the tokenization phase. In particular, the current system is unable to handle ambiguous tokens. In this research, we tackle the token ambiguity problem with a more general approach. Two probabilistic models, a character-by-character Hidden Markov Model and a hierarchical model, are established by extracting statistical information from a collection of training data sources, labeled using a tool generated from hand-written descriptions. We show how to incorporate the learned Markov models into the rest of the algorithm to enhance format inference. We will explain the algorithms and implementations behind our new system and we will evaluate its success using a number of measures. Books: - Benjamin C. Pierce: Types and Programming Languages, Chapter 1-11, 13-24. - Stuart J. Russell, Peter Norvig: Artificial Intelligence, A Modern Approach (2nd edition), Chapter 13, 15 (15.1-15.3, 15.6) - Christopher M. Bishop: Pattern Recognition and Machine Learning, Chapter 8, Chapter 13 (13.1-13.2) Papers: - Kathleen Fisher, David Walker, Kenny Q. Zhu, and Peter White. From Dirt to Shovels: Fully Automatic Tool Generation from Ad Hoc Data. Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2008. - Nicholas Kushmerick, Daniel S. Weld, Robert Doorenbos. Wrapper Induction for Information Extraction. International Joint Conference on Artificial Intelligence, 1997. - David Pinto, Andrew McCallum, Xing Wei and W. Bruce Croft. Table Extraction Using Conditional Random Fields. Proceedings of the 2003 annual national conference on Digital government research. - Geert Jan Bex, Frank Neven, Thomas Schwentick, and Karl Tuyls. Inference of concise DTDs from XML data. Proceedings of the 32nd international conference on Very Large Data Bases, 2006. - Vinayak Borkar, Kaustubh Deshmukhy, and Sunita Sarawagiz. Automatic Segmentation of Text into Structured Records. Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001. - Arvind Arasu and Hector Garcia-Molina. Extracting Structured Data From Web Pages. Proceedings of the ACM SIGMOD international conference on Management of data, pages 337¨C348, 2003. - E. M. Gold. Language Identification in the Limit. Information and Control, 1967. - Stephen Soderland. Learning Information Extraction Rules for Semistructured and Free Text. Machine Learning, 1999.

1 0

P Calamia preFPO
by Melissa M Lawson 05 May '08

05 May '08

Paul Calamia will present his preFPO on Tuesday May 13 at 10AM in Room 402. The members of his committee are: Tom Funkhouser, Advisor; Peter Svensson (Norwegian Univ. of Science and Technology) and Perry Cook, Readers; Szymon Rusinkiewicz and Adam Finkelstein, Non-Readers. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Advances in Virtual-Acoustic Simulations through Edge Diffraction and Multiresolution Modeling Abstract: In recent years there has been growing interest in modeling sound propagation in complex, three-dimensional (3D) environments. With diverse applications for the military, the gaming industry, psychoacoustics researchers, architectural acousticians, and others, advances in computing power and 3D audio-rendering techniques have driven research and development aimed at closing the gap between the auralization and visualization of virtual spaces. To this end, this thesis focuses on improving the physical and perceptual realism of sound-field simulations in virtual environments through two distinct approaches: accurate and efficient computation of edge diffraction, and multiresolution modeling. To model sound propagation in virtual environments, acoustical simulation tools commonly rely on geometrical-acoustics (GA) techniques which assume asymptotically high frequencies, large flat surfaces, and ray-like paths. Such techniques can be augmented with diffraction modeling to compensate for the effect of surface size on the strength and directivity of a reflection, to allow for propagation around obstacles and into shadow zones, and to maintain soundfield continuity across reflection and shadow boundaries. Using a time-domain, line-integral diffraction expression known as the Biot-Tolstoy-Medwin (BTM) formulation, this thesis explores various aspects of diffraction calculations for virtual-acoustic simulations. Specifically, we first present analytical approximations for the BTM formulation which allow for accurate numerical computations for receivers at or near shadow and reflection boundaries, locations where the original diffraction integral experiences a singularity. We then describe an edge-subdivision strategy that allows for fast diffraction calculations with low error relative to a numerically more accurate solution. We present a novel method to find GA components using diffraction parameters which ensures continuity at reflection and shadow boundaries. Finally, to address the considerable increase in propagation paths due to diffraction, we describe a simple procedure for identifying and culling insignificant diffraction components during a virtual-acoustic simulation. The secondary thrust of this thesis involves the extension of GA techniques to highly detailed 3D models through a multiresolution approach. Such models, e.g. those created for architectural renderings or resulting from laser scans of building interiors, often exist as noisy meshes that comprise faces which are too small and too numerous for use with GA methods. To address these issues, we have developed a system in which image sources that give rise to specular reflections can be merged using frequency-dependent clustering criteria. The result is a significantly reduced set of aggregate image-sources which characterize a model's geometry and its reflection properties in a frequency-dependent, multiresoultion representation.

1 0

J Jiang general exam
by Melissa M Lawson 05 May '08

05 May '08

Joe Wenjie Jiang will present his research seminar/general exam on Monday May 12 at 10AM in Room 402. The members of his committee are: Jennifer Rexford (advisor), Mung Chiang (ELE), and Michael Freedman. 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. ------------------------------ Title : Cooperative Content Distribution and Traffic Engineering in a Provider Network Traditionally, Internet Service Providers (ISPs) make profit by providing Internet connectivity, while content providers (CPs) play the more lucrative role of delivering content to users. As network connectivity is increasingly a commodity, ISPs have a strong incentive to offer content to their subscribers by deploying their own Content Distribution Networks (CDNs). Running both a CDN and the underlying network presents new opportunities for coordination between server selection (to match servers with subscribers) and traffic engineering (to select efficient routes for the traffic). In this work, we utilize a mathematical framework to show that separating server selection and traffic engineering leads to a sub-optimal equilibrium, even when the CDN is given accurate and timely information about network conditions. Leveraging ideas from cooperative game theory, we propose that the system implements a Nash bargaining solution that significantly improves the fairness and efficiency of the joint system. This study is another step towards a systematic understanding of the interactions between those who generate and distribute contents and those who provide and operate networks. Reading List Textbook [1] L. Peterson and B. Davie, Computer Networks: A Systems Approach, 3rd edition, Morgan Kaufmann Publishers, May 2003. Research papers: [1] D. Clark, "The design philosophy of the DARPA Internet protocols," ACM SIGCOMM Computer Communication Review, Vol. 18, No. 4, pp. 106-114, Aug. 1988. [2] T. Karagiannis, P. Rodriguez and K. Papagiannaki, "Should Internet Service Providers fear peer-assisted content distribution", IMC'05: Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, pp. 6-6, 2005. [3] A. Su, D. R. Choffnes, A. Kuzmanovic and F. Bustamante, "Drafting behind Akamai (Travelocity-based detouring)", SIGCOMM 2006, pp. 435-446, 2006. [4] M. Garetto, D. R. Figueiredo, R. Gaeta and M. Sereno, "A modeling framework to understand the tussle between ISPs and peer-to-peer file-sharing users", Performance Evaluation, vol. 64, no. 9-12, pp. 819-837, 2007. [5] V. Aggarwal, A. Feldmann and C. Scheideler, "Can ISPS and P2P users cooperate for improved performance?", ACM SIGCOMM Computer Communication Review, vol. 37, no. 3, pp. 29-40, 2007. [6] H. Xie, A, Krishnamurthy, A. Silberschatz and Y. R. Yang, "P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers", P4P Working Group position paper. [7] C. Huang, J. Li and K. W. Ross, "Can Internet video-on-demand be profitable?", SIGCOMM'07, pp. 133-144, 2007. [8] M. J. Freedman, C. Aperjis and R. Johari, "Prices are Right: Managing resources and incentives in peer-assisted content distribution", in submission. [9] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, I. Stoica, "A Data-Oriented (and Beyond) Network Architecture", SIGCOMM'07, pp. 181-192, 2007. [10] M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, "SplitStream: High-bandwidth content distribution in a cooperative environment", ACM SOSP'03. [11] Antony I. T. Rowstron and Peter Druschel, "Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems", Middleware '01: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, pp. 329-350, 2001. [12] M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy and A. Venkataramani, "Do incentives build robustness in BitTorrent?", NSDI'07.

1 0

1-2pm Wed May 7 talk on Learning Structured Bayesian Networks by Marie desJardins
by Jennifer Rexford 04 May '08

04 May '08

Speaker: Professor Marie desJardins, University of Maryland Title: *Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Date/time: 1-2pm Wednesday May 7 Location: 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

B Zeller general exam
by Melissa M Lawson 02 May '08

02 May '08

Bill Zeller will present his research seminar/general exam on Monday May 12 at 2PM in Room 402. The members of his committee are: Ed Felten (advisor), Brian Kernighan, and Andrew Appel. 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: Cross-Site Request Forgery (CSRF) attacks occur when a malicious web site causes a user's web browser to perform an unwanted action on a trusted site. These attacks have been called the "sleeping giant" of web-based vulnerabilities, because many sites on the Internet fail to protect against them and because they have been largely ignored by the web development and security communities. We present four serious CSRF vulnerabilities we have discovered on four major sites, including what we believe is the first published attack involving a financial institution. These vulnerabilities allow an attacker to transfer money out of user bank accounts, harvest user email addresses, violate user privacy and compromise user accounts. We recommend server-side changes (which we have implemented) that are able to completely protect a site from CSRF attacks. We also describe the features a server-side solution should have (the lack of which has caused CSRF protections to unnecessarily break typical web browsing behavior). Additionally, we have implemented a client-side browser plugin that can protect users from certain types of CSRF attacks even if a site has not taken steps to protect itself. Books: - Practical Cryptography: Ferguson, Schneier - Security Engineering: Anderson Papers - [Anupam, Mayer] Security of Web Browser Scripting Languages: Vulnerabilities, Attacks, and Remedies http://delivery.acm.org/10.1145/1270000/1267564/p15-anupam.pdf?key1=1267564 <http://delivery.acm.org/10.1145/1270000/1267564/p15-anupam.pdf?key1=1267564… 21&coll=GUIDE&dl=GUIDE&CFID=57632849&CFTOKEN=53175682> &key2=7559754021&coll=GUIDE&dl=GUIDE&CFID=57632849&CFTOKEN=53175682 - [Fu, Sit, Smith, Feamster] Dos and Don'ts of Client Authentication on the Web http://pdos.csail.mit.edu/papers/webauth:sec10.pdf - [Krannig] Towards Web Security Using PLASMA http://delivery.acm.org/10.1145/1270000/1267563/p14-krannig.pdf?key1=1267563 <http://delivery.acm.org/10.1145/1270000/1267563/p14-krannig.pdf?key1=126756… 021&coll=GUIDE&dl=GUIDE&CFID=57633385&CFTOKEN=26863737> &key2=0389754021&coll=GUIDE&dl=GUIDE&CFID=57633385&CFTOKEN=26863737 - [Moore, Voelker, Savage] Inferring Internet Denial-of-Service Activity http://www.caida.org/publications/papers/2001/BackScatter/usenixsecurity01.… - [Huang, Yu, Christian Hang, Tsai, Lee, Kuo] Securing Web Application Code by Static Analysis and Runtime Protection http://www.cs.ucsb.edu/~yuf/paper/WWW04.pdf <http://www.cs.ucsb.edu/%7Eyuf/paper/WWW04.pdf> - [Bortz, Boneh, Nandy] Exposing Private Information by Timing Web Applications http://crypto.stanford.edu/~abortz/papers/timingweb.pdf <http://crypto.stanford.edu/%7Eabortz/papers/timingweb.pdf> - [Boyd, Keromytis] SQLrand: Preventing SQL Injection Attacks http://www1.cs.columbia.edu/~angelos/Papers/sqlrand.pdf <http://www1.cs.columbia.edu/%7Eangelos/Papers/sqlrand.pdf> - [Chou, Ledesma, Teraguchi, Boneh, Mitchell] Client-side defense against web-based identity theft http://crypto.stanford.edu/SpoofGuard/webspoof.pdf - [Xie, Aiken] Static Detection of Security Vulnerabilities in Scripting Languages http://theory.stanford.edu/~aiken/publications/papers/usenix06.pdf <http://theory.stanford.edu/%7Eaiken/publications/papers/usenix06.pdf> - [Vogt, Nentwich, Jovanovic, Kirda, Kruegel, Vigna] Cross-Site Scripting Prevention with Dynamic Data Tainting and Static Analysis http://www.seclab.tuwien.ac.at/papers/xss_prevention.pdf - [Ye, Smith] Trusted Paths for Browsers http://delivery.acm.org/10.1145/1070000/1065546/p153-ye.pdf?key1=1065546 <http://delivery.acm.org/10.1145/1070000/1065546/p153-ye.pdf?key1=1065546&ke… coll=GUIDE&dl=GUIDE&CFID=57635236&CFTOKEN=42774008> &key2=3080854021&coll=GUIDE&dl=GUIDE&CFID=57635236&CFTOKEN=42774008

1 0

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