[Lowerbounds, Upperbounds]

It has been complained to me that I use long variable names in my code, which I think is a defendable practice. Worse, I also use stupidly long “abbreviations” in LaTeX

\newcommand{\LovaszLocalLemma}{Lov\'asz Local Lemma}

which doesn’t abbreviate at all…

Well, these complaints are understandable, but what if you don’t have to type these long words in full?

Type this_super_very_super_long_word into Emacs. Press Enter. Now type th and then hit Alt-/. Bang!

I can’t imagine how many seconds of my life I have saved with this feature (surely more than the time it takes me to compose this post to share it with you). These days, even when I type moderately long word like moderately, I use completion.

Vim users don’t have to feel left out. Try Ctrl-P and Ctrl-N instead.

P.S. The next complaint I will get is that Alt-/ is not all that easy to hit. I agree. That’s why I have this line in my .emacs:

(global-set-key [(control ?h)] 'dabbrev-expand)

Your key choice may vary.

TITLE: Disrepancy games
SPEAKER: Michael Krivelevich
WHEN: March 2, 4:30pm
WHERE: PPB 300

ABSTRACT:

A discrepancy game played on a hypergraph $H=(V,E)$ by two players, Balancer and Unbalancer. They select one element of the vertex set $V$ alternately, until all vertices are selected. Balancer wins if at the end of the game all edges $e$ in $E$ are roughly equally distributed between the two players.

We derive a criteria for Balancer’s win in a general discrepancy game. In particular, it follows from our result that if $H$ is $n$-uniform and has $m$ edges, then Balancer can achieve having between $n/2-c\sqrt{n\ln m}$ and $n/2+c\sqrt{n\ln m}$ of his vertices on every edge $e$ of $H$.

We also discuss applications in positional game theory.

A joint work with Noga Alon, Joel Spencer and Tibor Szab\’o.

Speaker: Srinath Sridhar

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Parameterized Algorithms for Steiner Tree Variants

Abstract:

Steiner tree problems naturally come up in diverse applications. It is sometimes necessary to find optimal solutions for such problems. Finding Steiner minimum trees on hypercubes is equivalent to finding the shortest evolutionary tree. In this talk, I will define two variants of the problem both of which are NP-complete. The problems can however be characterized by a parameter which is assumed to be small in practice. The first problem can be solved in time exponential in the parameter and polynomial in the size of the input. This shows that the problem is ‘fixed parameter tractable’ (FPT). The second problem can be solved in polynomial time if the parameter is a constant. I will go over prior work and provide an overview of the algorithms.

Starting from my inbox, I discovered that

The Art of Computer Programming, Volume 4, Fascicle 4 : Generating All Trees–History of Combinatorial Generation

is available for sale now. Here is a totally no-commission-involved link to the item on Amazon.com. The previous three fascicles are of course also available.

“Computers and the Future of Mathematical Proofs”

Thomas Hales, Mellon Professor
U. of Pittsburgh, Dept. of Mathematics

Friday, February 24, 3:30 pm
2500 W. W. Posvar Hall

Presented by Pitt’s Ctr. for Philosophy of Science ANNUAL LECTURE SERIES

Abstract: It is relatively common for the mathematical proof of a single theorem to run hundreds or even thousands of pages. It has also become common for mathematical proofs to rely on computer-assisted calculations. An editor of one of the most prestigious mathematical journals has recently declared that it has become impossible to find peers who are willing to review computer code. As a result, the journal has started to publish theorems without any meaningful review of the underlying computer code. What do these developments mean for computers and the future of mathematical proofs?

(Location Map)

A Geometric Perspective on Learning Theory and Algorithms
Professor Partha Niyogi, University of Chicago

Tuesday, February 28, 2006
3:30 -4:30 pm
5409 Wean Hall

Abstract:
Increasingly, we face machine learning problems in very high dimensional spaces. We proceed with the intuition that although natural data lives in very high dimensions, they have relatively few degrees of freedom. One way to formalize this intuition is to model the data as lying on or near a low dimensional manifold embedded in the high dimensional space. This point of view leads to a new class of algorithms that are “manifold motivated” and a new set of theoretical questions that surround their analysis. A central construction in these algorithms is a graph or simplicial complex that is data-derived and we will relate the geometry of these to the geometry of the underlying manifold. Applications to embedding, clustering, classification, and semi-supervised learning will be considered.

Speaker: Abraham Flaxman

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Handy distributions for average-case anaylsis

Abstract:
Since I managed to sneak in practice for my job talk at a Theory Lunch last month, (thanks for the feedback everybody!), I will regale you with an informal survey of some of the many distributions for random graphs and other structures that have been popular in average-case analysis of combinatorial algorithms.

From Prof. Kavita Ramanan from the Math Department:

The informal ‘Graduate Students Seminar’ on “The Coupling Method” that I am running is being held from 2:30–4:00 (it is usually done around 3:30 or 3:45) on Fridays at Wean Hall 6423. We are following the book “The Coupling Method” by Torgny Lindvall, though we will also read papers, etc. We have so far had just two lectures that have covered the first, introductory, chapter of the book by Lindvall and the related background material from Appendix 2.

Refreshments (pizza, coke) will be served.

To put yourself on the seminar mailing list, send an e-mail to spredoiu at andrew.cmu.edu.

IMPORTANT: Every week, anyone who plans to attend the seminar on Friday should e-mail Gerard Brunick — gbrunick at andrew.cmu.edu — by Thursday noon, so we can order the right amount of refreshments.

All students that plan to attend (reasonably) regularly are welcome.

When: Friday, February 17, 12:00 p.m.

Where: 1507 Newell-Simon Hall

Andreas Krause

Abstract:
When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able to communicate efficiently. In this talk, I will present our data-driven approach that addresses the three central aspects of this problem: measuring the predictive quality of a set of sensor locations (regardless of whether sensors were ever placed at these locations), predicting the communication cost involved with these placements, and designing an algorithm with provable quality guarantees that optimizes the NP-hard tradeoff. Specifically, we use data from a pilot deployment to build non-parametric probabilistic models called Gaussian Processes (GPs) both for the spatial phenomena of interest and for the spatial variability of link qualities, which allows us to estimate predictive power and communication cost of unsensed locations. Using these models, we present a novel efficient algorithm, pSPIEL, which selects Sensor Placements at Informative and cost-Effective Locations. Exploiting two important properties of this problem — submodularity and locality — we prove strong approximation guarantees for our pSPIEL approach. We also provide extensive experimental validation of this practical approach on several real-world placement problems, demonstrating significant advantages over existing methods.

Ryan O’Donnell, MIT/Microsoft Theory Group

Feb 20, 2006
NSH 3305, 1:30pm

Abstract:
For most constraint satisfaction problems — such as finding the maximum cut in a graph, or trying to solve an overconstrained system of equations — it is NP-hard to find an optimal solution. Nevertheless, one still wants to find algorithms that come as close to the optimum as they can. Unfortunately, the best known algorithms and the best known NP-hardness results do not yet match for many basic problems.

In this talk I will talk about recent attempts to find the sharp boundaries between P and NP for approximating constraint satisfaction problems. Interestingly, progress on proving hardness results mostly comes by finding more efficient algorithms in the area of “property testing”. I will describe new such algorithms and mention how their analysis is connected to such diverse areas as voting theory and the “double bubble” problem. As an example consequence of these connections, we get complexity-theoretic evidence that there is no efficient algorithm for finding the maximum cut in a graph with guarantee better than Goemans-Williamson’s: 0.878567….

BIO: Ryan O’Donnell received his Ph.D. from MIT in 2003, advised by Madhu Sudan. He then went to the Institute for Advanced Study as a postdoc under Avi Wigderson and is currently a postdoc at Microsoft Research. Ryan received a Best Student Paper award at CCC for his paper “Hardness amplicification within NP” and a Best Paper award for his paper “Extremal properties of polynomial threshold functions”. His research focus is on complexity theory, hardness of approximation, discrete fourier analysis, and computational learning theory.

Bert Zwart, Eindhoven University of Technology

NSH 3305, 1:30PM

Abstract:
Processor Sharing (PS) queues were originally introduced to analyze the performance of time-sharing in computer networks. Nowadays, PS queues are one of the most popular congestion models for TCP traffic on the Internet. Under the PS discipline, each customer in the system receives the same service rate.

Motivated by obtaining a better understanding of the impact of reneging (e.g. aborting the download of a file) in communication networks, we consider a PS queue in overload where customers may leave after a certain amount of time, before their service is finished. Under the PS service discipline, such behavior is unwelcome, since it always implies that some work is done in vain. Therefore, when the queue is in overload, the actual throughput can be much lower than the total service rate.

We consider a fluid approximation of this queue, which is accurate when both the arrival and service rates are large. We apply this fluid approximation to analyze the impact of reneging on system performance in PS queues. By studying several examples, we show that the impact can be quite substantial and propose an admission control scheme to reduce its effect.

BIO:

Bert Zwart received his Ph.D at Eindhoven University of Technology in september 2001 under the supervision of Onno Boxma and Sem Borst. After that, he did a postdoc at INRIA Rocquencourt (France). In 2002, Bert returned to Eindhoven as an assistant professor. Bert is currently associate editor of Mathematics of Operations Research and serves as TPC member in several conferences.His current research focuses on various topics in applied probability and the performance analysis of computer and communication systems.

Some days ago I was walking in the University Center (a social activity building on our campus) and I saw Mike Shamos.

For those of us who studied Computational Geometry, Mike probably needs no introduction. Mike is also famous for being an expert witness in many computer software and electronic voting cases. (For a technical readership, the DeCSS case is probably the most notable.) But since Mike is often seen on campus, what makes this post interesting?

Well, when I saw him, he was actually standing at the billiards tables and speaking with a cue stick. This scene was completely unexpected to me back then. Out of curiosity, I stopped by the tables and from the audience I learned that he was in fact teaching introductory billiards that day. Having watched his amazing demonstrations, from that day on, I have a new understanding of billiards.

You’re Invited to Celebrate Gary Miller’s 60th Birthday at MillerFest 2006!

April 19-20, 2006
Carnegie Mellon University, Pittsburgh, PA

We are celebrating Gary Miller’s 60th birthday this spring with a banquet and workshop. The banquet will be held Wednesday evening, April 19th, at the Pittsburgh Athletic Association, with the workshop occurring on Carnegie Mellon’s campus the following day. The workshop will feature presentations related to Professor Miller’s research achievements, including computational number theory, randomized algorithms, parallel algorithms, and scientific computing.

For more information, please see the workshop web site:
http://www.aladdin.cs.cmu.edu/workshops/millerfest/

Please register online as soon as possible since this will help us with planning. There is no fee to attend the workshop if you register by Monday, April 3rd. There is small fee to attend the banquet, which promises to be an enjoyable evening featuring reminiscences about the life and career of Professor Miller.

Out-of-town visitors should make their hotel reservations by Wednesday, March 29th, to take advantage of the pre-negotiated workshop rate of \$105 per night (\$119.70 including taxes) at the Holiday Inn near campus. To make your reservations, call the the Holiday Inn (100 Lytton Avenue, Pittsburgh, PA 15213) at 412-682-6200 and be sure to ask for the ALADDIN Workshop rate.

You may also be interested to know that MillerFest is being held in conjunction with CS50, which celebrates fifty years of computer science at Carnegie Mellon. Please see http://www.cs50.cs.cmu.edu/ for a complete schedule of CS50 events.

We look forward to seeing you at MillerFest!

Guy Blelloch, Alan Frieze, and Shanghua Teng

Speaker: Mohit Singh

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs

The minimum spanning tree problem is a fundamental problem in combinatorial optimization. It also has various applications, especially in network design. A favorable property of a connecting network is not only to be ‘cheap’ but also to have ’small load’ on all nodes. A natural way to formulate this problem is via the minimum degree minimum spanning tree (MDMST) problem.

In an instance of the MDMST problem, we are given a graph G=(V,E) and a non-negative cost function c on edges, and the objective is to find a minimum cost spanning tree T under the cost function c such that maximum degree of T is minimized. Here, the maximum degree of T is the maximum degree among all vertices in T.

In this talk, we will present an algorithm for the MDMST problem which returns a MST of maximum degree at most OPT+k where OPT is the minimum maximum degree of any MST and k is the distinct number of costs in any MST of G. We use a lower bound given by a linear programming relaxation to the problem and strengthen known graph-theoretic results on minimum degree subgraphs to prove our result.

This is joint work with R. Ravi.

Several days ago, David asked how to evaluate an adviser and later Lance replied with his post of wisdoms.

David pointed out that he knew of relatively few resources on how to be an adviser. (His post has one link on this.) While I am not ready to write a post of experience like Lance did, I do have a thought to share.

Not long ago, CMU CS alum Scott Berkun gave a talk based on his book on project management. In his talk, Scott told us many interesting stories about his project management experience back in Microsoft. What struck me was his lists of items of “do”s and “don’t”s in management and his list of questions to ask the team members as a project progresses into different stages.

While Scott was focusing on software projects, I believe some of his ideas are applicable to academic advising. For example, he suggests that we should explicitly ask our team members (students) “Do you think you have all the resources you need for you to succeed?” and “Do you feel that this meeting is a waste of your time?” (Whether you get an honest answer back is another matter. And if you don’t expect you can get an honest answer, then you already have a complicated issue to tackle.)

In hindsight, I suppose it’s hardly surprising that academic advisers can draw experiences from software project managers. They are both managing smart people in a creative process. While the two fields have many differences, the human factor can be pretty much the same.

P.S. Scott’s background is in software project management and the book is not directly written for academic advisers. It takes some effort to relate his ideas with advising. So don’t rush out to buy the book and then tell me that you can’t find a short list on how to be an adviser. There isn’t.

After several months of beta-testing, our Theory group’s Subversion server is now open to host any of our projects. If you want to start using this server for a project, please contact me via email so that I can open a repository for you and setup its access control. Note that our server has been configured to support non-SCS collaborators (anyone who doesn’t have an account in the SCS) and so it is very easy to host your papers.

To download and install the required Subversion client, start from this page.

Please read Chapters 1 to 3 of this online book if you are not familiar with the concept of version control and concurrent development. And even if you are already familiar with the basic operations of CVS, it may help to refresh your memory and learn the subtle (but usually not important) differences between Subversion and CVS. If you have questions, feel free to post a comment here.

P.S. My strategy for this rollout is “let it be” for the first couple months. In the past I have struggled to get the beta-testers do everything “right” when none of these seemingly arbitrary subtleties is critical. Therefore, it seems wiser to let everyone use the server and correct the common mistakes later (in future posts and talks).

This is not a post to argue for or against the big-O notation. Instead I just want to share an observation using a toy example.

Consider a dictionary data structure that supports access in logarithmic time. Suppose we have two implementations A and B where A is two times faster than B. (To make it precise but toyish, imagine an access takes $\log n$ time and $2 \log n$ time respectively where $n$ is the number of elements.)

How would this factor of two become important?

Well, when there is a hard upperbound on the amount of time allowed in an access, then the maximum number of elements that can be stored in A is actually the square of that of B.

It’s squared, not just doubled.

Now here’s something to think about. You can have a digital photo album that can store a maximum of two thousand photos or another one with four million photos. They are equally responsive on your computer. Which one would you prefer as a customer?

(Or, perhaps we can wait 18 months and be happy with the former one? )

Random Graphs

Alan Frieze
Carnegie Mellon University

Wean 7220
Feb 10th, 15:30

We will review some of the major results in random graphs and some of the more challenging open problems. We will cover algorithmic and structural questions. We will touch on newer models, including those related to the WWW.

Speaker: Todd Phillips

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Data Structures for Cellular Decompositions

Abstract:

In many applications of comptutational geometry, we seek to store and manipulate a complex geometric collection that has been decomposed into primitive geometric objects (cells). Common examples include the storage of meshes, scenes, arrangements, or embedded planar graphs. Good data structures must efficiently support localized operations for exploring adjacency and containment between these cells. In general, such decompositions may have very complicated neighborhoods and connectedness that can lead to computational topology problems. We will explore state of the art data structures, and we will see how a group theoretic approach to the problem can yield very elegant solutions. We will also present some recent contributions from both algebraic and data structures viewpoints.

Teresa Maria Jeronimo Sousa

“Decompositions of Graphs”

Thursday, February 9, 2006
4:00 p.m.
Posner Hall, Room 259

ABSTRACT:

The subject of graph decompositions is a vast topic and has been studied for the past 40 years by numerous people. Given two graphs $G$ and $H$, an $H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a graph isomorphic to $H$. We allow partitions only, that is, every edge of $G$ appears in precisely one part. Let $\phi_H(G)$ be the smallest possible number of parts in an $H$-decomposition of $G$. We study the function $\phi_H(n)$ which is the smallest number such that any graph $G$ of order $n$ admits an $H$-decomposition with at most $\phi_H(n)$ elements.

Erdos, Goodman and Posa proved that $\phi_{K_{3}}(n)=t_2(n)$, where $t_{r-1}(n)$ denotes the number of edges in the Turan Graph, $T_{r-1}(n)$. This result was extended by Bollobas, who proved that $\phi_{K_{r}}(n)=t_{r-1}(n)$, for all $n \geq r \geq 3$.

We managed to obtain the exact value of $\phi_H(n)$ for some graphs $H$, namely the cycle of length 5, the cycle of length 5 with one chord and any clique-extension of order $r+1$. For $r \geq 3$ a clique-extension of order $r+1$ is a connected graph that consists of a $K_r$ plus another vertex adjacent to at most $r-1$ vertices of $K_r$. For all fixed $H$ with chromatic number $r \geq 3$ we will prove an asymptotic result about $\phi_H(n)$, that is we show that $\phi_H(n)= t_{r-1}(n)+o(n^2)$. For a non-empty graph $H$ we denote by gcd(H) the greatest common divisor of the degrees of $H$. For a bipartite graph with gcd(H)=1 the exact value of the function $\phi_H(n)$ will be obtained, for $n$ sufficiently large.

The proofs presented use Turan’s Theorem, the Regularity Lemma, results of Pippenger and Spencer, Gustavsson’s Decomposition Theorem for dense graphs and results about packing vertex disjoint copies of a fixed graph $H$ into a large graph $G$.

This is joint work with Oleg Pikhurko.