CSE logo University of Washington Department of Computer Science & Engineering
 CSE 590z and 590zz - Theory Seminars, spring 2002
  CSE Home     590z Previous Quarters  About Us    Search    Contact Info 

    590z meets Tuesdays, 1:30-2:20pm in EE1 037. 590zz meets Wednesdays, 2:30-3:20pm in MGH 295.
 
View the combined email archive for cse590z@cs and theory-group@cs.
 
The plan for 590z this quarter is to try to have as many outside speakers as possible and spend the rest of the weeks letting students and faculty present interesting papers in various theory areas. 590zz, as usual, will focus on the current research work of students and faculty. This can be anything from half-baked to fully developed ideas. The point is to let everyone in the theory group know what you are working on and perhaps get some useful insights from others into problems that you are stuck at. Graduating students are also welcome to present their job talks.


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



Talk Abstracts       

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:

  1. The classical facility location problem, whose modern-day applications include finding good clusterings and cost-effective placements of servers on the Internet. We give an algorithm whose running time is dominated by the time to sort the edges of the underlying metric.
  2. Market equilibrium: we give the first polynomial time algorithm for finding a price vector under which market clears, assuming that buyers have linear utilities.

---------------

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.



CSE logo 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]