[Lowerbounds, Upperbounds]

Update 2008-05-08: Please note that this post was written before I started using svninfo, and I highly recommend it if you are dealing with multiple source files. You still need to set the Id keyword property on each source file, but the double dollar trick is not really needed. See the \svnInfo command.

For each file in a Subversion repository, we can specify a list of name-value pairs which are called “properties”. Properties can be used for any purpose (useful for automation scripts), and they are versioned just like the content of the files.

Some properties, however, have special meanings in Subversion. For example, the automatic end-of-line conversion feature relies on the svn:eol-style property. And in this post, we will look at another one: svn:keywords.

To use the svn:keywords feature, you insert special tags like $keyword$ into your file. There are currently five keywords in Subversion: Date, Rev, Author, URL, Id. The idea is when you commit a file, Subversion will automatically expand the keywords inside the file.

To use this feature, first add the svn:keywords property to the files that you want keyword expansion. For example, svn propset svn:keywords "Date Rev" *.tex will add two keywords to all the TeX files in the current directory.

Then, inside the TeX files, you can insert text fragments like:

Last committed as $ $Rev$ $ on $ $Date$ $


(The extra pairs of dollar signs are added to “eat” the dollar signs that surround Subversion keywords.)

The five keywords are more or less self-explaining. But if you want to dig deeper into advanced features like fixed-width keywords, you can read it here.

P.S. Again it is very convenient to have the properties set automatically for all TeX files in your repository. To do so, here is an example config file that you can use. Any file added after you changed the config file will automatically have their properties set.

SPEAKER: Alan Frieze
TIME: Thursday Sept. 28th, 4:30 PM
PLACE: PPB 300
TITLE: Line of Sight Networks

ABSTRACT:

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 Debany.

Title: Computer Science Unplugged

Speaker: Tim Bell, University of Canterbury, NZ
Author of “CS Unplugged”

Time and Place: Tuesday, Sep 26, 2006 1:30p-3:00p WEH 4625

Abstract:

Computer Science Unplugged is a project that seeks to teach principles of computer science without using computers. It can be used in conjunction with computer courses, in classrooms, and in situations where access to computers is limited. This seminar describes activities that Computer Science academics can use to demonstrate principles of computer science to school children in a variety of settings, and as a warm up for university courses. These activities are “unplugged” — no computers are required.

We will describe how “Unplugged” material can be used for school outreach, and some evaluation and lessons learned over the years will be presented.

Approximation Algorithms for Broadcast Scheduling

Nikhil Bansal
IBM T. J. Watson Research Center

Friday, September 29th, 2006, 3:30 pm
Wean Hall 7220

Abstract

We consider the following problem in the broadcast scheduling model. There are n pages at a broadcast server, and at each time slot the server receives several requests for these pages. The server can transmit exactly one page per time slot, and once a page is transmitted, it satisfies all the requests waiting for that page. The goal is to find a broadcast schedule that minimizes the average waiting time of requests.

I will describe a poly-logarithmic approximation ratio for this problem, that improves upon the previously known bound of O(n^{1/2}).

This is joint work with Don Coppersmith and Maxim Sviridenko.

SPEAKER: Michael Dinitz
TIME: Wednesday 12-1pm, September 27, 2006
PLACE: NSH 1507
TITLE: Spanners with Slack

ABSTRACT:

Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion; spanners have been widely studied in the literature for over two decades, and a variety of tight results are known. For instance, it is known that any metric has a spanner with O(n) edges that approximates distances to within an O(log n) distortion.

In this talk we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into L_p spaces. For instance, we show that if we ignore an epsilon fraction of the distances, we can get spanners with O(n) edges and O(log(1/epsilon)) distortion for the remaining distances.

Among other results in this talk, we show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. Finally, we also review notions of average distortion (without slack) previously studied in the literature, and show that our slack spanner constructions give us constant average distortion spanners.

This is joint work with Hubert Chan and Anupam Gupta

34 Years of Bin Packing

David S. Johnson
AT&T Labs

Friday, September 29, 2006
10:30am - SENSQ 5317

Abstract

In the bin packing problem, one is given a list of 1-dimensional items and asked to pack them into a minimum number of unit-capacity bins. This was one of the first NP-hard problems to be studied from the “approximation algorithm” point of view, and over the years it has served as a laboratory for the study of new questions about approximation algorithms and the development of new techniques for their analysis. In this talk I present a brief survey of this history, covering worst-case, average-case, and experimental results, and leading to the new “sum-of-squares” algorithm for the problem.

Friday, September 22nd, 3:30pm WEH 7220

Title: Agnostically Learning Halfspaces
Speaker: Dr. Adam Klivans, University of Texas at Austin

Abstract: 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 R^n, as well as under any log-concave distribution over R^n. It also agnostically learns Boolean disjunctions in time 2^Õ(√n) with respect to any distribution. The new algorithm, essentially L_1 polynomial regression, is a noise-tolerant arbitrary-distribution generalization of the “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. Our Fourier-type algorithm over the unit sphere makes use of approximation properties of various classes of orthogonal polynomials.

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

SPEAKER: Ryan O’Donnell.
TIME: Wednesday 12-1pm, September 20, 2006.
PLACE: NSH 1507
TITLE: Testing Dictators (and the hardness of approximating Max-Cut-Gain)

ABSTRACT:

“Dictator functions” are functions f : {0,1}^n -> {0,1} of the form f(x) = x_i. Given an unknown function f, a “dictator test” involves querying f(x) at an extremely small number of random points x and performing a test on the results. The test should pass with significantly higher probability when f is a dictator function than when f is far from being a dictator function.

The main interest in highly query-efficient dictator tests is they can usually be transformed into hardness-of-approximation results for basic algorithmic problems like Max-3LIN, Min-Vertex-Cover, etc. (using PCP technology).

In this talk we will review some known 2-query and 3-query dictator tests. We will then describe a new 2-query dictator test and show how it leads to an optimal new hardness-of-approximation result for the Max-Cut-Gain problem.

This includes joint work with Subhash Khot of Georgia Tech.

On Nash Equilibria for a Network Creation Game
Susanne Albers
Friday, September 8th, 2006, 3:30 pm
Wean Hall 7220

Abstract

We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of alpha per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. Fabrikant et al. proved an upper bound on the price of anarchy of O(sqrt(alpha)). They also formulated a tree conjecture stating that there exists a constant A such that, for any alpha > A, all non-transient Nash equilibria form a tree. They showed that if the tree conjecture holds, the price of anarchy is constant, for all alpha.

We disprove the tree conjecture, i.e. we construct a family of arbitrarily large graphs that contain cycles and form non-transient Nash equilibria for non-constant alpha. Furthermore, we give improved upper bounds on the price of anarchy. We develop a constant upper bounds for alpha in O(sqrt(n)) and for alpha >= 12n log n. For the intermediate values we show an improved bound of O(1+ min{ alpha^2/n, n^2/alpha }^{1/3}). Additionally, we present characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.

Joint work with Stefan Eilts (Freiburg) and Eyal Even-Dar, Yishay Mansour and Liam Roditty (Tel-Aviv).

Mor Harchol-Balter
What Analytical Performance Modeling Teaches Us About Computer Systems Design

ABSTRACT:

Computer systems design is based on many commonly-held beliefs and heuristics, many of which have never been challenged:

* Thousands of server farm “load balancing” policies do exactly that — they aim to balance the load among the servers. But is load balancing necessarily a good thing?

* Consider a choice between a single machine with speed s, and n identical machines with speed s/n. Which would you choose? Are you always right?

* Scheduling policies which favor “short” jobs, like Shortest-Remaining-Processing-Time-First (SRPT) are often avoided because it is feared that they starve the “long” jobs. But does favoring “short” jobs necessarily hurt “long” ones?

* Cycle stealing between a “donor” machine and a “beneficiary” machine is a central theme in distributed systems. The donor machine helps the beneficiary machine with jobs, whenever the load at the donor machine is below some threshold. But why are we giving the donor machine all the control?

In this talk, we will consider these and other fundamental questions in system design and look at how new research in analytical performance modeling helps us overturn some age-old beliefs.

When: Tuesday, September 12, 3:00 p.m.
Where: 3305 Newell-Simon Hall

David Eckhardt, Associate Teaching Professor in Computer

Colloquium on Computer Science Pedagogy:
The Herbert A. Simon Award for Teaching Excellence in Computer Science Lecture

Abstract:

Teaching systems courses necessarily bears some resemblance to trench warfare. One’s boots are firmly in the muck and blue sky is seen rarely and briefly. Can we learn things of general value while engaged in such a grimy pursuit?

In this talk, I will attempt to draw lessons about abstraction and debugging from some time spent in the trenches. I will also make a few teaching-strategy suggestions in the hope that they may be of use to others. Finally, I will suggest that we add a data structure to our undergraduate curriculum in an attempt to improve retention of skills and encourage reflective professional development.

Posted here:

http://www.cs.colorado.edu/~hal/alist.txt

Update: Some stats are available in this post in Geomblog.