[Lowerbounds, Upperbounds]

Edward R. Tufte is an expert in information design. Some of you may have read his pamphlet The Cognitive Style of PowerPoint (mostly bashing PowerPoint). Here we have his essential ideas in that pamphlet… in the PowerPoint bulleted-list format.

http://www.aaronsw.com/weblog/000931

P.S. I don’t entirely agree with all of Edward’s ideas in the pamphlet, but the pamphlet is a starting point for those of us who really think about our presentations. Maybe I will write about it later.

I just upgraded to WinMerge 2.2.2.0 and I can’t be happier.

WinMerge is a GUI for comparing and merging files. The new merge mode is very handy (F9) and it even highlights what’s changed within a region (F4). It can also compare between whole directories. Get it!

http://winmerge.sourceforge.net/

For those of you that work mostly in the command line (I do), you can put these two lines into wdiff.bat and put it in a directory in your path (I store all my small programs in “C:\Program Files\Misc”):

@echo off
start "" "C:\Program Files\WinMerge\WinMerge.exe" %*

Then you can invoke WinMerge just like diff. Note that %* means “all arguments passed to this batch file”.

The 44th Annual Greek Food Festival is coming!

The is one event that all is at CMU shouldn’t miss. It’s just a 5 minutes walk away from campus and you get really high quality Greek food. From May 8 to May 13, you can expect to see me eating their pastries non-stop. Yum!

Full menu is available at their website.

Today our undergrads put up a really huge poster in the NSH Atrium in honor of their beloved adviser Mark Stehlik. Kudos!

Click on the image to see it at its original size (6MP/2MB).

Do you think we will get another 64MB USB keychain this year?

Just a reminder that the CS Department is sponsoring the
GRAD STUDENT APPRECIATION TG on Friday, April 29 –
5:00 PM in the NSH Atrium.

Please come to be appreciated by the faculty, and to
celebrate the end of classes, the start of exams, summer,
or anything else that floats your boat!

Good food — Mad Mex!
Good drink — a variety!

See you there!

Don’t let Keanu Reeves steal the focus!

This is an excellent tutorial on Singular Value Decomposition (SVD) by Todd Will from UW-La Crosse. I highly recommend it for everybody who deals with Linear Algebra.

http://www.uwlax.edu/faculty/will/svd/index.html

Among other excellent insights, once you read the page on Perpframes, Aligner and Hangers (the 3rd page in that site), you will never see a matrix the same way again. It’s like the, erh, blue pill. (Or is it the red one? )

From arXiv cs daily comes a very interesting paper titled Online Medians via Online Bribery by Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young. Here is part of the abstract:

Our proofs reduce online medians to the following online bribery problem: faced with some unknown threshold T>0, an algorithm must submit “bids'’ b>0 until it submits a bid as large as T. The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bribery.

I suppose this can be a useful skill when I travel to some parts of the world later this summer?

Full information:

Read the rest of this entry »

Sometimes it’s very handy if you define your own math operator and have it behave like other
LaTeX math functions (such as \log). Here is an example of how you can do it:

\DeclareMathOperator{\poly}{poly}

Once defined, you can simply write $O(2^k \poly(n))$ instead of $O(2^k \text{poly}(n))$.

Neat eh?

Over the years I have heard many opinions from graduate students about going to talks not related to their research interests. My impression is that more and more students feel that they should skip such talks because:

• The talk is in an area that they are not familiar with. (”This talk will be way over my head.”)
• They have more important things to do. (”My adviser will not go to such talks either.”)
• Many talks are usually difficult to follow. (”It’s easier to directly read the paper.”)

As some of you may know, recently Avi Wigderson gave a talk in STOC 2004 about why we should listen to talks in other areas. He really seems to have some convincing arguments about why knowing other areas can help your own research. I won’t repeat them here.

And even though the opinion of a small potato like me doesn’t carry any weight, let me add to his list from a less utilitarian perspective (I do not claim Avi’s talk was utilitarian but the motivation he gave in his talk was certainly targeted to convince you of the benefits):

• Manuel Blum once told me that “a PhD should be someone who knows everything about something and something about everything” and I believe him.
• I feel that even very productive graduate students should have more time than their advisers.
• As a community (if it ever existed), we should show up to community events, even just to show our support and appreciation to the speaker and the community itself. (I know this is mostly a culture thing. I am a Chinese and we treasure fellowship.)

What do you think?

P.S. I am spending the last 25 minutes to write this post because today one of our weekly “community event” scheduled at this time has been canceled due to various reasons. I don’t blame anyone for this. We all have our priorities and I respect that. (I lament only solely because there is a lack of free food. You believe me, right? )

Denis Naddef
University of Grenoble, also Tepper School of Business

Friday, April 29
2:00 - 3:30 pm
384 Posner Hall

The Diversity Management Problem

Abstract:

Read the rest of this entry »

Back in March 2005, an EZView user told me about his colleagues who prefer to work at 100% zoom level and how this was driving him insane since he had to change the zoom level every time he opened a presentation. Presumably this is because they work on high resolution (1600×1200) displays but he doesn’t. (Neither do I. My primary machine is an IBM ThinkPad X30 running at 1024×768 even though my desktop can do 16-by-12.)

But given what I’ve learned from writing EZView, I told him confidently, “I can fix it!”

Ladies and Gentlemen, from your Iron Monkey-wanna-be comes a new PowerPoint plug-in: whenever a presentation is opened, it will adjust the zoom level to “Fit”. Please let me know of any bugs.

http://www.cs.cmu.edu/~maverick/Programs/ZoomToFit/

The icon I used is from the Kids Icon Theme by Everaldo Coelho. Kudos!

Colin Cooper

TITLE: The cover time of random walks on random graphs
WHEN: Thursday, April 28, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT:

Read the rest of this entry »

For those of you who use GNU Emacs or Vim, do you know that you can change the color theme/scheme very easily?

Really, take a look at these two pages and look at the varieties that you can get.

• http://www.cs.cmu.edu/~maverick/GNUEmacsColorThemeTest/
• http://www.cs.cmu.edu/~maverick/VimColorSchemeTest/

And in case you don’t know, both GNU Emacs and Vim have native versions in Windows. I use them daily and happily.

Subhash Khot
Georgia Institute of Technology

10:00AM, April 28 Thursday
3305 NSH

Hardness of Approximation Results

ABSTRACT:

Read the rest of this entry »

OK, this is not exactly about a particular open question, but I just thought that maybe you will be interested.

IBM Research’s Ponder This features a problem every month and is open to everyone. Check it out!
http://www.research.ibm.com/ponder/

Usually I am humbled by the questions and those that managed to solve them so quickly. But I will continue to ponder it every month.

An old but classic column by Bill Gasarch: http://www.cs.umd.edu/~gasarch/papers/poll.ps

Inspite of Luis’s “proof” this poll still seems as relevant as ever.

You probably know that you can start a PowerPoint slide show from the current slide by clicking on a tiny icon, but do you know that you can do this with just the keyboard?

I wrote PowerPoint EZView because I am obsessed in getting my drawings accurate to the pixel and needed a fast way to do a full screen preview.

Get it here:
http://www.cs.cmu.edu/~maverick/Programs/EZView/

P.S. If you are using PowerPoint 2003, then you can already do this with Shift-F5. But I have all three recent versions of PowerPoint running on my computers and so EZView supports PPT2K3 too.

Did you know about the string macros in BibTeX files? Here is an example.

Put this line at the top of a bib file:

@string{JACM = "Journal of the ACM"}

Now the journal field of an JACM article can be entered easily like:

@Article{Hastad2001Optimal,
author = {Johan H\aa{}stad},
title = {Some Optimal Inapproximability Results},
journal = JACM,
year = 2001,
volume = 48,
number = 4,
pages = {798--859}
}


Here is a short list of macros that I have used in a recent paper:

Read the rest of this entry »

Check this out…. a new 10 page (only!) proof to the PCP theorem due to Irit Dinur:
http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/index.html

Finally I can hope to try to understand the theorem! And supposedly it uses a purely combinatorial amplification lemma.

Jason Hartline
Microsoft
3:30PM, Friday 2005-04-22
4625 Wean Hall

Derandomization of Auctions

ABSTRACT:

Read the rest of this entry »