2006-2007 seminars

Originally number theoretic methods were used to construct optimal (explicit) expanders. Recently combinatorial methods have been utalized in proving that certain number theoretic graphs are expanders. We will explain some uses of such expanders in...

We develop a framework for obtaining (deterministic) Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic problems with either convex or monotone single-period cost functions. Using our framework, we give the first...

In the past 2 years there has been considerable progress in the algorithmic problem of combining rankings (permutations on a ground set of "candidates") into a consensus ranking. This problem dates back to the 18th century, when the French...

In 1951 Nash proved that every game has a Nash equilibrium. The proof is non-constructive, reducing the existence of Nash equilibria to that of Brouwer fixpoints. Whether Nash equilibria can be computed efficiently had remained open. I shall outline...

In the first talk I reviewed the basic properties of linear feedback shift registers and their analysis using generating functions and trace functions. I then defined feedback with carry shift registers (FCSRs) and began their analysis by N-adic...

Traditional algorithm design is being challenged by the remarkable technological advances in data acquisition of recent years. Today's algorithms must often cope with data that is massive, noisy, uncertain, high-dimensional, nonuniformly priced...

Linear feedback shift registers (or, equivalently, linear recurrences) have been studied in one form or another for at least 75 years. They have found a Myriad of applications in communications, cryptography, random number generation, and other...

We present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1-epsilon) satisfiable 2CSP our first algorithm finds an assignment of variables satisfying a 1 - O(sqrt...

In part I of this talk, we began a discussion of "simple algorithms" and restricted our attention to the priority algorithm model which models ``greedy-like'' algorithms. In Part II of this talk, we will extend the priority algorithm framework to...

The Internet is an indispensable part of our information society, and yet its basic foundations remain vulnerable to simple attacks, and one area that remains especially susceptible to attack is routing. There have been increasing efforts in the...