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.
Friday, February 23rd, 2007
3:30pm
WEH 7220
The Price of Privacy and the Limits of LP Decoding
Kunal Talwar
Microsoft Research
Suppose one encodes an n-dimensional real vector x as y=Ax, for a suitably chosen A, and an adversary arbitrarily corrupts some of the entries of y to get y’. The surprising fact, proved by Donoho, is that by taking the entries of A as i.i.d. Gaussians, the vector x can be *exactly* recovered by minimizing the L_1 norm |y’ – Ax’| over all x’, provided only a tiny constant fraction of the entries of y were corrupted. Our principal result is the discovery of a sharp threshold rho* ~ 0.239, such that this L_1 minimization succeeds up to any error rate less than rho*, but fails for rates > rho*. This resolves an open question of Candes, Rudelson, Tao, and Vershynin.
Our interest in this problem arose while investigating the price, in accuracy, of protecting privacy in a statistical database. Our results say that any privacy mechanism, interactive or non-interactive, providing reasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.
This is joint work with Cynthia Dwork and Frank McSherry.
SPEAKER: Leonid Kontorovich
TIME: Wednesday 12-1pm, February 21, 2007
PLACE: NSH 1507
TITLE: Kernel Methods for Learning Languages
ABSTRACT:
We present a novel paradigm for learning formal languages from positive and negative examples. The technique consists of mapping the strings to an appropriate high-dimensional feature space and constructing a separating hyperplane in that space. We initiate the study of the linear separability of automata and languages by examining the rich class of piecewise-testable languages. For this language family, we give a kernel that (1) renders it linearly separable and (2) is efficiently computable.
We also give a universal kernel that renders all the regular languages linearly separable. We are not able to compute this kernel efficiently and conjecture that it is intractable, but we do have an efficient $\epsilon$-approximation.
Joint work with Corinna Cortes and Mehryar Mohri.
Adaptive Analysis of Algorithms
Erik D. Demaine
MIT
For many computational problems, some inputs are easier than others. How can we tell easy inputs from hard inputs? Worst-case analysis of algorithms is often unsatisfying because it misses these performance nuances. Average-case analysis gives a better sense about possible performance, but requires some knowledge about the distribution of inputs, making results more specific. In contrast, adaptive analysis parameterizes the input space by one or more additional parameters beyond the problem size, and the goal becomes to optimize simultaneously for all values of those parameters, which is a substantially stronger form of worst-case analysis. When possible, strong adaptive bounds give a fine sense of the intrinsic difficulty of inputs and a better sense of which algorithms are better than which others.
In particular, I’ll talk about successful adaptive analyses of algorithms for boolean set operations (arising in text retrieval), black-box curve manipulation (arising in computer-aided design), black-box function integration (arising in numerical analysis), and basic problems such as sorting and binary search trees.
SPEAKER: Matt Streeter
TIME: Wednesday 12-1pm, February 14, 2007
PLACE: NSH 1507
TITLE: Combining Multiple Heuristics in an Adversarial Online Setting
ABSTRACT:
Heuristics for solving NP-hard problems often have complementary strengths and weaknesses. For example, algorithms developed by statistical physicists are extremely fast at solving satisfiable random 3-CNF formulae, while algorithms based on chronological backtracking are faster on unsatisfiable and structured formulae. What if we could combine several heuristics into a meta-heuristic with better mean running time, on-the-fly while solving a sequence of problem instances? This talk presents some no-regret algorithms that can be used to do exactly that.
Specifically, we consider the following online problem. We are given a pool of (randomized) heuristics and are fed, one at a time, a sequence of instances of some decision problem. To solve each instance, we may interleave the execution of the heuristics according to an arbitrary schedule and may periodically restart each heuristic with a fresh random seed. Our goal is to be competitive with the best fixed schedule in hindsight, even in a universe where the run length distribution of each heuristic on each instance is governed by an adversary.
This talk is based on joint work with Daniel Golovin and Stephen Smith.
February 16, 2007
Ryan Williams
1:30 PM, 1507 Newell-Simon Hall
Thesis Proposal
Title: Algorithms and Resource Requirements for Fundamental Problems
Abstract:
We establish more efficient methods for solving certain classes of NP-hard problems exactly, as well as methods for proving limitations on how quickly the same problems can be solved.
For example, in the Max-Cut problem, one is given a graph $G=(V,E)$ and integer $K$, and one wishes to determine if $G$ has a subset of vertices such that the number of edges leaving the subset is at least $K$. The trivial algorithm for Max-Cut runs in roughly $O(poly(n)\cdot 2^n)$ time, where $n$ is the number of vertices in $G$. Prior to our work, no better algorithm was known for the general case. Our results imply that Max-Cut can be solved in $O(\sqrt{3}^n) = O(1.74^n)$ time and space, yet Max-Cut cannot be solved in $O(n^{\sqrt{3}})$ time and $n^{o(1)}$ space.
Further study includes finding faster algorithms and proving larger limitations for these problems, as well as extending our techniques to counting versions of {\sf NP} problems. We have already extended some of our algorithms in this manner, and are currently working on how limitations can be proved.
Thesis Committee:
Manuel Blum, Chair
Ryan O’Donnell
Steven Rudich
Russell Impagliazzo, University of California, San Diego
Dieter van Melkebeek, University of Wisconsin, Madison
SPEAKER: Benoit Hudson
TIME: Wednesday 12-1pm, February 7, 2007
PLACE: NSH 1507
TITLE: Three Recent Mesh Refinement Results
ABSTRACT:
Mesh refinement is the first step in running a finite element simulation: we take an input geometry (points, segments, polygons, …) and output a mesh of triangles and tetrahedra.
I’ll report on three exciting new mesh refinement results our group have come up with in the past year. First, for the benefit of those who didn’t see Todd’s talk last semester, I’ll reiterate (without proof) our optimal-time algorithm for mesh refinement. Next, I’ll show how to work-efficiently parallelize our algorithm to within a log factor of optimal depth. Finally, I’ll show how to dynamically maintain a mesh as we add or remove points to/from it, in optimal time. There were no known fast algorithms for any of these problems before except in two dimensions.
Our work opens up a vast number of open problems, both geometric and algorithmic; I’ll make sure to leave some for the audience to ponder.
Sometimes you will encounter a projector screen that hangs so low, making the bottom of the slide way below anyone in the room can see. One way to avoid this annoying situation is to leave some space at the bottom of your slides. This works well when you know the room ahead of time. But what if you are visiting a new place? (Hmm… job talks come to mind.)
Turns out there are actually a couple of solutions.
My favorite is to use a rarely used feature of PowerPoint—you can in fact adjust the dimension of the slide show window through some minimal scripting. Here is a demo file as a proof of concept. (If you use Internet Explorer, please save the file and then open it locally. See below.) I can imagine many fancy mechanisms to integrate this into your slides.
Or you can open the PowerPoint file inside Internet Explorer, which will host the slide show inside its client area. (Try drag and drop the file into IE.) You can then resize the IE window as you go.
Or you can hold down the Alt key and then click that tiny “Slide Show from current slide” icon in the lower left corner. Your slide show will now be run in a windowed mode, similar to how it is being run when you open a PowerPoint file inside IE. You can then adjust this window like any other window.
All of these methods have issues though. If you use the first, you need to cover up the strip of desktop exposed due to a reduced window size. I bring a full-screen-sized black bitmap for this reason. But if you do this right, it does look very nice. The second and third bring unnecessary clutter like toolbars to the projector screen. Plus, you lose the ability to make pen annotations if you happen to be a tablet user.
P.S. I tested this in version 2003 only. I no longer have the older versions.
