[Lowerbounds, Upperbounds]

ALADDIN WORKSHOP ON FLEXIBLE NETWORK DESIGN
November 4-5, 2005
Princeton University

Network Design with its many variants is one of the most active mathematical research areas involving researchers from Theoretical Science, Graph Theory, Operations Research, Discrete Optimization, Game Theory and Information Theory.

The goal of this workshop is to focus on this active area of applications of algorithms to understand current trends, identify understudied areas, and formulate new directions for further investigation. To this end, the workshop participants include an eclectic mix of experts from real-world network design and deployment, graph algorithms, network coding, algorithmic mechanism design applied to pricing problems in networks, and configuration and routing of networks.

REGISTRATION AND ADDITIONAL INFORMATION

There is no fee to attend this workshop, but advance registration is required. For more details about the workshop and to register online, please visit http://www.aladdin.cs.cmu.edu/workshops/netdes/index.html.

QUESTIONS?

For questions about registration, please contact Susan Hrishenko at Carnegie Mellon University, (email susan027@cs.cmu.edu or phone 412-268-7317). For questions about local arrangements, please contact Mitra Kelly at Princeton University (email mkelly@cs.princeton.edu or phone 609-258-4562).

Title: Reconstructing Evolutionary Trees Optimally

Speaker: Srinath Sridhar, CSD

Location: NSH 1507
Time: 12-1 pm
Date: Friday, October 28th, 2005

Abstract:

Evolutionary trees are fundamental to our understanding of the mechanisms of nature. They have been used to solve many important problems, such as tracing the evolution of diverse species and tracking historical human migration patterns. Over the last decade, there has been a tremendous
amount of research in the area bringing together theoreticians and biologists. In this talk, I will focus on reconstructing evolutionary trees optimally by finding the smallest (most parsimonious) tree for an input set of DNA sequences. We will consider an important special case of the problem that is equivalent to finding the minimum Steiner tree in Hamming space. In this talk, I will formulate the problem, prove a simple lower bound on the size of the smallest tree and outline an algorithm to reconstruct it. Finally, I will show experimental results using DNA from humans (multiple ethnic groups) and other primates.

Luis von Ahn

12:00 PM, 3305 Newell-Simon Hall

Thesis Oral

Title: Human Computation

Abstract:

Tasks like image recognition are trivial for humans, but continue to challenge even the most sophisticated computer programs. This thesis introduces a paradigm for utilizing human processing power to solve problems that computers cannot yet solve. Traditional approaches to solving such problems focus on improving software. I advocate a novel approach: constructively channel human brainpower using computer games. For example, the ESP Game, introduced in this thesis, is an enjoyable online game — many people play over 40 hours a week — and when people play, they help label images on the Web with descriptive keywords. These keywords can be used to significantly improve the accuracy of image search. People play the game not because they want to help, but because they enjoy it.

I introduce three other examples of games with a purpose: Peekaboom, which helps determine the location of objects in images, Phetch, which collects paragraph descriptions of arbitrary images to help accessibility of the Web, and Verbosity, which collects common-sense knowledge. I also show that, in principle, every problem that could be solved by a computer, today or in the future, could be solved using enjoyable computer games.

In addition, I introduce CAPTCHAs, automated tests that humans can pass but computer programs cannot. CAPTCHAs take advantage of human processing power in order to differentiate humans from computers, an ability that has important applications in practice.

The results of this thesis are currently in use by hundreds of Web sites and companies around the world, and some of the games presented here have been played by over 100,000 people. Practical applications of this work include improvements in problems such as: image search, adult-content filtering, spam, common-sense reasoning, computer vision, accessibility, and security in general.

Thesis Committee:
Manuel Blum, Chair
Takeo Kanade
Michael Reiter
Josh Benaloh, Microsoft Research
Jitendra Malik, University of California, Berkeley

Daniel Blandford

3:00 PM, 3305 Newell-Simon Hall

Thesis Oral

Title: Compact Data Structures with Fast Queries

Abstract:

Many applications dealing with large data structures can benefit from keeping them in compressed form. Compression has many benefits: it can allow a representation to fit in main memory rather than swapping out to disk, and it improves cache performance since it allows more data to fit into the cache. However, a data structure is only useful if it allows the application to perform fast queries (and updates) to the data.

This thesis describes compact representations of several types of data structures including variable-length arrays and dictionaries, separable graphs, ordered sets, text indices, and meshes. All of the representations support fast queries; most support fast updates as well. Several structures come with strong theoretical results, and all of the structures come with experimental results showing good compression results. (This represents an improvement over many compressed structures, which can be too complex to implement or suffer from high constant factors.) The compressed data structures are usually close to as fast as their uncompressed counterparts, and sometimes are faster due to caching effects.

These data structures are united by a common theme: the use of difference coding to represent data by its difference from other, previously known, data. For example, a compact graph structure represents the neighbors of a vertex by the difference between the neighbor label and the original vertex label. For many structures this is combined with a relabeling scheme which ensures that most of the differences encoded are small. The variable-bit-length arrays and dictionaries represent a general framework for creating compressed queryable data structures. This represents an improvement for many structures, which would otherwise need to be built ad-hoc.

Thesis Committee:
Guy Blelloch, Chair
Christos Faloutsos
Danny Sleator
Ian Munro, Waterloo

Speaker: David Johnson, AT&T Labs - Research

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Compressing Rectilinear Pictures, with Applications to the Internet

Abstract:

We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers. This model is a generalization of one previously studied in the context of rectilinear picture compression. It embodies an optimization problem that arises when drawing figures using common software packages such as Excel and Xfig.

Here the goal is to create a colored rectilinear pattern within an initially white square canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Motivated by the ACL application, we study the special case in which all rectangles must be strips that extend either the full length or the full height of the canvas. We provide several equivalent characterizations of the patterns achievable in this special case and present a polynomial-time algorithm for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also bound the improvement one can obtain by using arbitrary rectangles in the construction of such patterns, and analyze heuristics for the case of general patterns.

This is joint work with David Applegate, Gruia Calinescu, Howard Karloff, Katrina Ligett, and Jia Wang.

TITLE: On a conjecture of Berge and Simonovits on hypergraph products
SPEAKER: Dhruv Mubayi, University of Illinois, Chicago
WHEN: October 27, 12-1pm
WHERE: Wean Hall 5403

ABSTRACT:

The product of hypergraphs $G$ and $H$ has vertex set equal to the cartesian product of $V(G)$ and $V(H)$, and edge set equal to the set of all cartesian products of edges in $G$ with edges in $H$. We construct a hypergraph sequence $G_n$ for which the chromatic number of $G_n$ approaches infinity, and yet the chromatic number of the product of $G_n$ with itself is $2$. This disproves a conjecture of Berge and Simonovits from the early 70’s. On the other hand, we show that if $G$ and $H$ are hypergraphs with infinite chromatic number and finite edge sizes, then the chromatic number of the product of G and H is also infinite. We also provide a counterexample to a “dual” version of their conjecture, by constructing a graph sequence $G_n$ for which the independence ratio tends to $0$, and yet the independence ratio of the product tends to $1/2$. The constant $1/2$ cannot be replaced by a larger number. The construction is obtained via connections to Ramsey-Turan theory, and addresses a question of Kostochka. We will end with some open problems.

This is joint work with Vojtech Rodl.

Friday, October 28, 2005
1:30 pm Posner Hall 151

Dimitris Bertsimas
Sloan School of Management, MIT

Robust and Adaptive Optimization: A Tractable Approach to Optimization under Uncertainty

For almost all its history, the predominant model in Operations Research to describe uncertainty is probability theory. Optimization under uncertainty, however, when the primitive elements are probability distributions suffers from the curse of dimensionality, and thus it does not have a tractable theory.

We show that when the primitive elements to describe uncertainty are polyhedral or conic uncertainty sets, the central models of optimization (linear, mixed integer, conic) under uncertainty, models known as robust optimization, can be reformulated as optimization problems of the same structure and a mild increase in the dimension, and thus are tractably solvable both practically and theoretically. We also show how to construct uncertainty sets from data and risk preferences.

We further describe adaptive optimization, a tractable theory for optimization under uncertainty with recourse when uncertainty is described via uncertainty sets.

We finally present applications of these methods to: optimal control, inventory theory and multiperiod asset allocation.

This will be a “long weekend” for many of us.

On Friday and Saturday, there will be FriezeFest. As of this morning, all the abstracts for FriezeFest are up. There is already some press coverage about FriezeFest on the Pittsburgh Post-Gazette.

On Saturday afternoon, there will be two FOCS Tutorials, colocated in the same building with FriezeFest. Subhash’s session is also listed on the FriezeFest schedule, so he may get an interesting mix of audience in the auditorium. As for Bernard’s, well, he may get some “competition” from FriezeFest, but then he’s going to get a hardwood floor ballroom. At CMU we hold a lot of music and dance events there. If there can be music before his session, would it be Jazz?

FOCS will be in downtown Pittsburgh from Sunday to Tuesday. The program has been published for some time. Of special note is the panel discussion at the business meeting on Sunday night. The topic will be “Exciting the public about (theoretical) Computer Science”. Does that mean we need more beverage or less beverage during the business meeting?

Incidentally, there is also a joint meeting of the National Association of Science Writers and Council for the Advancement of Science Writing in the same hotel with FOCS. Their theme will be about Science in Society and New Horizons in Science. Perhaps we can get some science writers to come over to the business meeting and get them excited about TCS?

Finally, there is an increased number of talks at CMU this week due to people flying in for FOCS. You can see the long list of events on the frontpage of this blog. Oops, Dorit Hochbaum is about speak in this week’s OR Seminar in roughly -5 minutes… Got to go.

TITLE: Anti-Ramsey and Canonical Ramsey type problems
SPEAKER: Tao Jiang, Miami University, Oxford, OH
WHEN: 4-5pm, October 20
WHERE: PPB 300

We discuss a collection of problems that deal with color patterns in edge-colorings of the complete graph under various constraints. A subgraph $H$ in an edge-colored host graph $G$ is monochromatic if all edges of $H$ have the same color, rainbow if all the edges of $H$ have different colors, and properly colored if no two incident edges have the same color.

Here are some examples of the problems to be discussed.

(1) Given a graph $H$ and a positive integer $n$, what is the maximum number $R^*(n,H)$ of colors in an edge-coloring of $K_n$ that does not contain a rainbow copy of $H$? This maximum number is called the anti-Ramsey number of $H$. Anti-Ramsey numbers are closely related to the Turan numbers.

(2) Given two graphs $G$ and $H$, what is the smallest $n$ such that in every edge-coloring of $K_n$ (using any number of colors) there must exist either a monochromatic copy of $G$ or a rainbow copy of $H$? This problem is motivated by the Erdos-Rado Canonical Ramsey Theorem and has been studied by various researchers in different contexts.

(3) Given a graph $H$ and a positive integer $n$, what is the maximum $k$ such that in every edge-coloring of $K_n$ in which each color appears at most $k$ times at each vertex there must exist a properly colored copy of $H$? a rainbow copy of $H$?

We will give a brief history of these problems, their connection to each other, and mention some results and open problems.

Speaker: Nina Balcan

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Mechanism Design via Machine Learning

Abstract:

In this work, we make an explicit connection between machine learning and mechanism design. In doing so, we obtain a unified approach for considering a variety of profit maximizing mechanism design problems, including many that have been previously considered in the literature. In particular, we use techniques from sample-complexity in machine learning theory to reduce problems of incentive-compatible mechanism design to standard algorithmic questions. We apply these results to a wide variety of revenue-maximizing pricing problems, including the problem of auctioning a digital good, the attribute auction problem, and the problem of item-pricing in unlimited-supply combinatorial auctions.

It is worth noting that from a learning perspective, these settings present several unique challenges: the loss function is discontinuous and asymmetric, and the range of bidders’ valuations may be large.

This is joint work with Avrim Blum, Jason Hartline, and Yishay Mansour, to appear in FOCS’05.

Wednesday, October 19, 2005
1:30 pm Posner Hall 151

Dorit Hochbaum
Haas School of Business, Berkeley

What do sport ranking, group decision making, multicriteria decisions, customer segmentation, medical prognosis and assessing bankruptcy risk have in common?

The problems of aggregate ranking or group decision making (or any of the others listed in title) are challenging. We review some known models for the problems and present alternative models. The new models overcome some of the shortcomings of existing models and offer flexibility. Moreover, these models are linked to network flow problems (with convex objective) and to inverse problems. We provide polynomial time algorithms using network flow techniques such as parametric cut and fractional multicommodity linear programming.

TITLE: Embedding into $l_p$ with constant average distortion
SPEAKER: Ofer Neinman, Hebrew University of Jerusalem
WHEN: 12:00-13:00, October 20
WHERE: Wean Hall 5403

ABSTRACT:

An embedding is a function between metric spaces, usualy from an arbitrary one into a more simple and structured space (such a Euclidean space). The distortion is the multiplicative amount by which distances change. A well known theorem of Bourgain states that every metric space embeds into Euclidean space with $O(\log n)$ distortion, which is tight. Our result is a strengthening of Bourgain’s Theorem, providing a CO-Lipschitz embedding with constant average distortion. As a matter of fact, it provides for any $\epsilon$ the best $\epsilon$-slack distortion simultaneously.

This is joint work with Yair Bartal and Ittai Abraham.

Monday, October 17, 4:30 pm, Wean Hall 7500 (Coffee at 4:15)

Speaker: Robert Griffiths (CMU)

Title: Dense Coding Using Quantum Entanglement

Abstract:

Entanglement is a somewhat mysterious property of a quantum system, one with no direct classical analog. Dense coding is a process in which entanglement can be used to increase the capacity of a quantum channel to carry information by a factor of two, despite the fact that entanglement by itself does not transport information. The question addressed in this talk is how dense coding, both the original protocol (Bennett and Wiesner) and some more recent variations thereof, can help us understand entanglement and its role in quantum information theory.

I just discovered that there is another book about TeX that has been “freed”:

TeX for the Impatient
ftp://ftp.tug.org/tex/impatient-1.0/book.pdf

I have not found time to read it yet, but flipping through the PDF suggests that this is a pretty good book.

As for why you would want to read about TeX? Well, at least you can tell confidently which one of the following five gives a different (probably unintended) output:

1. H{\aa}stad
2. H\aastad
3. H\aa
stad
4. H\aa{}stad
5. H\aa stad

and perhaps even explain the (visually non-existent) differences between the other four.

P.S. I feel obligated to make sure you really know 2 is wrong unless you really have defined \aastad. 1 and 4 are better because they are less confusing. A control word “eats” the spaces and also the end-of-line after it, hence 3 and 5 both “work” but for a less obvious reason.

If you use Emacs to edit your LaTeX files, then you want to know about Local Variables. They are “comments” that you write at the end of a file, say in this example:

blah blah

% Local variables:
% mode: latex
% TeX-master: "main.tex"
% End:

The purpose of local variables is to allow you to give Emacs extra customization when you load a file. In this example, we want Emacs to switch to latex mode and set the TeX-master variable to “soda.tex”. mode is actually a special variable controlling the major mode of the file. The TeX-master variable is used by AUCTeX so that when you invoke LaTeX on the current buffer (Ctrl-C Ctrl-C), it will instead invoke LaTeX on the “master” file. This is crucial when you break the paper into multiple files and use \input to string them together because this alleviates the need to switch to the master file before you invoke LaTeX.

There is also another way to specify local variables by putting them in the beginning of a file. Here is how our example would look like:

% -*- mode: latex; TeX-master: "main.tex"; -*-

blah blah

There is also a special local “variable” call eval. The value for that variable is simply evaluated as an expression, and hence it can actually be somewhat dangerous. Fortunately Emacs also provides enable-local-eval to let you catch the evals.

Happy TeXing in Emacs!

This week I am recollecting what services I enjoyed at past conferences, and perhaps more importantly, what services I would like them to have but they didn’t. By “services”, I mean things that are mostly for the convenience of the attendees. Traditional things like “local maps” and “unlimited supply of bottled water” (*) are in this category, but specialties like “a blog set up for the conference” are also OK. (AAAI did it.)

Note that I am *not* in charge of the Local Arrangements of FOCS 2005, so I can’t guarantee anything. But I can guarantee that your inputs will be heard. In fact, I imagine such a list can be useful to organizers of any conference, so consider my posting of this right before FOCS merely a coincidence.

To make this post extensible, I guess I am going to use the threaded-comments feature and post my day-dreaming one at a time. Please feel free to chip-in yours. It can only make better conferences.

Note also that there is an RSS feed for the comments on this site, so you don’t have to come back to check the comments.

(*) I don’t necessarily think the latter is a good thing due to environmental concerns, but it does have its appeal over cups… Plus, the hotel may not like the idea unless you order from them at their price…

In some publications(*), space is at a premium. While I do not recommend tuning your baselinestretch in the main body of a paper, I believe there are other reasonable things to tweak. In particular, I often find the space used by itemized lists to be a bit more than desirable. But how can we cut the space down without inserting \vspace*{-1ex} before every \item?

Well, I just figured it out last week: you want to use the paralist package. What it does is to provide several new list environments that consume no space between list items by default. You can add some space back in, but this time you can control the amount. Here is an example:

\usepackage{paralist}
\setlength{\pltopsep}{0.5ex} % space before first item
\setlength{\plitemsep}{0.25ex} % space between items
\newenvironment{itemizeC}{\begin{compactitem}}{\end{compactitem}}

The last line in the example is really just for convenience if you happen to want to switch between normal lists and compact lists easily.

Also note that paralist is quite a feature-rich package. Among other things, it can let you customize the item bullets and margins, as well as providing an enumerated list environment inparaenum that wraps its items in a paragraph like: (i) blah; (ii) blah blah. Be sure to check out its documentation!

(*) You know I really meant conference proceedings, don’t you?

I have installed Instiki on Abu. Instiki is a wiki server intended for simple wikis. The server itself is written entirely in Ruby and is extremely extensible. In its lingo, a server hosts a list of “webs”, each corresponding to the wiki of a project. To see the current list of webs hosted by Abu, use this URL:

http://abu.aladdin.cs.cmu.edu/

So far we have two sandboxes for playing and two actual webs. There is a web unofficially used by the FOCS 2005 local arrangements (I guess we really just use it as a notepad online). There is also a web called Papers Illustrated, which is Dan Golovin’s brain child if you recall the Town Meeting we had in the beginning of the semester. PI is password protected for the moment, but most CMUers know the password anyway. I imagine that when PI gets more content, we will publish the web so that Google can crawl it.

I have also patched Instiki a bit to add ASCIIMathML to it. Now you have another way to play with ASCIIMathML by going into the Sandbox.

Finally, since we have the server software set up already, if you want to have your own simple wiki hosted on Abu, let me know. Instiki is not as industrial-strength as MediaWiki, but it is probably adequate for most small projects.

Cheers!

Speaker: Vineet Goyal

Time: Wednesday 12-1pm

Place: NSH 1507

Title : How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems

Abstract:

Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new “demand-robust'’ model motivated by recent work on two-stage stochastic optimization problems. We propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and uncapacitated facility location. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting.

This is joint work with Kedar Dhamdhere, R. Ravi and Mohit Singh.

Fumei Lam
Massachusetts Institute of Technology

Friday, October 14, 2005
1:30 - 3:00 pm
Room 151

Traveling Salesman Path Problems

In the Traveling Salesman Path Problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. The problem is a generalization of the Traveling Salesman Problem with many important applications.

We’ll survey approximation algorithms for this problem and present properties of the polytope corresponding to a linear programming relaxation. We consider the set of traveling salesman path perfect graphs, graphs for which the convex hull of incidence vectors of traveling salesman paths can be described by linear inequalities. We show such graphs have a description by way of forbidden minors and also characterize them constructively. We extend these results to relate the underlying graph structure to the integrality gap of the corresponding fractional path polyhedron.

Joint work with Michel Goemans, Alantha Newman, and Santosh Vempala.