| 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. |
| 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. |
| 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.
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.
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.
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
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.
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.
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.
Approximation-Algorithms Turned Bandit