Theory Seminars - Spring 2006



Date Speaker Speaking
Mar 28
MiRC 102
3-4pm
Santosh Vempala Dispersion of Mass and the Complexity of Randomized Algorithms
How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. Two of the most appealing conjectures in the latter field, called (i) slicing (or isotropic constant) and (ii) variance, together imply that for a random point X from an isotropic convex body in n-space, the variance of |X|^2 is O(n). We prove a reverse inequality: for any isotropic polytope with at most poly(n) facets, the variance of |X|^2 is AT LEAST n/ln n (up to a constant). In fact, the lower bound holds for any polytope of unit volume with poly(n) facets contained in the ball of radius poly(n). It implies that in order for most of such a convex polytope to be contained between two concentric spheres, their radii have to differ by about 1/\sqrt{\log n}; in contrast, most of a unit-volume ball lies in between two spheres whose radii differ by only about 1/\sqrt{n}. Such geometric dispersion leads to lower bounds on the randomized complexity of some basic algorithmic problems, including a quadratic lower bound for estimating the volume of a convex body.

This is joint work with Luis Rademacher.

Feb 27
MiRC 102
12-1pm
Adam Klivans, U of Texas, Austin Agnostically Learning Halfspaces
We give the first algorithm that efficiently learns halfspaces (under distributional assumptions) in the notoriously difficult agnostic framework of Kearns, Schapire, and Sellie. In this model, a learner is given arbitrarily labeled examples from a fixed distribution and must output a hypothesis competitive with the optimal halfspace hypothesis.

Our algorithm constructs a hypothesis whose error rate on future examples is within an additive ε of the optimal halfspace in time poly(n) for any constant ε > 0 under the uniform distribution over {0,1}n or the unit sphere in Rn, as well as under any log-concave distribution over Rn. It also agnostically learns Boolean disjunctions in time 2O(sqrt(n)) with respect to *any* distribution. The new algorithm, essentially L1 polynomial regression, is a noise-tolerant arbitrary-distribution generalization of the "low-degree" Fourier algorithm of Linial, Mansour, & Nisan.

Joint work with A. Kalai, Y. Mansour, and R. Servedio.

Jan 30
MiRC 102
2-3pm
Ryan O'Donnell, Microsoft Research Learning under the uniform distribution: Toward DNF
In this talk we will survey some recent work on the problem of learning under the uniform distribution. In this problem, there is an unknown function f : {0,1}n -> {0,1}. The learning algorithm has access to random "examples" from the function of the form <x,f(x)>, where x is drawn uniformly at random. The algorithm's job is to output a "hypothesis" h : {0,1}n -> {0,1} which is epsilon-close to f. Our main concern is the time-efficiency of the algorithm.

The "holy grail" would be to give an algorithm taking polynomial time for any function f with a polynomial-sized DNF formula. We will discuss some algorithmic attacks on the problem, and also discuss why complete success may prove an elusive goal...

Jan 20
MiRC 102
1-2pm
Amihood Amir, Bar-Ilan University Asynchronous Pattern Matching - Metrics
Traditional Approximate Pattern Matching (e.g. Hamming distance errors, edit distance errors) assumes that various types of errors may occur to the data, but an implicit assumption is that the order of the data remains unchanged.

Over the years, some applications identified types of "errors" were the data remains correct but its order is compromised. The earliest example is the "swap" error motivated by a common typing error. Other widely known examples such as transpositions, reversals and interchanges are motivated by biology.

We propose that it is time to formally split the concept of "errors in data" and "errors in address" since they present different algorithmic challenges solved by different techniques. The "errors in address" model, which we call asynchronous pattern matching, since the data does not arrive in a synchronous sequential manner, is rich in problems not addresses hitherto.

We will consider some reasonable metrics for asynchronous pattern matching, such as the number of inversions, or the number of generalized swaps, and show some efficient algorithms for these problems. As expected, the techniques needed to solve the problems are not taken from the standard pattern matching "toolkit".

(joint work with Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skienna and U. Vishne)

Jan 9
MiRC 102
11-12 am
Tom Hayes, Berkeley Playing the k-armed bandit with adaptive payouts

The "k-armed bandit" is a modified slot machine, which has k arms you can pull, rather than just one. Each arm has a different payout, which can change every time you play, but is always in the range [0,1]. If we get to play this machine T times, how well can we do, compared to the best single arm in hindsight? Specifically, the goal is to minimize "regret", defined as the random variable Payout(algorithm) minus Payout(best arm).

The character of this problem depends strongly on how much information is given to the algorithm. In the "full information" version of the game, the algorithm is told the payout for all k arms after each round. This version of the problem is well-understood, and randomized algorithms are known which, with high probability, guarantee regret O(\sqrt{T log k}), which is optimal. In the "bandit" version of the game, the algorithm is only told the payout for the arm it chose in the last round. This setting is harder, with a lower bound of Omega(\sqrt{T k}), and previously best upper bound O(T^{2/3}) (for k fixed).

We present a new randomized algorithm for the bandit version, which achieves regret O(\sqrt{T k log k}) with high probability.

This is joint work with Varsha Dani.


Theory Seminar: Schedule for Summer 2006

Date Speaker Speaking
aug 10
CCB 101
4-5pm
Hariharan Narayanan Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body
We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for estimating the surface area of a convex bodies given by a membership oracle. Our method has a complexity of O*(n4), where n is the dimension, compared to O*(n8.5) for the previous best algorithm. We show that this estimate cannot be improved given the current state-of-the-art in volume computation.

Theory of Computation Colloquium - Fall 2006

Room MiRC 102A at 2:00 p.m. on Monday unless otherwise noted.

Date Speaker Topic
Sep 11 Subhash Khot New Results for Learning Noisy Parities and Halfspaces
Sep 18 Ehud Kalai An Approach to Bounded Rationality
Sep 21 Alan Frieze Line of Sight Networks (Joint ACO/TOC Colloquium)
Oct 2 Juan Vera On the Average Case Performance of some Approximation Algorithms for the Facility Location Problem
Oct 9 Roman Vershynin Beyond Hirsch Conjecture: on Smoothed Complexity of the Simplex Algorithm
Oct 23 No talk FOCS '06
Oct 30 Christine Heitsch The Challenge of Coding Biological Information in Nucleotide Sequences
Nov 6 Venkat Guruswami List Decoding with Optimal Rate: Folded Reed-Solomon Codes
Nov 10 Santosh Vempala, Richard Karp, Ravi Kannan, Richard Lipton ARC ThinkTank Distinguished Lectures
Nov 13 Adam Kalai Approximation-Algorithms Turned Bandit
Nov 20 Eric Vigoda, Jennifer Chayes, Christian Borgs, Milena Mihail Kickoff for the Special Focus on Discrete Random Systems


Sep 11, Subhash Khot, Georgia Tech

New Results for Learning Noisy Parities and Halfspaces

I will present some new results on the learnability of parities and halfspaces in the presence of noise. The results can be informally stated as:
(1) In uniform distribution setting, learning juntas on k variables reduces to learning noisy parities on k variables. Learning DNFs reduces to learning noisy parities on O(log n) variables.
(2) Learning halfspaces: Given a set of labeled examples in Rn such that there is a halfspace that correctly classifies 1-ε fraction of examples, it is NP-hard to find a halfspace that is correct on 1/2+ε fraction of examples for any ε > 0. This is optimal.
(3) It is hard to PAC-learn majorities of halfspaces assuming that the Ajtai-Dwork lattice-based cryptosystem is secure (which amounts to assuming that the shortest vector problem for n-dimensional lattices is hard to approximate within factor nO(1)).

Joint work with Vitaly Feldman, Parikshit Gopalan, and Ashok Kumar Ponnuswami. To appear in FOCS'06.


Sep 18, Ehud Kalai, Northwestern University

An Approach to Bounded Rationality

A central question in game theory, learning, and other fields is how a rational intelligent agent should behave in a complex environment, given that it cannot perform unbounded computations. We study strategic aspects of this question by formulating a simple model of a game with additional costs (computational or otherwise) for each strategy. While a zero-sum game with strategy costs is no longer zero-sum, we show that its Nash equilibria have an interesting structure and the game has a new type of "value." We also show that potential games with strategy costs remain potential games. Both zero-sum and potential games with strategy costs maintain a very appealing property: simple learning dynamics converge to Nash equilibrium.


Sep 21, Alan Frieze, Carnegie Mellon University

Line of Sight Networks

Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. In addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community.

For many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space and when they have line-of-sight access to one another --- consider, for example, urban settings or large indoor environments. In such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions.

Here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for k-connectivity. Specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (We think of the rows and columns as "streets" and "avenues" among a regularly spaced array of obstructions.) Further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. In addition to analyzing connectivity and k-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional "relay" nodes.

Joint work with Jon Kleinberg, R. Ravi and Warren Debaney.


Oct 2, Juan Vera, Georgia Tech (via CMU)

In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Conventional wisdom holds that "in practice" approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this talk, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.

We analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

Joint work with Abraham D. Flaxman and Alan M. Frieze


Oct 9, Roman Vershynin, UC Davis

Beyond Hirsch Conjecture: on Smoothed Complexity of the Simplex Algorithm

Smoothed analysis of algorithms is concerned with the expected running time of an algorithm under slight random perturbations of arbitrary inputs. Spielman and Teng proved that the (shadow-vertex) simplex method had polynomial smoothed complexity. On a slight random perturbation of arbitrary linear program, the simplex method finds the solution after a walk on polytope(s) with expected length polynomial in the number of constraints n, the number of variables d and the inverse standard deviation of the perturbation 1/sigma.

Our main result is that the length of walk in the simplex method is actually polylogarithmic, rather than polynomial, in the number of constraints n. This shows that the tight Hirsch conjecture n-d on the length of walk on polytopes is not a limitation for the smoothed Linear Programming. Random perturbations create short paths between vertices.

Smoothed analysis is related to theoretical open problems of independent interest, such as estimating the condition number of a random matrix, and the problem of "decoupling" phase-I from phase-II in linear programming. We will discuss some approaches to these problems based on concentration inequalities.


Oct 30, Christine Heitsch, Georgia Tech

The Challenge of Coding Biological Information in Nucleotide Sequences

In the nucleus, lengthy DNA molecules have a canonical double-stranded helix structure well-adapted for information storage and retrieval. In the laboratory, short single-stranded DNA sequences have a variety of possible applications, ranging from microarrays to nanomolecular structures and DNA computation. Furthermore, ongoing discoveries highlight the many vital regulatory and catalytic functions performed by different RNA molecules, other than mediating the production of proteins from DNA. Thus, increasing interest is focused on the self-bonding of RNA molecules and on the design, analysis, and prediction of RNA secondary structures.

With the goal of understanding and manipulating the structural / functional information encoded by the selective base pair hybridization of single-stranded DNA and RNA molecules, we consider algorithms for the design of RNA secondary structures and DNA code words based on discrete mathematical models. Our combinatorial approach relies on reducing the problem of designing an RNA sequence with a specified set of base pairings to the question of creating a set of nucleotide code words of sufficient quality. Thus, the essential challenge in both cases is producing sets of short oligonucleotides whose elements are strongly differentiated from each other with respect to the biochemical energetics.


Nov 06, Venkat Guruswami, University of Washington

List Decoding with Optimal Rate: Folded Reed-Solomon Codes

Suppose you want to communicate a message of k packets on a noisy communication channel. So you judiciously encode it as a redundant collection of n = ck packets and transmit these. What is the fewest number of correct packets one needs to receive in order to have any hope of recovering the message?

Well, clearly one needs at least k correct packets. In this talk, I will describe an encoding scheme that attains this information-theoretic limit: for any desired constant eps > 0, it enables recovery of the message as long as at least k(1+eps) packets are received intact. The location of the correct packets and the errors on the remaining packets can be picked adversarially by the channel.

This achieves the optimal trade-off (called "capacity") between redundancy and error-resilience for a malicious noise model where the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. These results are obtained in an error-recovery model called list decoding. The talk will introduce and motivate the problem of list decoding, and then give a peek into the algebraic ideas and constructions that lead to the above result.

Based on joint work with Atri Rudra.


Nov 13, Adam Kalai, Weizmann Institute.

Approximation-Algorithms Turned Bandit

In a multi-armed bandit problem, a decision maker makes a sequence of decisions, online, in the face of uncertainty. For example, consider a traveling salesman who repeatedly must choose a route to visit a set of cities. Each period, she decides on a route and then finds out the total time that it took. Her goal is to achieve low average time over many periods. More generally, the decision-maker has a known (possibly infinite) set of decisions D, and there is an unknown sequence of cost functions chosen from a known family of functions F.

Unfortunately, many problems like the TSP example above, cannot be solved efficiently offline, even if everything was known in advance, and one must use approximation algorithms instead. We give a general reduction, showing how to solve *online* linear optimization problems (ones where costs scale linearly like the online TSP example), using an approximation algorithm designed for the *offline* (full-information) setting. Performance is guaranteed to be nearly as good as the average performance of the best single decision, e.g., best route, if one had to use the same decision each period, where the best is chosen with the benefit of hindsight.

Our results generalize prior work which gave similar results for the case where the offline problem could be solved exactly, or for special types of approximation algorithms. The use of approximation algorithms presents interesting new difficulties for which we provide geometric solutions.


Maintained by Dani Denton, Tejas Iyer and Santosh Vempala. ({denton,ti,vempala} at cc dot gatech dot edu)