[Lowerbounds, Upperbounds]

On average, I get asked the following question about once a month:

Are there symbolic links in Windows, similar to the ln -s target_name link_name on Unix?

Let me answer it here once(*) and for all. The answer is “yes”. NTFS supports a similar concept called junctions. Sysinternals even has a free utility for you to manipulate junctions.

http://www.sysinternals.com/Utilities/Junction.html

To create a junction, say junction link_name target_name.

(*) although in reality I don’t expect most that will ask me such questions to read this blog…

Do you know that Perl “regular expressions” can accept NP-complete languages?

http://perl.plover.com/NPC/

Happy backtracking!

I consider it a good habit to always insert a \label right after you open a new section (and subsection and subsubsection), regardless of whether you think you will want to refer to it later. You won’t believe how often I see friends hardcoding section references because they are too “busy” to go back to add the \label. Of course, all is good as long as the section numbering doesn’t change…

And just like using \cite, please be sure to always precede a \ref with a tilde to avoid having a section number in the beginning of a line.

Here is an example usage. To declare a label,

\subsection{Grid Minor and Treewidth}
\label{sec:grid-tw}

and to refer to that section,

As we have seen in Section~\ref{sec:grid-tw}, the existence of a $k-by-k$ grid minor in $G_A$ is inevitable.

I have inherited from the Emacs AUCTeX package the habit of prefixing all the (sub)sections by sec:. Similarly, all theorem-like labels are prefixed by thm:.

Do you know that you can double-click on a drawing tool in PowerPoint and continue drawing new instances of the same object type until you click on another tool or press Esc?

This is very handy when you need to draw many different instances of the same type of object. Connectors come to mind. (In fact, I can hardly think of any other tools of which this trick is more relevant.)

There are actually three kinds of dashes in LaTeX, each serving a different purpose. Let’s use them well.

• The intra-word one is simply a single dash. Example:
  

  I like ice-cream.

• We should use two dashes to indicate number range. The most common place this comes up is in the bib file. Note that there should be no space surrounding it. Example:
  

  pages = {293--299}

• The last one is the actual dash punctuation where there are three dashes in a row and again there should be no space surrounding it. Example:
  

  Sometimes it's difficult---or even downright impossible---to come up with a short example sentence.

LAMPS OF ALADDIN ANNUAL PROJECT REVIEW
Wednesday, May 11, 2005
10:00 am - 5:00 pm
Newell Simon Hall 3305

You are invited to attend any sessions of interest during this day-long workshop in which students will present their recent research results or outline ongoing work. The primary purpose of this review is to inform other students and faculty of research that is going on as part of ALADDIN and associated projects. The talks will be conference length (about 20 minutes) and aimed for a general theory audience. We plan to have enough time to include ample discussion.

Agenda and Abstracts: http://www.aladdin.cs.cmu.edu/workshops/lamps05/index.html
More Information: Susan Hrishenko, x8-7317, susan027 @ cs dot cmu dot edu

TENTATIVE SCHEDULE - Wednesday, May 11, 2005

Read the rest of this entry »

Summer Paper Proposals from:
Vineet Goyal, Viswanath Nagarajan, Mohit Singh, and John Turner
Tepper School of Business

Friday, May 13, 2005
2:00 - 3:30 pm
384 Posner Hall

Abstracts:

Read the rest of this entry »

Do you know that you can clone an object in PowerPoint by dragging it while holding down Ctrl?

This is very handy when you need to draw several instances of the same object. But when the number of instances is large, you will be better of using copy and paste.

Here is an “innocent” combinatorial problem, with the best known bounds being very simple (but nobody managed to improve them since 1978). Disclaimer: the problem is very catchy (I struggled with it for quite a while), so do not read any further if, for example, you are writing a PhD thesis

Maker and Breaker alternatively select 1 and q edges of K_n (the complete graph on n vertices) until all edges have been claimed. Maker wins if his graph has a triangle. What is the smallest q=q(n) such that Breaker has a winning strategy?

The best known strategy for Maker is to claim edges incident to some vertex x (and never miss a one-step win). If Breaker managed to block x completely, say after m rounds, then Breaker made n-1-m + {m\choose 2}\le m q(n) moves. This implies that q(n) is approximately at least \sqrt{2n}.

On the other hand, Breaker can win if q> 2\sqrt{n}: for each edge xy claimed by Maker, Breaker selects \sqrt{n} edges at x and \sqrt{n} edges at y. Thus Maker’s graph has maximum degree at most (n-1)/\sqrt{n}+1 and Breaker can always block all immediate threats.

Reference: V.Chvatal and P.Erdos, Biased positional games, Ann. Discrete Math. 2 (1978), 221-229.

I would bet on the \sqrt{2n} bound

Oleg

Here is my 3-minute tutorial of using \cite properly in LaTeX.

• Always precede it with a tilde (unbreakable space ~). This way you avoid starting a new line with a citation because of word wrapping.

  Bad:

  Garey and Johnson \cite[GJ1979]

  Good:

  Garey and Johnson~\cite[GJ1979]

• Use the optional argument (square brackets [ ]) to indicate specific part of a citation.

  Bad:

  Vazirani~\cite{Vazirani2001} page IX

  Good:

  Vazirani~\cite[p.~IX]{Vazirani2001}

• Combine multiple citations into one cite using comma.

  Bad:

  \cite{CJ} \cite{IPZ} \cite{H}

  Good:

  \cite{CJ, IPZ, H}

Hi, I am defending my thesis on Friday this week.
My thesis proposes analytical tools for performance analysis (or analysis of Markov chains).

Speaker: Taka Osogami
Place: NSH 3305
Time: Friday 1:30PM-

Title: Analysis of multi-server systems via dimensionality reduction of Markov chains

http://www-2.cs.cmu.edu/~osogami/thesis/

Even though I am a Windows user, I spend a lot of time in the command prompt. While many Unix users actually tweak their .login and related files, I’ve seen a lot of Windows users living with the default. This series proposes several easy fixes to make their life easier.

First thing first: the command prompt that all of us should be using on Windows NT or later is cmd.exe whereas command.com is there only for backward compatibility…

I recommend associating a hotkey to your command prompt. I use Ctrl-Alt-Z to mimic the Ctrl-Z feeling in Unix.

Many Windows users miss this feature. For each shortcut in your Start menu, you can associate a hotkey with it. Right click on Start->Programs->Accessories->Command Prompt. Click Properties.

Click on the text field of Shortcut key and press Ctrl-Alt-Z. Then click OK.

Now no matter where you are, pressing Ctrl-Alt-Z will get you to the command prompt.

P.S. There is an annoying “feature”. If you have opened a command prompt already, it will bring you there instead of opening a new one. I will tell you how to fix it later.

Speaker: Katrina Ligett
Place: NSH 1507
Time: Wednesday 12-1pm

Title:
Routing Without Regret

Abstract:

Read the rest of this entry »

Do you know that you can quickly zoom in PowerPoint by using the scroll wheel while holding down Ctrl?

P.S. In fact, this behavior seems quite consistent among many Windows applications, including non-Microsoft applications like FireFox. I suppose Office started the trend and now it gets into the human interface guideline?

Let’s go support our fantastic undergrads!

This Wednesday, May 4, the SCS Undergrad Research Thesis students will be presenting synopses of their theses as part of Meeting of the Minds, the Undergraduate Research Symposium to be held in the University Center. Events are scheduled throughout the day on Wednesday, beginning at 9:30am; the thesis students, their topics and talk-times are listed below. For the first time, all the SCS Senior Thesis talks are back to back in one room!

Read the rest of this entry »

Andrea Lodi, DEIS, University of Bologna

Friday, May 6, 2005
2:00 - 3:30 pm
153 Posner Hall

Optimizing over the First Chvatal Closure

Abstract:

Read the rest of this entry »