BATS: Bay Area Theory Symposium 2004

Talk Abstracts 

Computing Equilibria in Multi-Player Games

Tim Roughgarden, Stanford University

This talk will survey recent research (joint with Christos Papadimitriou) on the complexity of computing equilibria — particularly correlated equilibria — in games with a large number of players. Such games, in order to be computationally meaningful, must be presented in some succinct, game-specific way.  I will discuss a general algorithmic framework for identifying the complexity of optimizing over the correlated equilibria of a compactly represented multi-player game, and applications of this paradigm to symmetric games, graphical games, and congestion games. Consequences include (on the positive side) the first polynomial-time algorithm for this problem in symmetric games and (on the negative side) the first complexity-theoretic justification of the standard restrictions on the topology of a graphical game.

An Overview of Time-Space Tradeoffs

Erik Vee, IBM Almaden

Even as computers grow more powerful, algorithms are expected to handle larger and larger amounts of data. The area of time-space tradeoffs studies such algorithms operating in memory-constrained environments. It focuses on finding general properties of problems that make them computationally difficult to solve using limited space, rather than simply examining specific problems.

This talk will give an overview of time-space tradeoffs, highlighting some of the strongest recent results. It will give an introduction to the techniques used, demonstrating the connection between time-space tradeoffs and communication complexity. It will also suggest several future directions, as well as potential hurdles to future progress.

Recent Schemes for Increasing the Quantum Fault-tolerance Threshold

Ben Reichardt, UC Berkeley

Errors, including faulty gates and corrupted memory, are inevitable in a quantum computer. Therefore implementations will require schemes to protect against noise, using for example quantum error correcting codes. How much noise is tolerable? Recent schemes have increased the threshold of tolerable noise to several percent.

Sublinear Queries (SuLQ) Statistical Databases: Privacy with Power

Cynthia Dwork, Microsoft Research

We revisit the classical problem of adding noise to the query responses of a statistical database so as to simultaneously provide privacy for the individual database entries while yielding a rich set of useful statistics and functionalities.

For concreteness, let the database have n rows (people) and d columns  (attributes). A query consists of a pair (S,f), where S is a subset of rows and f is a d-ary function. The true answer to the query is the sum of the application of f to every row in S. The perturbation algorithm adds to the true answer some random noise, and releases the result.

An investigation of the amount of noise needed to preserve privacy shows the viability of this approach when the number of queries is small relative to the size of the database. In particular, the amount of noise needed to preserve privacy is little-o of the sampling error when the number of queries is sub-linear in the size of the database. (Such a scenario makes sense when the database is very large.) Thus, privacy can be protected at essentially no cost in statistical accuracy, and the massive size of the database can be exploited to enhance, rather than undermine, privacy.

The SuLQ primitive — query and noisy response — gives rise to a powerful calculus of noisy computation, permitting, for example, approximate versions of k means clustering, the perceptron algorithm, principal component analysis, and machine learning in the statistical queries model. 

Joint work with A. Blum, F. McSherry, and K. Nissim.

Efficient Hashing with Lookups in Two Memory Accesses

Rina Panigrahy, Stanford University

The study of hashing is closely related to the analysis of balls and bins. Azar et. al. [ABKU99] showed that instead of using a single hash function, if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins.  This leads to the concept of two-way hashing where the largest bucket contains O(log log n) balls with high probability. The hash lookup will now search in both the buckets an item hashes to. Since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. Using this fact, we present a simple, practical hashing scheme that maintains a maximum load of 2, with high probability, while achieving high memory utilization. In fact, with n buckets, even if the space for two items is pre-allocated per bucket, as may be desirable in hardware implementations, more than n items can be stored giving a high memory utilization.  Assuming truly random hash functions, we prove the following properties of our hashing scheme:

· Each lookup takes two random memory accesses, and reads at most two items per access.

· Each insert takes O(log n) time and up to log log n + O(1) moves, with high probability, and constant time in expectation.

· The scheme maintains 83.75% memory utilization, without requiring  dynamic allocation during inserts.

We also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. By performing at most h moves, we can maintain a maximum load of O(log log n / h log(log log n / h)). So, even by performing one move, we achieve a better bound than by performing no moves at all.

A Metric Notion of Dimension and its Algorithmic Applications

Robi Krauthgamer, IBM Almaden

Let us define the dimension of a metric space is as the minimum k > 0 such that every ball in the metric space can be covered by 2^k balls of half the radius.  This definition has several attractive features besides being applicable to every metric space. For instance, it coincides with the standard notion of dimension in Euclidean spaces, but captures also nonlinear structures such as manifolds.

I will survey some recent results dealing with metric spaces of low dimension (under the above definition). This includes embeddings into low-dimensional Euclidean spaces, as well as algorithms for computational problems involving metric spaces, such as Nearest Neighbor Search and the Traveling Salesmen Problem.

Computational Biology: Cool Problems and How to Find Them

Gene Myers, UC Berkeley

We survey a number of current problems that are "hot" in computational biology, what working at the interface is like, and some tips about how to go about it.