Small world, power law and the Internet

http://www-net.cs.umass.edu/cs691s/

Coresets

A coreset is a subset Q of input points P that well approximates P. Unlike \eps-net, \eps-approximation that approximate the input set combinatorially, a coreset approximates the input set under geometric measures. Since a coreset usually has a small size, 1/\eps^{O(1)}, it can be used to speed up many geometric algorithms.

The basic idea is to find a small subset whose convex hull approximates the convex hull of P. A simple algorithm is to put a grid and select one point in each extremal cell. A better algorithm is to put a large ball enclosing all the points, find a nice (uniform) sampling of points on the surface of the ball, and find the (approximate) nearest neighbor in P of each sample point. The collection of (approximate) nearest neighbors is a coreset. The size of the coreset is 1/\eps^{(d-1)/2} (The big enclosing ball is a (d-1)-dim manifold, the sampling rate is about \sqrt{\eps}).

The above algorithm, however, has an exponential dependence on the dimension. For high dimensional data, special techniques are used to find a coreset whose size is only polynomial dependent on dimension.

Hardness of approximation

MAX-SNP problems: with constant approximation but no PTAS.

Examples: MAX-3SAT, Metric TSP, Max Clique on bounded degree graphs.

PCP theorem basically proves that MAX-3SAT, thus all MAX-SNP-complete problems, has no PTAS unless P=NP.

A good course webpage:

http://www.cc.gatech.edu/~khot/pcp-course.html

Symmetric games

Symmetric games: all players are identical and indistinguishable. They have the same strategy sets, their utility functions are the same function of their own strategy and the other players' actions, and this function is symmetric in the other players' actions.

Examples: prinsoner's dilemma.

Nash proved that every symmetric game must have a symmetric equilibrium where all players play the same strategy.

J. F. Nash, Jr. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951.

Introduction to mechanism design

Maintained by David Parkes @ Harvard:

http://www.eecs.harvard.edu/~parkes/mechdesign.html

Survey on optimizations of geometric problems

Approximation schemes for NP-hard geometric optimization problems: A survey, by Sanjeev Arora. Here is a link.

New blog for research use

It's good to keep a record of my (random) thoughts everyday.