|
CSE Home |
590z Previous Quarters |
About Us |
Search |
Contact Info |
Talk Schedule
Note for speakers: Please email me (ashish@cs.washington.edu) the
details of your talk as soon as you decide. Thanks!
|
| Day | Speaker(s) | Title |
| Apr 2 | Leonard J. Schulman, Cal Tech | The Time Value of Resources (abstract) |
| Apr 3 | Jason Hartline | Competitive Auctions and Coding Theory (abstract) |
| Apr 9 | Lisa Korf, Dept of Mathematics, UW | Stochastic Programming and Options Pricing (abstract) |
| Apr 10 | Sanjeev Arora, Princeton University | Computing very good approximate solutions to traveling salesman and other geometric NP-hard problems: A survey (abstract) |
| Apr 16 | Carl de Marcken, ITA Software | The Computational Complexity of Air Travel Planning (abstract) |
| Apr 17 | Jason Hartline | Competitive Auctions and Coding Theory continued (abstract) |
| Apr 23 | Richard Ladner | On Two Class-Constrained Version of the Multiple Knapsack Problem (abstract) |
| Apr 24 | Theory Night Group | Strong History Independence and Canonical Representations (abstract) |
| Apr 30 | Dimitris Achlioptas, Microsoft Research | Randomized Kernel Functions (abstract) |
| May 1 | ||
| May 7 | Paul Tseng, Department of Mathematics, UW | On Approximating Nonconvex Quadratic Optimization by SDP Relaxation (abstract) |
| May 8 | William Pentney | Web Search through Link Analysis (abstract) |
| May 14 | Elchanan Mossel, Microsoft Research | Learning Functions of k Hidden Variables (abstract) |
| May 15 | Erik Vee | Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems (abstract) |
| May 21 | No seminar because of STOC | |
| May 22 | Gidon Shavit | Combinatorial Bounds for List Decoding (abstract) |
| May 28 | Vijay Vazirani, Georgia Tech | Primal-Dual Algorithms and Market Equilibria (abstract) |
| May 29 | Frank McSherry | Random Graph Models for Information Networks (abstract) |
| Jun 4 | ||
| Jun 5 | Anna Karlin |

| Speaker | Leonard J. Schulman, Cal Tech |
| Title | The Time Value of Resources |
| Abstract |
We examine a familiar quandary: current shortage of cash forces
investment choices that are suboptimal in the long run. We model this
situation and show both a positive result: an algorithm whose
inefficiency, in all situations covered by our model, is bounded; and
negative results, namely that in some situations, no algorithm can
improve on our bound. We consider several examples, including
sequential construction of Steiner trees.
This is joint work with Sridhar Rajagopalan, IBM. |
---------------
| Speaker | Jason Hartline |
| Title | Competitive Auctions and Coding Theory |
| Abstract |
I will discuss a recent new competitive auction based loosely on
Byzantine agreement and erasure correcting codes. The an auction in
the class of auctions presented achieves the best known competitive
ratio, 3.39 (from 4.0). This results comes from using a mix of
previously used auction design techniques which I will review, and
some new techniques that seem to be similar in flavor to techniques
used for erasure correcting codes and Byzantine agreement.
This will be a rather informal talk and it would be great to get feedback from people who are more familiar with erasure correcting codes and Byzantine than I am. |
---------------
| Speaker | Lisa Korf, Dept of Mathematics, UW |
| Title | Stochastic Programming and Options Pricing |
| Abstract | This lecture examines options pricing problems in the setting of stochastic programming. To understand this lecture, it will be helpful to know a little bit about linear programming; everything else will be fully explained. We will define the requisite financial terminology, define stochastic programs, and apply them to derive pricing results for options. |
---------------
| Speaker | Sanjeev Arora, Princeton University |
| Title | Computing very good approximate solutions to traveling salesman and other geometric NP-hard problems: A survey |
| Abstract |
Traveling Salesman, Steiner Tree, and many other famous geometric optimization problems are NP-hard. Since we do not expect to design efficient algorithms that solve these problems optimally, we should try to design approximation algorithms, which can compute a provably near-optimal solution. This talk surveys a new technique developed over the past few years that allows us to design approximation schemes for many of these problems. For any fixed constant c>0, the algorithm can compute a solution whose cost is at most (1+ c) times the optimum. (The running time is polynomial for every fixed c>0, and in many cases is even nearly linear.) The talk will be self-contained and accessible to a general scientific audience. It will survey the techniques, results and open problems of this area. |
---------------
| Speaker | Carl de Marcken, ITA Software |
| Title | The Computational Complexity of Air Travel Planning |
| Abstract |
At any moment there are between 2,000 and 10,000 commercial airliners
in the sky, part of a dense network that provides more than 100,000
practical paths from Boston to San Francisco every day.
But the search problem faced by travel agents, that of finding a desirable combination of flights and fares for a given passenger's trip, is much harder than path planning. In fact, the airlines' price structure is so rich that finding the cheapest price for a simple round-trip journey is in the general case undecidable. Even if one bounds the size of solutions to a small number of flights there may be more than 10^20 reasonable answers to a simple travel query. This talk will describe the nature of the travel planning problem from a computer science perspective, ranging from network properties of the flights to the practical and theoretical complexity of pricing. In addition, it will sketch some new search algorithms that are a radical departure from the brute force methods that previously dominated the travel industry. For example, we directly construct a factored graphical representation of the space of answers to a travel query that is very similar to a Bayes' net or the chart produced by a context-free parser. Using this representation a graph of 250,000 nodes can encode 10^30 or more options. We have developed a wide range of algorithms for manipulating this representation, and many of our problems and solutions will be of interest to the Bayes' net and statistical NLP communities. Carl de Marcken is chief scientist at ITA Software, a company that develops search engines for airlines and that provides the software for web sites such as Orbitz. He has a PhD in computer science from MIT, where his undergraduate and doctoral theses on natural language processing won best dissertation awards. |
---------------
| Speaker | Richard Ladner |
| Title | On Two Class-Constrained Version of the Multiple Knapsack Problem |
| Abstract |
Tami Tamir (more about her)
will be visiting for the next two years, starting in September 2002. I
will present one of her papers with Hadas Shachnai.
In the Multiple Knapsack Problem (MKM) there are items from different classes that can be placed in a number of knapsacks. Each knapsack has a capacity which is the number of items it can hold and a class limit which bounds the number of classes that can appear in the knapsack. Two problems are explored: (i) Total packing: maximize the total number of items placed in all the knapsacks and (ii) Fair packing: maximize the factor c such that at least c percent of each class of item is placed in all the knapsacks. There are versions of these problems where the items have a weight and utility, but the problem already has interesting applications which the weights and utilities are the same. Total packing and fair packing are NP hard problems so we'll talk about approximate algorithms to solve these problems. |
---------------
| Speakers | Theory Night Group |
| Title | Strong History Independence and Canonical Representations |
| Abstract |
We give a brief introduction to history independent data structures,
i.e., ones that have representations in memory that do not give away
any extraneous information about the data structures history. We
answer an open question of Naor and Teague and show that a data
structure is strongly history independent iff it has canonical
representations[1]. We then give a less restrictive definition of
strong history independence and give some interesting properties of
this definition that relate to canonical representations.
[1] This is shown using Naor and Teague's definition of canonical representations which allows initial randomness when the data structure is created (E.g., for the choice of hash functions for a hashtable). |
---------------
| Speaker | Dimitris Achlioptas, Microsoft Research |
| Title | Randomized Kernel Functions |
| Abstract |
Kernel Principal Component Analysis (KPCA) is a relatively new machine
learning technique that significantly generalizes PCA. KPCA can be
extremely effective, but scales very poorly to large data sets as it
requires the eigendecomposition of a correspondingly large, dense
matrix. We show how one can employ randomization to dramatically speed
up KPCA by employing three orthogonal techniques: i) sampling and
quantizing the entries of the Gram matrix, ii) applying randomized
rounding in evaluating the kernel expansions, and iii) using random
projections in evaluating the kernel itself. In all three cases, we
give sharp, high-probability bounds on the accuracy of the obtained
results.
Interestingly, it seems that all three techniques above can be cast as instantiations of the following very simple idea: replace the kernel function k by a "randomized" kernel function which behaves like k in expectation. The central limit theorem, in different guises, does all the remaining work. Based on joint work with Frank McSherry (UW) and Bernhard Scholkopf (Max Planck). |
---------------
| Speaker | Paul Tseng, Department of Mathematics, UW |
| Title | On Approximating Nonconvex Quadratic Optimization by SDP Relaxation |
| Abstract | We will survey recent results on approximating nonconvex quadratic optimization by semidefinite programming (SDP) relaxation. This began with the seminal work of Goemans and Williamson for Max Cut, followed by extensions of Nesterov and Ye. Recent results for the case of ellipsoid constraints will also be discussed. |
---------------
| Speaker | William Pentney |
| Title | Web Search through Link Analysis |
| Abstract | I will present recent results from a study of use of spectral methods for web search. Several different web search algorithms have been proposed in recent years (PageRank, HITS, etc.), each of which presents particular issues in practice. The problems posed by synonymy (multiple terms with identical meanings) and polysemy (single terms with multiple meanings) are a particular issue for such algorithms. I will propose a model for the search problem, and a search algorithm which attempts to address synonymy and polysemy by using a low-dimensional representation of anchor text content. |
---------------
| Speaker | Elchanan Mossel, Microsoft Research |
| Title | Learning Functions of k Hidden Variables |
| Abstract |
We consider a fundamental problem in learning theory: learning an
arbitrary Boolean function which depends on an unknown set of k out of
n Boolean variables. We give an algorithm for learning such
functions under the uniform distribution in time c_k n^{a k}) where
c_k is some constant independent of n, and a = m/(m+1), where m <
2.376 is the matrix multiplication exponent.
This is the first polynomial factor improvement over O(n^k) bound which can be achieved via exhuastive search. The new algorithm is based on a new duality Lemma relating the Fourier representation of a Boolean function over the reals and its representation as a polynomial over the Field of two elements. Joint work with Ryan O'Donnell (MIT) and Rocco Servedio (Harvard). |
---------------
| Speaker | Erik Vee |
| Title | Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems |
| Abstract |
Time-space tradeoffs are lower bounds that explicitly give the
tradeoff between time and memory. This paper examines two directions
related to time-space tradeoffs.
The first part gives a connection between static data structures and time-space tradeoffs. This connection allows us to prove bounds on the query-time of important problems, such as Lambda-Nearest Neighbor. The second part extends techniques using communication complexity to multiparty communication complexity. These techniques allow us to show a strict separation between general and oblivious branching programs, two widely-used models of nonuniform computation. |
---------------
| Speaker | Gidon Shavit |
| Title | Combinatorial Bounds for List Decoding |
| Abstract |
Parts of paper by Venkat Guruswami, Johan Hastad, Madhu Sudan, and
David Zucherman with this title.
"Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. Here, we report linear codes with non trivial list-decodability: i.e., codes of large rate that are nicely list-decodable... ... we show that there exist codes of rate $R$ and block-length $n$ that have at most $c$ codewords in every Hamming ball of radius $H^{-1}(1-R-1/c)n$... ... for every $\epsilon > 0$ , we present a polynomial time constructible asymptotically good family of binary codes of rate $\Omega(\epsilon^4)$ that can be list-decoded in polynomial time from up to a fraction $(1/2 - \epsilon)$ of errors, using lists of size $O(\epsilon^2)$..." |
---------------
| Speaker | Vijay Vazirani, Georgia Tech |
| Title | Primal-Dual Algorithms and Market Equilibria |
| Abstract |
The primal-dual schema has emerged as an important unifying principle
in approximation algorithms, an area that has been the focus of
algorithmic research over the last decade. The basic idea underlying
this schema transcends the setting of optimization problems, and has
recently been applied to game theoretic settings.
I will describe both aspects in the context of the following problems:
|
---------------
| Speaker | Frank McSherry |
| Title | Random Graph Models for Information Networks |
| Abstract | 590zz today will be an informal discussion of some of the stuff I have been doing my generals on. I suspect we will take a vote as to whether people are interested in spending time listening to me ramble about graph stuff (neat stuff, btw). In particular, I am fully conversant in Kleinberg's recent small world work, as well as some resource discovery work he has done recently. There are also some neat evolutionary graph models from Barabasi et al. and from the Almaden group. |
|
Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [Comments to Ashish Sabharwal, ashish] |
||