SUNMONTUEWEDTHUFRISAT
Conferences, Lectures, & Seminars
Events for October
-
CS Colloquium
Tue, Oct 05, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Maxim Sviridenko , IBM Watson
Talk Title: Local Search Algorithms for Submodular Maximization
Abstract: We study the problem of maximizing a submodular function over the intersection of k matroids (for a constant k>=2). Submodular-function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including Max Cut in digraphs, graphs and hypergraphs, certain constraint satisfaction problems, maximum-entropy sampling, and maximum facility-location problems.
Our main result is that for any k>=2 and any epsilon>0, there is a natural local-search algorithm which has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves a 1/(k+1)-approximation of Nemhauser, Wolsey and Fisher from 1978. For maximizing a linear function over k matroids, we obtain a 1/(k-1+epsilon)-approximation, improving a previously known 1/k-approximation. Our analysis can be applied even to general non-monotone submodular maximization subject to k matroid constraints. We show that in this case the approximation guarantee of our algorithm is 1/(k+1+1/(k-1)+epsilon), improving the previously known factor of 1/(k+2+1/k+epsilon).
Biography: Maxim Sviridenko is a research stuff member in the Algorithms group of the Optimization Center in the Department of Business Analytics and Mathematical Sciences of the IBM T.J. Watson Research Center. He received his Ph.D. in Applied Mathematics and Computer Science from the Sobolev Institute of Mathematics (Russia) in 1999. After that he held two postdoc positions: in the Department of Commerce and Business Administration (UBC, Canada) and Computer Science Department at the University of Aarhus Denmark) before joining IBM Research in 2000. His research interests include design and analysis of algorithms for discrete optimization problems, computational complexity, integer and linear programming, modelling real-life optimization problems arising in various industrial applications and developing algorithms to solve such problems. Recently, he has been working on analyzing the local search algorithms that is one of the most popular approaches to solve optimization problems in practice.
Host: Dr. David Kempe
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Oct 07, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Andrea Richa , Arizona State University
Talk Title: A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks
Abstract: In this paper we consider the problem of designing a medium access control
(MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel.
This is joint work with Christian Scheideler (University of Paderborn, Germany) and Baruch Awerbuch (John Hopkins University).
Biography: Prof. Andrea W. Richa is an Associate Professor at the Department of Computer Science and Engineering at Arizona State University since August 2004. She joined this department as an Assistant Professor in August 1998. Prof. Richa received her M.S. and Ph.D. degrees from the School of Computer Science at Carnegie Mellon University, in 1995 and 1998, respectively. She also earned an M.S. degree in Computer Systems from the Graduate School in Engineering (COPPE), and a B.S. degree in Computer Science, both at the Federal University of Rio de Janeiro, Brazil, in 1992 and 1990, respectively. Prof. Richa's main area of research is in network algorithms. For more information, please visit http://www.public.asu.edu/~aricha
Host: Prof. Shang-Hua Teng
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Mon, Oct 18, 2010 @ 04:00 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Vince Conitzer, Duke University
Talk Title: Computational Methods for Acting Strategically
Abstract: Abstract:
Game theory concerns settings where multiple self-interested agents (e.g., people or software agents) interact in the same environment. It attempts to describe the actions that rational strategic agents will take. Many successful real-world applications of game theory are in the context of designing a system or mechanism, for example, the design of the auctions used by major search engines to allocate advertisement slots. Game theory can be used to optimize the design, taking the strategic behavior of the agents (bidders) into account.
However, a different type of application of game theory is to design a decision support tool for one of the agents in the game. For example, we may wish to help a security force to allocate its resources strategically to defend against an attacker. Because the details of the strategic setting will vary across time and across users, computational considerations are paramount: we need algorithms that can take arbitrary games as input. Moreover, due to the ambiguities of game theory, it is not clear that we can restrict attention to a single computational problem. For example, an algorithm for computing a single Nash equilibrium may not be satisfactory if there is a better equilibrium that we might reach, or if there is concern that the other agent will not play the same equilibrium.
In this talk, I present algorithms and complexity results for a variety of computational problems in game theory, and discuss them in the context of how they can help an agent act (more) strategically.
Biography: Vincent Conitzer is an Assistant Professor of Computer Science and Economics at Duke University. He received Ph.D. (2006) and M.S. (2003) degrees in Computer Science from Carnegie Mellon University, and an A.B. (2001) degree in Applied Mathematics from Harvard University. His research focuses on computational aspects of microeconomics, in particular game theory, mechanism design, voting/social choice, and auctions. This work uses techniques from, and includes applications to, artificial intelligence and multiagent systems. Conitzer has received a CAREER award, a Sloan fellowship, the inaugural Victor Lesser dissertation award, an honorable mention for the ACM dissertation award, and several awards for papers and service at the AAAI and AAMAS conferences.
Host: Prof. Milind Tambe
Location: Hedco Neurosciences Building (HNB) - Audi
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Oct 19, 2010 @ 11:00 AM - 12:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. David Lomet, Microsoft Research
Talk Title: Multi-Version Concurrency via Timestamp Range Conflict Management
Abstract:
A database supporting multiple versions needs to distinguish these versions to determine which versions a transaction can read. By using timestamps as fine granularity, ordered and non-dense version identifiers, the effects of transaction access conflicts and the ordering the conflicts imposes on transactions can be captured in a transaction timestamp range. Using these ranges as constraints often permits concurrent access where conventional concurrency control would block. Blocking can also be an alternative where earlier multi-version techniques required an abort. Timestamp ranges together with the form of conflict can determine the response, concurrent access, blocking, or abort. Further, when blocking is possible, timestamp ranges can be used to conservatively find deadlocks without graph based cycle detection. Thus, multi-version support can enhance the performance of access to current time data via improved concurrency, while supporting transaction time functionality.
Biography:
David Lomet has been a principal researcher and manager of the Database Group at Microsoft Research, Redmond since 1995. Before that, he spent seven years at Digital Equipment Corporation, mainly at Cambridge Research Lab. Earlier, he was a research staff member at IBM Research in Yorktown and subsequently a Professor at Wang Institute. Dr. Lomet spent a sabbatical at the University of Newcastle-upon-Tyne working with Brian Randell. He has a Ph.D in Computer Science from Univ. of Pennsylvania.
Dr. Lomet has done research and product engineering in machine architecture, programming languages, and distributed systems. He is most known for his work in database systems and is one of the inventors of the transaction concept. His database work has focussed on access methods, concurrency control, and recovery. He has published over 100 papers and holds over 40 patents. He has twice been an author of SIGMOD "best papers".
Dr. Lomet has served on many program committees, including SIGMOD, VLDB, and ICDE. He has been FODO'93 PC chair, ICDE'2000 PC co-chair, VLDB'2006 Core Track Chair, and ICDE'2001 conference co-chair. Dr. Lomet has been editor-in-chief of the Data Engineering Bulletin since 1992, and was awarded the SIGMOD Contributions Award for this. He has been an editor of ACM Transactions on Database Systems, the VLDB Journal, and the Journal of Distributed and Parallel Databases. He is on the VLDB Endowment Board, the IEEE TCDE Executive Committee , and has served on the ICDE Steering Committee. Dr. Lomet is a Fellow of AAAS, ACM, and IEEE.
Host: Prof. Shahram Ghandeharizadeh
Location: Henry Salvatori Computer Science Center (SAL) - 222
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Oct 21, 2010 @ 03:30 AM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Eric Wohlstadter , University of British Columbia
Talk Title: Object-Oriented Middleware for Offline Web Applications
Abstract: Recent advances in Web browser technology have led to interest for development of offline Web applications. Offline Web applications make use of persistent data stored on a clientùs local machine to allow for disconnected operation. Disconnected operation has been studied previously in the context of network file systems, object-oriented databases, and distributed object systems. However, previous work does not always apply to the unique software architecture of the browser programming environment. For this reason we have investigated object persistence middleware which meets the design challenges of this environment. In this talk, two specific technical challenges will be described: first, the event-driven architecture of the browser runtime and second, handling the dynamic nature of the JavaScript programming language.
First, traditional systems for disconnected operation rely heavily on lazy object loading (similarly, page faulting). However, the synchronous RPC mechanisms required by lazy loading are well known to be impractical in a Web browser (giving rise to the well known Ajax model). In this talk, I will describe the design of a persistent object-oriented programming model suited for the asynchronous browser environment.
Second, dynamic languages such as JavaScript are schema-less which complicates the mapping of objects to physical storage. Furthermore, such languages allow the runtime binding of first-class function instances as object methods. This complicates object persistence since function instance closures become part of the state of an object. In this talk, I will describe a JavaScript program source transformation we have developed that enables full support for the semantics of the JavaScript data model in our middleware.
Biography: Eric Wohlstadter is an assistant professor at the University of British Columbia. He received a PhD from the University of California, Davis (2005). His research interests include middleware systems, software architecture, dynamic program analysis, and aspect-oriented programming.
Host: Prof. Nenad Medvidovic
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Mon, Oct 25, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Janusz Marecki, IBM T.J. Watson Research Center
Talk Title: Playing in the Dark: On Solving Single/Multistage Bayesian Stackelberg Games with Unknown Player Preferences
Abstract: Recent years have seen a rise in interest in applying game theoretic methods to real world domains such as public surveillance or infrastructure security wherein one player (the leader) chooses a strategy to commit to and waits for the other player (the follower) to respond. In arriving at optimal leader strategies in these domains, of critical importance is the leader's ability to act, often over prolonged periods of time, despite its limited knowledge of the preferences of the follower. In this talk I will first present a suite of efficient algorithms for solving single-stage Bayesian Stackelberg Games with distributional uncertainty over follower payoffs. I will then describe an efficient sampling based algorithm for solving multi-stage Bayesian Stackelberg Games where follower payoffs can initially be unknown. Finally, I will discuss the limitations of the proposed algorithms, in light of the novel business applications of Bayesian Stackelberg Games.
Biography: Janusz Marecki is a research staff member at the mathematical sciences department at IBM T.J. Watson Research Center. Janusz obtained his Ph.D in artificial intelligence form from University of Southern California and Dr.Sc in mathematical modeling from State Scientific and Research Institute of Information Infrastructure in Ukraine. Prior to joining IBM Research, Janusz was a research assistant at the European Laboratory for Nuclear Research, a research associate at the Ukrainian Academy of Sciences and a lecturer at the Academy of Computer Sciences in Poland. His research interests are in reasoning under uncertainty in single/multiagent systems with an emphasis on planning with continuous resources in stochastic environments. He is an author of over 80 refereed publications and four patents.
Host: Dr. Milind Tambe
Location: Charles Lee Powell Hall (PHE) - 223
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
