Thu, Mar 1, 4:30
Mohit Singh
PPB 300
Title: Approximating Minimum Bounded Degree Spanning Trees to within one of Optimal
Abstract:
In the Minimum Bounded Degree Spanning Tree problem, we are given an edge-weighted undirected graph with degree bound k for each vertex v and the task is to find a spanning tree of minimum cost which satisfies all the degree bounds. In this talk I will present an efficent algorithm which returns a spanning tree in which degree of any vertex v is at most k+1 and whose cost is at most the cost of the optimal spanning tree of maximum degree k. This settles a conjecture of Goemans affirmatively and generalizes a result of Furer and Raghavachari to weighted graphs. This is essentially best possible.
The algorithm generalizes when vertices have distinct upper and lower bounds on vertex degrees and returns a spanning tree of optimal cost which violates the degree bounds by an additive one.
The main technique used is the iterative rounding method introduced by Jain in the design of approximation algorithms. Our major technical contribution is to extend the ideas of this method and apply them effectively to a new domain of problems. An unique feature of our iterative rounding algorithm is that it does not round. The talk will be self-contained.
This is joint work with Lap Chi Lau.
Friday, March 2nd, 3:30pm
WEH 7220
The Limits of Quantum Computers
Scott Aaronson (University of Waterloo)
In the popular imagination, quantum computers would be almost magical devices, able to “solve impossible problems in an instant” by trying exponentially many solutions in parallel. In this talk, I’ll describe four results in quantum computing theory that directly challenge this view.
First, I’ll show that any quantum algorithm to decide whether a function f:[n]->[n] is one-to-one or two-to-one needs to query the function at least n^{1/5} times. This provides strong evidence that collision-resistant hash functions, and hence secure electronic commerce, would still be possible in a world with quantum computers.
Second, I’ll show that in the “black-box” or “oracle” model that we know how to analyze, quantum computers could not solve NP-complete problems in polynomial time, even with the help of nonuniform “quantum advice states.”
Third, I’ll show that quantum computers need exponential time to find local optima — and surprisingly, that the ideas used to prove this result also yield new classical lower bounds for the same problem.
Finally, I’ll show how to do “pretty-good quantum state tomography” using a number of measurements that increases only linearly, not exponentially, with the number of qubits. This illustrates how one can sometimes turn the limitations of quantum computers on their head, and use them to develop new techniques for experimentalists.
No quantum computing background will be assumed.
SPEAKER: Andrew Gilpin
TIME: Wednesday 12-1pm, February 28, 2007
PLACE: NSH 1507
TITLE: Nesterov’s excessive gap technique and poker
ABSTRACT:
For the generic convex optimization problem of minimizing a (non-smooth) convex function f(x) over a convex domain D, any subgradient method requires O(1/epsilon^2) iterations for obtaining an epsilon-solution. However, this analysis is based on a black-box oracle access model for f and D. Recently, Nesterov developed the excessive gap technique which yields an algorithm needing only O(1/epsilon) iterations to obtain an epsilon-solution in certain problems having a non-smooth convex objective with a certain max-like structure.
In this talk I will present the general theory behind Nesterov’s excessive gap technique, and I will describe how we extended the basic framework to handle the problem of computing approximate Nash equilibria in two-person zero-sum sequential games of imperfect information. Also, I will discuss some additional heuristics we developed which yield even faster convergence in practice.
Finally, I will describe how we used this algorithm (along with our recent advances in automated abstraction for sequential games of imperfect information) to develop an extremely competitive heads-up Texas Hold’em poker player.
This talk describes joint work with Samid Hoda, Javier Pena, Tuomas Sandholm, and Troels Sorensen.
