\documentclass[letterpaper,11pt]{article}

\usepackage[papersize={85mm, 55mm}, text={75mm, 45mm}]{geometry}
\pagestyle{empty}

% For automata drawings
\usepackage{tikz}
\usepackage{pgf}
\usetikzlibrary{arrows}

\begin{document}
\begin{figure}[h]
  \footnotesize
  \centering
  \begin{tikzpicture}[
    % type of arrow head
    >=stealth',
    % keep arrow head from touching the surface
    shorten >= 1pt,
    % automatic node positioning
    auto,
    % 
    node distance=2cm,
    % line thickness
    semithick,
    bend angle=10,
    graybox/.style = {draw=gray!20, fill=gray!20, rounded corners},
    line/.style = {->, draw=black, thick},
    box/.style = {circle, draw=blue!50, fill=blue!20, minimum size=4mm}
    ]

    \coordinate (S) at (-5cm, 0cm);

    \coordinate (S1) at (-3cm, 2cm);
    \coordinate (S2) at (-3cm, 1cm);
    \coordinate (S3) at (-3cm, 0cm);
    \coordinate (S4) at (-3cm, -2cm);

    \coordinate (M1) at (0cm, 1.5cm);
    \coordinate (M2) at (0cm,  .5cm);
    \coordinate (M3) at (0cm,-1.5cm);

    \coordinate (T) at (2cm, 0cm);

    \node (BBox) [graybox, minimum width=1cm, minimum height=2cm] at (-3cm, 1.5cm) {};
    \node [left] at (BBox.130) {$S_1$};

     % nodes
    \node (Sbox)  [box] at (S)  {s};
    \node (Sbox1) [box] at (S1) {$\ell_1$};
    \node (Sbox2) [box] at (S2) {$\ell_2$};
    \node (Sbox3) [box] at (S3) {$\ell_3$};
    \node (Sbox4) [box] at (S4) {$\ell_n$};
    
    \node (Mbox1) [box] at (M1) {$r_1$};
    \node (Mbox2) [box] at (M2) {$r_2$};
    \node (Mbox3) [box] at (M3) {$r_m$};
    
    \node (Tbox) [box] at (T) {t};
    
    \fill [black] (-3cm,  -.8cm) circle (1.2pt);
    \fill [black] (-3cm,   -1cm) circle (1.2pt);
    \fill [black] (-3cm, -1.2cm) circle (1.2pt);

    \fill [black] (0cm, -.3cm) circle (1.2pt);
    \fill [black] (0cm, -.5cm) circle (1.2pt);
    \fill [black] (0cm, -.7cm) circle (1.2pt);


    % edges
    \path[line] (Sbox) -- node [above] {1} (Sbox1);
    \path[line] (Sbox) -- node [above] {1} (Sbox2);
    \path[line] (Sbox) -- node [below] {1} (Sbox3);
    \path[line] (Sbox) -- node [below] {1} (Sbox4);

    \path[line] (Sbox1) -- node [above] {1} (Mbox1);
    \path[line] (Sbox2) -- node [above] {1} (Mbox1);

    \path[line] (Sbox3) -- node [above, pos=.7] {1} (Mbox2);

    \path[line] (Sbox1) -- node [below, pos=.3] {1} (Mbox3);

    \path[line] (Sbox4) -- node [below] {1} (Mbox2);
    \path[line] (Sbox4) -- node [below] {1} (Mbox3);

    \path[line] (Mbox1) -- node [above] {$d_1$} (Tbox);
    \path[line] (Mbox2) -- node [below] {$d_2$} (Tbox);
    \path[line] (Mbox3) -- node [below] {$d_m$} (Tbox);
   \end{tikzpicture}
 \end{figure}
\end{document}
Comments Off on Flow Network Example

\documentclass{article}

% For fancy drawing
\usepackage{tikz, subfigure}

\usepackage[papersize={140mm, 100mm}, text={130mm, 90mm}]{geometry}

% order: \order[st]{1}, \order{k}
\newcommand{\order}[2][th]{\ensuremath{{#2}^{\mathrm{#1}}}}

\begin{document}
\pagestyle{empty}
\begin {figure}[h]
  \centering
  \subfigure[staying inside the folding]{
    \begin{tikzpicture}
      [
      line/.style = {draw, thick},
      arrow/.style = {draw, semithick, -latex},
      dot/.style = {draw, fill=black},
      ]
      
      \coordinate (O) at (3cm, 0cm);
      \coordinate (J) at (1cm, 0cm);
      \coordinate (L) at (2cm, 0cm);
      \coordinate (K) at (4cm, 0cm);
      
      \coordinate (A) at (0cm, 0cm);
      \coordinate (B) at (5cm, 0cm);
      \node at (A) {};
      \node at (B) {};

      \path [arrow] ([yshift=2mm]L) -- node [above] {$\ell_{i+1}$} ([yshift=2mm]O);
      \path [line] (J) -- (K);
      
      \fill [dot] (J) circle (.3mm);
      \fill [dot] (L) circle (.3mm);
      \fill [dot] (K) circle (.3mm);
      
      \node [below] at (L) {$k'$};
      \node [below] at (K) {$j$};
      \node [below] at (J) {$0$};
      \node [below] at (O) {$k$};
   \end{tikzpicture}
  }
  \qquad\qquad
  \subfigure[stretching beyond the folding]{
    \begin{tikzpicture}
      [
      line/.style = {draw, thick},
      arrow/.style = {draw, semithick, -latex},
      dot/.style = {draw, fill=black},
      ]
      
      \coordinate (O) at (3cm, 0cm);
      \coordinate (J) at (0cm, 0cm);
      \coordinate (L) at (1cm, 0cm);
      \coordinate (K) at (2cm, 0cm);
      
      \coordinate (A) at (-1cm, 0cm);
      \coordinate (B) at (4cm, 0cm);
      \node at (A) {};
      \node at (B) {};

      \path [arrow] ([yshift=2mm]L) -- node [above] {$\ell_{i+1}$} ([yshift=2mm]O);
      \path [line] (J) -- (K);
      
      \fill [dot] (J) circle (.3mm);
      \fill [dot] (L) circle (.3mm);
      \fill [dot] (K) circle (.3mm);
      
      \node [below] at (L) {$k'$};
      \node [below] at (K) {$j'$};
      \node [below] at (O) {$j$};      
      \node [below] at (J) {0};
    \end{tikzpicture}
  }
 \caption{The $\order{(i+1)}$ segment folded to the right}
\end{figure}

\begin {figure}[h]
  \centering
  \subfigure[staying inside the folding]{
    \begin{tikzpicture}
      [
      line/.style = {draw, thick},
      arrow/.style = {draw, semithick, -latex},
      dot/.style = {draw, fill=gray!50},
      ]
      
      \coordinate (O) at (2cm, 0cm);
      \coordinate (J) at (1cm, 0cm);
      \coordinate (L) at (3cm, 0cm);
      \coordinate (K) at (4cm, 0cm);
      
      \coordinate (A) at (0cm, 0cm);
      \coordinate (B) at (5cm, 0cm);
      \node at (A) {};
      \node at (B) {};

      \path [arrow] ([yshift=2mm]L) -- node [above] {$\ell_{i+1}$} ([yshift=2mm]O);
      \path [line] (J) -- (K);
      
      \fill [dot] (J) circle (.3mm);
      \fill [dot] (L) circle (.3mm);
      \fill [dot] (K) circle (.3mm);
      
      \node [below] at (L) {$k'$};
      \node [below] at (K) {$j$};
      \node [below] at (J) {$0$};
      \node [below] at (O) {$k$};
    \end{tikzpicture}
  }
  \qquad\qquad
  \subfigure[stretching beyond the folding]{
    \begin{tikzpicture}
      [
      border/.style = {draw=gray!90, thick},
      line/.style = {draw, thick},
      arrow/.style = {draw, semithick, -latex},
      dot/.style = {draw, fill=gray!50},
      ]
      
      \coordinate (O) at (0cm, 0cm);
      \coordinate (J) at (1cm, 0cm);
      \coordinate (L) at (2cm, 0cm);
      \coordinate (K) at (3cm, 0cm);
      
      \path [arrow] ([yshift=2mm]L) -- node [above] {$\ell_{i+1}$} ([yshift=2mm]O);
      \path [line] (J) -- (K);
      
      \fill [dot] (J) circle (.3mm);
      \fill [dot] (L) circle (.3mm);
      \fill [dot] (K) circle (.3mm);
      
      \node [below] at (J) {$0$};
      \node [below] at (L) {$k'$};
      \node [below] at (K) {$j'$};
      \node [below] at (O) {$k'-\ell_{i+1}$};
      
      \path [border] (O) -- ([yshift=3mm]O);
    \end{tikzpicture}
  }
  \caption{The $\order{(i+1)}$ segment folded to the left}
\end{figure}
\end{document}
Comments Off on carpenter’s ruler

\documentclass{article}

\usepackage[papersize={85mm, 20mm}, text={75mm, 15mm}]{geometry}

\usepackage{pgf, tikz}
\usetikzlibrary{arrows,automata}

\begin{document}
\begin{figure}[h]
  \footnotesize
  \centering
  \begin{tikzpicture}[
    % type of arrow head
    >=stealth',
    % keep arrow head from touching the surface
    shorten >= 1pt,
    % automatic node positioning
    auto,
    % 
    node distance=1.5cm,
    % line thickness
    semithick,
    % text for the initial state arrow. I left it as blank
    initial text=]
    \tikzstyle{every state}=[draw=blue!50, thick, fill=blue!20,
    minimum size=4mm]
    
    \node[state] (v1) {$v_1$};
    \node[state] (v2) [right of=v1] {$v_2$};
    \node[state] (v3) [right of=v2] {$v_3$};
    \node[state] (v4) [right of=v3] {$v_4$};
    \node[state] (v5) [right of=v4] {$v_5$};
    
    \path[->] (v1) edge (v2);
    \path[->] (v3) edge (v4);
    \path[->] (v4) edge (v5);

    \path[->, bend right, bend angle = 5] (v2) edge (v5);
    \path[->, bend left, bend angle = 25] (v1) edge (v3);
  \end{tikzpicture}
\end{figure}
\end{document}
Comments Off on directed graph

pdf

\documentclass[12pt]{article}

\usepackage[papersize={6in, 9.1in}, text={5.5in, 8.8in}]{geometry}
\usepackage{amsmath}

\usepackage{mathspec}
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase}
\setmainfont[Mapping=tex-text]{Minion Pro}
%\setmainfont[Mapping=tex-text]{Hoefler Text}
%\setmainfont[Mapping=tex-text]{Garamond}
\setsansfont[Mapping=tex-text]{Candara}
%\setsansfont[Mapping=tex-text]{Myriad Pro}
%\setsansfont[Mapping=tex-text]{Comic Sans MS}
%\setmonofont{Courier}
\setmonofont{Monaco}

\usepackage{paralist}

\newcommand{\fpd}[2]{\ensuremath{\frac{\partial{#1}}{\partial{#2}}}}

\begin{document}
\thispagestyle{empty}
The Cauchy distribution is a symmetric distribution on
$(-\infty,\infty)$ with pdf
\begin{equation*}
  f_X(x;\theta,\gamma) =
  \frac1\pi \cdot \frac{\gamma}{(x-\theta)^2+\gamma^2}
\end{equation*}
In this paper, we only deal with the case $\theta=0$.

Consider two independent Gaussian random variables $X,Y\sim N(0,1)$.
We will prove that the ratio $X/Y$ is a Cauchy distribution by
\begin{inparaenum}[(1)]
\item defining the transformation $U=X/Y$ and $V=|Y|$,
\item finding the joint pdf $F_{U,V}(u,v)$, and
\item integrating out $V$ to obtain the marginal pdf of $U$.
\end{inparaenum}

Unfortunately, the mapping $U=X/Y$ and $V=|Y|$ is not one-to-one:
the two points $(x,y)$ and $(-x,-y)$ map to the same $(u,v)$
We need to partition $(X,Y)$ into $A_0,A_1,A_2$ such that the mapping
from $A_i$ to $(U,V)$ is one-to-one.
\begin{enumerate}
  \item $A_0=\{(X,Y):Y=0\}$: This exceptional case does not happen
    because $\Pr[Y=0]=0$ when $Y\sim N(0,1)$.
  \item $A_1=\{(X,Y):Y>0\}$: The mapping $U=X/Y$, $V=|Y|$ is
    one-to-one, and the inverse mappings are $h_{11}(u,v)=uv$,
    $h_{21}=v$.
  \item $A_2=\{(X,Y):Y<0\}$: The mapping $U=X/Y$, $V=|Y|$ is
    one-to-one, and the inverse mappings are $h_{12}(u,v)=-uv$,
    $h_{22}=-v$.
\end{enumerate}
\begin{equation*}
\begin{array}{lllll}
  J_1 & =
  \begin{vmatrix}
    \fpd{h_{11}}{u} & \fpd{h_{11}}{v} \\
    \fpd{h_{21}}{u} & \fpd{h_{21}}{v}
  \end{vmatrix}
  & = 
  \begin{vmatrix}
    \fpd{uv}{u} & \fpd{uv}{v} \\
    \fpd{v}{u} & \fpd{v}{v}
  \end{vmatrix}
  &=
  \begin{vmatrix}
    v & u \\ 0 & 1
  \end{vmatrix}
  &= v \\
  J_2 &= 
  \begin{vmatrix}
    \fpd{h_{12}}{u} & \fpd{h_{12}}{v} \\
    \fpd{h_{22}}{u} & \fpd{h_{22}}{v}
  \end{vmatrix}
  &= 
  \begin{vmatrix}
    \fpd{(-uv)}{u} & \fpd{(-uv)}{v} \\
    \fpd{(-v)}{u} & \fpd{(-v)}{v}
  \end{vmatrix}
  &=
  \begin{vmatrix}
    -v & -u \\ 0 & -1
  \end{vmatrix}
  &= v
\end{array}
\end{equation*}
%%%
\begin{equation*}
  f_{X,Y}(x,y) =
  \frac{1}{\sqrt{2\pi}}\exp(-x^2/2)
  \frac{1}{\sqrt{2\pi}}\exp(-y^2/2) =
  \frac{1}{2\pi}\exp\left(-\frac{x^2+y^2}{2}\right)
\end{equation*}
%%%
\begin{align*}
  f_{UV}(u,v) &= f_{XY}(h_{11}(u,v),h_{21}(u,v))|J_1|
  + f_{XY}(h_{12}(u,v),h_{22}(u,v))|J_2| \\
  &= \frac{1}{2\pi}\exp\left(-\frac{(uv)^2 + v^2}{2}\right)|v| +
  \frac{1}{2\pi}\exp\left(-\frac{(-uv)^2 + (-v)^2}{2}\right)|v| \\
  &= \frac{v}{\pi}\exp\left(-\frac{v^2(u^2+1)}{2}\right),
  \qquad -\infty < u < \infty, \quad0<v<\infty \\
\end{align*}
%%%
\begin{alignat*}{2}
  f_U(u) &=
  \int_0^\infty \frac{v}{\pi}\exp\left(-\frac{v^2(u^2+1)}{2}\right) dv
  & \text{integrating out $V$}\\
  &= \int_0^\infty \frac{1}{2\pi}\exp\left(-\frac{u^2+1}{2}z\right) dz
  & \qquad\text{Let $z=v^2$ and $dz=2vdv$} \\
  &= \frac{1}{2\pi}\cdot \frac{2}{u^2+1}
  & \int_0^\infty \exp(-\alpha z) dz = \frac1\alpha \\
  &= \frac{1}{\pi}\cdot\frac{1}{u^2+1},\qquad -\infty< u<\infty
\end{alignat*}
\end{document}


cauchy

\documentclass[10pt]{article}
\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[papersize={140mm, 210mm}, text={120mm, 200mm}]{geometry}

% For fancy fonts
\usepackage[T1]{fontenc}
\usepackage{ccfonts,eulervm}

\usepackage{tikz}

\newcommand{\fpd}[2]{\ensuremath{\frac{\partial{#1}}{\partial{#2}}}}

\thispagestyle{empty}

\begin{document}
The ratio of two Gaussian random variables $X,Y\sim N(0,1)$ is a
Cauchy distribution.
Let $U=X/Y$ and $V=|Y|$. If $Y=0$, $U$ and $V$ can be any value
because $\Pr(Y=0)=0$.
If we restrict consideration to either positive or negative value of
$Y$, then the transform from $\mathcal{A}=(X,Y)$ to
$\mathcal{B}=(U,V)$ is one-to-one.
\begin{equation*}
  A_1 = \{(x,y): y > 0 \},\qquad
  A_2 = \{(x,y): y < 0 \},\qquad
  A_3 = \{(x,y): y = 0 \}
\end{equation*}
These three partition $\mathcal{A}=\mathbb{R}^2$ and
$\Pr[(X,Y)\in A_0]=\Pr[Y=0]=0$.
\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    [line/.style ={draw, thick, -latex, shorten >=2pt},]
    \def\myradius{1.5cm}
    % left circle
    \shadedraw[left color=blue!10, right color=blue!60,
    draw=blue!50!black]
    (0, 0) -- (\myradius, 0mm) arc (0:150:\myradius) -- cycle; 
    \shadedraw[left color=red!10, right color=red!60,
    draw=red!50!black]
    (0, 0) -- (\myradius, 0mm) arc (0:-150:\myradius) -- cycle;
    \draw (0,0) circle (\myradius);

    \node at (5mm, 8mm) {$A_1$};
    \node at (5mm, -8mm) {$A_2$};
    \node at (-9mm, 0mm) {$A_0$};

    \node at (0cm, \myradius+5mm) {$\mathcal{A}=\mathbb{R}^2=(X,Y)$};

    % right circle
    \shade[left color=black!10, right color=black!40,
    draw=black!50!black] (6cm, 0) circle (\myradius);
    \node at (\myradius*4, \myradius+5mm)
    {$\mathcal{B}=\{(U,V):V\geq 0\}$};

    % arrows
    \path (\myradius*4-3mm, 8mm) edge [line, bend angle=10, bend right]
    node [above, midway] {$h_{11},h_{21}$} (8mm, 8mm);
    \path (8mm, 6mm) edge [line, bend angle=10, bend right]
    (\myradius*4-3mm, 6mm);
    
    \path (\myradius*4-3mm, -8mm) edge [line, bend angle=10, bend left]
    node [below, midway] {$h_{12},h_{22}$} (8mm, -8mm);
    \path (8mm, -6mm) edge [line, bend angle=10, bend left]
    (\myradius*4-3mm, -6mm);

  \end{tikzpicture}
\end{figure}

\begin{alignat*}{3}
  \mathcal{B} \to \mathcal{A}_1:&
  x=h_{11}(u,v)=uv, &\quad&y=h_{21}(u,v)=v \\
  \mathcal{B} \to \mathcal{A}_2:&
  x=h_{12}(u,v)=-uv, &\quad&y=h_{22}(u,v)=-v
\end{alignat*}

\begin{equation*}
  J_1 =
  \left|
  \begin{array}{cc}
    \fpd{uv}{u} & \fpd{uv}{v} \\
    \fpd{v}{u} & \fpd{v}{v}
  \end{array}
  \right|
  =
  \begin{vmatrix}
    v & u \\ 0 & 1 \\
  \end{vmatrix}
  = v,\quad
  J_2 =
  \left|
  \begin{array}{cc}
    \fpd{(-uv)}{u} & \fpd{(-uv)}{v} \\
    \fpd{(-v)}{u} & \fpd{(-v)}{v}
  \end{array}
  \right|
  =
  \begin{vmatrix}
    -v & -u \\ 0 & -1 \\
  \end{vmatrix}
  = v
\end{equation*}

\begin{equation*}
  f_{XY}(x,y) = \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{x^2}{2}\right)
  \cdot
  \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right) =
  \frac{1}{2\pi}\exp\left(-\frac{x^2+y^2}{2}\right)
\end{equation*}

\begin{align*}
  f_{UV}(u,v) &= \sum_{i=0}^2 f_{XY}(h_{1i}(u,v),h_{2i}(u,v))|J_i| \\
  &= \frac{1}{2\pi}\exp\left(-\frac{(uv)^2 + v^2}{2}\right)|v| +
  \frac{1}{2\pi}\exp\left(-\frac{(-uv)^2 + (-v)^2}{2}\right)|v| \\
  &= \frac{v}{\pi}\exp\left(-\frac{v^2(u^2+1)}{2}\right)
\end{align*}

\begin{alignat*}{2}
  f_U(u) &= \int_0^\infty
  \frac{v}{\pi}\exp\left(-\frac{v^2(u^2+1)}{2}\right) dv 
  &\qquad(\text{change of variable: $z=v^2$}) \\
  &= \int_0^\infty \frac{1}{2\pi}
  \exp\left(-\frac{u^2+1}{2}z\right) dz 
  & \left(\int_0^\infty\exp(-\alpha z) dz = 1/\alpha\right) \\ 
  &=\frac{1}{\pi}\cdot\frac{1}{u^2+1}
\end{alignat*}
\end{document}
Comments Off on Cauchy distribution: ratio of two gaussian random variables

\documentclass[12pt,table]{beamer}

\usepackage{hyperref}

% For fancy math
\usepackage{amsmath}

% color theme
\usetheme{psu}
\usecolortheme[RGB={0,38,93}]{structure}
\def\softness{0.4}
\definecolor{softblue}{rgb}{\softness,\softness,1}
\renewcommand{\emph}[1]{\textit{\textcolor{softblue}{#1}}}
\definecolor{darkgreen}{rgb}{0.2, 0.7, 0.5}
\newcommand{\paper}[1]{\textit{\textcolor{darkgreen}{#1}}}
% For fancy footnotes
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% For fancy fonts
\usepackage{mathspec}
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase}
\setmainfont[Mapping=tex-text]{Hoefler Text}
\setsansfont[Mapping=tex-text]{Candara}
%\setsansfont[Mapping=tex-text]{Myriad Pro}
%\setsansfont[Mapping=tex-text]{Comic Sans MS}
%\setmonofont{Courier}
\setmonofont{Monaco}

% For fancy picture
\usepackage{tikz}

%\usepackage{preamble}
\usepackage{xspace}
\newcommand{\LLL}{Lov\'asz Local Lemma\xspace}

\makeatletter
\newenvironment{customitem}[2]{
  \ifnum\@itemdepth >2\relax\@toodeep\else
  \advance\@itemdepth\@ne%
  \beamer@computepref\@itemdepth%
  \usebeamerfont{itemize/enumerate \beameritemnestingprefix body}%
  \usebeamercolor[fg]{itemize/enumerate \beameritemnestingprefix body}%
  \usebeamertemplate{itemize/enumerate \beameritemnestingprefix body begin}%
  \begin{list}
    {
      \usebeamertemplate{itemize \beameritemnestingprefix item}
    }
    { \leftmargin=#1 \itemindent=#2
      \def\makelabel##1{%
        {%  
          \hss\llap{{%
              \usebeamerfont*{itemize \beameritemnestingprefix item}%
              \usebeamercolor[fg]{itemize \beameritemnestingprefix item}##1}}%
        }%  
      }%  
    }
    \fi
  }
  {
  \end{list}
  \usebeamertemplate{itemize/enumerate \beameritemnestingprefix body end}%
}
\makeatother

\begin{document}

\title{A Constructive Proof of the Lov\'asz Local Lemma}
\subtitle{Robin Moser, STOC 2009}
\author{Youngtae Youn}
\institute{CSE Dept. Penn State}
\date{September 28, 2009}

%%%
\begin{frame}
  \frametitle{\LLL: Lov\'asz and Erd\H{o}s in 1975}
  \begin{itemize}
  \item What if bad events are \alert{not} independent?
    \begin{customitem}{1.3em}{0em}
    \item Bad events are \emph{mostly} independent from one
      another.
    \item Bad event are \alert{not} individually too likely to occur.
    \end{customitem}
    Still, $\Pr[\text{none of the bad events will occur}] > 0$.
  \item Lov\'asz Local Lemma
  \end{itemize}
\end{frame}

\end{document}
Comments Off on Beamer Nested Itemized List Indentation

LaTeX Source

\documentclass[12pt]{article}
\usepackage[papersize={120mm, 25mm}, text={100mm, 20mm}]{geometry}
\usepackage{concrete}
\usepackage{color}
\definecolor{MyGray}{rgb}{0.96,0.97,0.98}

\makeatletter\newenvironment{mybox}{%
   \begin{lrbox}{\@tempboxa}\begin{minipage}{0.97\textwidth}%
   \refstepcounter{equation}(\arabic{equation})}{\end{minipage}\end{lrbox}%
   \noindent\colorbox{MyGray}{\usebox{\@tempboxa}}}
\makeatother

\usepackage{amsmath}
% Matrix norm
\newcommand{\norm}[1]{\ensuremath{\lVert{#1}\rVert }}
% bold face letters for matrix and vector
\newcommand{\Ebf}{\ensuremath{\mathbf{E}}}

\begin{document}
\pagestyle{empty}
\begin{mybox}
$\displaystyle \quad |\sigma_k - \beta_k| \leq \norm{\Ebf}_2\quad$
for $1\leq k\leq n$.
\label{eq:1}
\end{mybox}

This can be proved by the following fact.
\begin{equation}
  \label{eq:2}
  x^2 + y^2 = z^2
\end{equation}
\end{document}
Comments Off on LaTeX Environment: Kleinberg-Tardos style

This document is generated as follows.

[ytyoun@Ordnung:~/doQment/]# xelatex test
[ytyoun@Ordnung:~/doQment/]# makeindex test
[ytyoun@Ordnung:~/doQment/]# makeindex test.nlo -s nomencl.ist -o test.nls
[ytyoun@Ordnung:~/doQment/]# xelatex test
\documentclass[12pt]{article}
 
\usepackage{hyperref}
\usepackage[papersize={120mm, 160mm}, text={95mm, 130mm}]{geometry}
 
% fancy fonts
\usepackage{concrete}
 
% for fancy section font and color
\usepackage{color}
\definecolor{section_color}{rgb}{0.35,0.0,0}
\usepackage{sectsty}
\allsectionsfont{\color{section_color}\sffamily\selectfont}
 
% fancy math
\usepackage{amsmath,amssymb}
 
% mathematical shorthand
\newcommand{\Abf}{\ensuremath{\mathbf{A}}}
\newcommand{\ubf}{\ensuremath{\mathbf{u}}}
\newcommand{\vbf}{\ensuremath{\mathbf{v}}}
\newcommand{\xbf}{\ensuremath{\mathbf{x}}}
\newcommand{\Vcal}{\ensuremath{\mathcal{V}}}
\newcommand{\Rbb}{\ensuremath{\mathbb{R}}}
 
\newcommand{\norm}[1]{\ensuremath{\lVert{#1}\rVert}}
\newcommand{\proj}[2]{\ensuremath{\pi_{#1}(#2)}}
\newcommand{\trans}[1]{\ensuremath{{#1}^\top}}
\newcommand{\bkt}[1]{\ensuremath{\langle{#1}\rangle}}
 
% math operators
\DeclareMathOperator{\trace}{trace}
 
% index generation
\usepackage{makeidx}
\makeindex
 
% 'list of notations' generation
\usepackage[refpage]{nomencl}  % refer to the page where notation appears
\renewcommand{\nomname}{List of Notations}
\renewcommand*{\pagedeclaration}[1]{\unskip\dotfill\hyperpage{#1}}
\makenomenclature
 
\begin{document}
\paragraph{Matrix Norm}\index{Matrix Norm}
The squared \index{Matrix Norm!Frebenius norm}Frobenius norm of a matrix
$\Abf_{m\times n}$ is defined as
\nomenclature{$\norm{\Abf}_F$}{Frobenius norm of $\Abf$}
\begin{equation*}
  \norm{\Abf}_F^2 = \sum_{i=1}^m\sum_{j=1}^na_{ij}^2 =
  \trace(\trans\Abf\Abf).
\end{equation*}
 
The 2-norm\index{Matrix Norm!2-norm} of a matrix $\Abf_{m\times n}$ is
defined as\nomenclature{$\norm{\Abf}_2$}{2-norm of $\Abf$}
\begin{equation*}
\norm{\Abf}_2 = \max_{\norm{\xbf}_2=1}\norm{\Abf\xbf}_2\quad
\text{for $\xbf\in\Rbb^{n\times 1}$}
\end{equation*}
 
For a subspace $\Vcal\subseteq \Rbb^n$ and a vector $\ubf\in\Rbb^n$,
let $\proj{\Vcal}{\ubf}$
\nomenclature{$\proj{\Vcal}{\ubf}$}{Projection of $\ubf$ onto subspace $\Vcal$}
\index{Projection}
be the projection of $\ubf$ onto $\Vcal$.
If $\{\vbf_1,...,\vbf_k\}$ is a basis for $\Vcal$, then
\begin{equation*}
  \proj{\Vcal}{\ubf} = \sum_{i=1}^k \bkt{\vbf_i,\ubf}\vbf_i
\end{equation*}
 
\printnomenclature
\printindex
 
\end{document}
Comments Off on LaTeX Example

Candara

Myriad

Comic Sans MS

Document Source Code

\documentclass[12pt,table]{beamer}
 
\usepackage{hyperref}
 
% For fancy math
\usepackage{amsmath}
 
% color theme
\usetheme{psu}
\usecolortheme[RGB={0,38,93}]{structure}
\def\softness{0.4}
\definecolor{softblue}{rgb}{\softness,\softness,1}
\renewcommand{\emph}[1]{\textit{\textcolor{softblue}{#1}}}
\definecolor{darkgreen}{rgb}{0.2, 0.7, 0.5}
\newcommand{\paper}[1]{\textit{\textcolor{darkgreen}{#1}}}
% For fancy footnotes
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
 
% For fancy fonts
\usepackage{mathspec}
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase} 
\setmainfont[Mapping=tex-text]{Hoefler Text}
%\setsansfont[Mapping=tex-text]{Candara}
\setsansfont[Mapping=tex-text]{Myriad Pro}
%\setsansfont[Mapping=tex-text]{Comic Sans MS}
%\setmonofont{Courier}
\setmonofont{Monaco}
 
% For fancy picture
\usepackage{tikz}
 
%\usepackage{preamble}
\usepackage{xspace}
\newcommand{\LLL}{Lov\'asz Local Lemma\xspace}
\begin{document}
 
\title{A Constructive Proof of the Lov\'asz Local Lemma}
\subtitle{Robin Moser, STOC 2009}
\author{Youngtae Youn}
\institute{CSE Dept. Penn State}
\date{September 28, 2009}
 
%%%
\begin{frame}
  \frametitle{\LLL: Lov\'asz and Erd\H{o}s in 1975}
  \begin{itemize}
  \item What if bad events are \alert{not} independent? 
    \begin{itemize}
    \item Bad events are \emph{mostly} independent from one
      another.
    \item Bad event are \alert{not} individually too likely to occur.
    \end{itemize}
    Still, $\Pr[\text{none of the bad events will occur}] > 0$.
  \end{itemize}
 
  \begin{block}{\LLL (Symmetric Case)}
    \begin{enumerate}
    \item $\Pr[bad_i] \leq \emph{p}$ for all $1 \leq i \leq n$.     
    \item Each $bad_i$ depends on other \emph{$d$} bad events.
    \item $e\cdot p\cdot (d+1) \leq 1$ where $\emph{e}=2.7182\cdots$
    \end{enumerate}
    \vspace{-4mm}
    \begin{center}
      Then, $\Pr[\text{none of the bad events will occur}] > 0$.
    \end{center}
  \end{block}
 
  \begin{itemize}
  \item dictionary definition of \emph{local}: affecting or limited to
    part of a whole.
  \item The bound in (3) is \alert{tight}.    
  \item We will prove for the \emph{loose} bound $4pd\leq 1$.
  \end{itemize}
\end{frame}
 
\end{document}

How to convert PDF into PNG

convert -density 600x600 -resize 800x600 -quality 90 myriad.pdf myriad.png
  • -density 600x600 treats the pdf as 600×600 dpi resolution
  • -resize 800x600 gives the dimensions in pixels of the resulting png file
  • -quality 90 uses the highest compression level for png (9) and no filtering (0)
Comments Off on XeLaTeX: font comparison

\documentclass[12pt]{article}
\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[papersize={100mm, 130mm}, text={90mm, 120mm}]{geometry}
 
% order: \order[st]{1}, \order{k}
\newcommand{\order}[2][th]{\ensuremath{{#2}^{\mathrm{#1}}}}
 
\newcommand{\Abf}{\ensuremath{\mathbf{A}}}
\newcommand{\Bbf}{\ensuremath{\mathbf{B}}}
\newcommand{\fpd}[2]{\ensuremath{\frac{\partial{#1}}{\partial{#2}}}}
 
\begin{document}
We prove the product rule of matrix derivative.
\begin{equation*}
\fpd{}{t}\Abf\Bbf = \fpd{\Abf}{t}\Bbf + \Abf\fpd{\Bbf}{t}
\end{equation*}
Let $[\boldsymbol{*}]_{ij}$ be the element of $\boldsymbol{*}$ in the
$\order{i}$ row and $\order{j}$ column. Then it's enough to prove
\begin{equation*}
\fpd{}{t}\left[\Abf\Bbf\right]_{ij} = 
\left[\fpd{\Abf}{t}\Bbf + \Abf\fpd{\Bbf}{t}\right]_{ij.}
\end{equation*}
Note that $[\Abf\Bbf]_{ij=}=\sum_ka_{ij}b_{kj}$.
 
\begin{align*}
  \fpd{}{t}[\Abf\Bbf]_{ij} &= \fpd{}{t}\sum_ka_{ik}b_{ij} \\
  &= \sum_k\left(
  \fpd{a_{ik}}{t}b_{kj} + a_{ik}\fpd{b_{kj}}{t}
  \right) \\
  &= \sum_k\left(\fpd{a_{ik}}{t}b_{kj}\right) +
  \sum_k\left(a_{ik}\fpd{b_{kj}}{t}\right) \\
  &= \left[\fpd{\Abf}{t}\Bbf\right]_{ij} + 
  \left[\Abf\fpd{\Bbf}{t}\right]_{ij} \\
  &= \left[ \fpd{\Abf}{t}\Bbf + \Abf\fpd{\Bbf}{t} \right]_{ij}
\end{align*}
\end{document}
Comments Off on matrix calculus: product rule of matrix derivative

doc.tex

\documentclass{article}
\usepackage[papersize={200mm, 60mm}, text={190mm, 55mm}]{geometry}
\usepackage{subfigure, tikz}

\begin{document}
\begin{figure}[H]
 \centering
 \subfigure[Original Graph]{\input{graph.tex}}
 \quad
 \subfigure[Independent Set]{\input{ind_set.tex}}
 \quad
 \subfigure[Vertex Cover]{\input{vc.tex}}
 \quad
 \subfigure[Clique]{\input{clique.tex}}
 \caption{Relations among Independent Set, Vertex Cover, and Clique}
\end{figure}

\end{document}

graph.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

ind_set.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=blue!80]  (O) circle (4pt);
  \shade[ball color=blue!80]  (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=blue!80]  (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=blue!80]  (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

vc.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=red ] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=red ] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=red ] (F) circle (4pt);
\end{tikzpicture}

clique.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (O);
  \path[line] (A) -- (C);
  \path[line] (A) -- (D);
  \path[line] (A) -- (E);
  \path[line] (B) -- (E);
  \path[line] (B) -- (F);
  \path[line] (C) -- (A);
  \path[line] (C) -- (E);
  \path[line] (C) -- (F);
  \path[line] (C) -- (O);
  \path[line] (D) -- (O);
  \path[line] (E) -- (O);

  % nodes
  \shade[ball color=green] (O) circle (4pt);
  \shade[ball color=green] (A) circle (4pt);
  \shade[ball color=gray]  (B) circle (4pt);
  \shade[ball color=green] (C) circle (4pt);
  \shade[ball color=gray]  (D) circle (4pt);
  \shade[ball color=green] (E) circle (4pt);
  \shade[ball color=gray]  (F) circle (4pt);
\end{tikzpicture}
Comments Off on Independent Set, Vertex Cover, and Clique