\documentclass[a4,portrait]{seminar}

\usepackage[dvips]{pstcol}
\usepackage{semcolor}
\usepackage{fancybox}
\input{seminar.bug}
%\input{seminar.bg2}
\usepackage{fancyhdr}
\usepackage{graphicx}
%\input{epsf.sty}
%\usepackage{texdraw}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\onlyslides{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{M_Beige}         {rgb}{0.96 , 0.96 , 0.86}
\newcommand{\CBei}[1]{\textcolor{M_Beige}{#1}}
\definecolor{M_Brown}         {rgb}{0.65 , 0.16 , 0.16}
\newcommand{\CBro}[1]{\textcolor{M_Brown}{#1}}
\definecolor{M_Gold}          {rgb}{1.00 , 0.84 , 0.00}
\newcommand{\CGol}[1]{\textcolor{M_Gold}{#1}}
\definecolor{M_LemonChiffon}  {rgb}{1.00 , 0.98 , 0.80}
\newcommand{\CLem}[1]{\textcolor{M_LemonChiffon}{#1}}
\definecolor{M_Orange}        {rgb}{1.00 , 0.60 , 0.00}
\newcommand{\COra}[1]{\textcolor{M_Orange}{#1}}
\definecolor{M_Pink}          {rgb}{1.00 , 0.75 , 0.80}
\newcommand{\CPin}[1]{\textcolor{M_Pink}{#1}}
\definecolor{M_Violet}          {rgb}{0.93 , 0.51 , 0.93}
\newcommand{\CVio}[1]{\textcolor{M_Violet}{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Cbla}[1]{\textcolor{black}{#1}}
\newcommand{\Cblu}[1]{\textcolor{blue}{#1}}
\newcommand{\Ccya}[1]{\textcolor{cyan}{#1}}
\newcommand{\Cgre}[1]{\textcolor{green}{#1}}
\newcommand{\Cred}[1]{\textcolor{red}{#1}}
\newcommand{\Cyel}[1]{\textcolor{yellow}{#1}}
\newcommand{\Cwhi}[1]{\textcolor{white}{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\mysemtitle}{2D SG Partition Functions}
\newcommand{\myname}{Enzo Marinari}
\newcommand{\myaffiliation}{Roma {\em La Sapienza}, Italy}
\newcommand{\mysemplace}{SPDSA, Hayama, Japan}
\newcommand{\mysemdate}{July 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\fancyhf{}
\renewcommand{\headrulewidth}{0.2mm}
\renewcommand{\footrulewidth}{0.2mm}
\fancyhead[C]{\tiny\textbf{\mysemtitle}}
\fancyfoot[L]{\tiny\Cblu{\mysemdate}}
\fancyfoot[C]{\tiny\Cblu{\mysemplace}}
\fancyfoot[R]{\tiny \Cblu{Page} \theslide}
\renewcommand{\slidetopmargin}{1.5cm}
\renewcommand{\slidebottommargin}{3.0cm}
\renewcommand{\headwidth}{\textwidth}
\autoslidemarginstrue

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\SlideColors}[3]{%
% #1 frame line color
% #2 foreground color
% #3 background color
\slideframe[\psset{linecolor=#1,fillcolor=#3,fillstyle=solid}]{scplain}
\color{#2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\headL}[1]{%
  \begin{center}
    \Large\bf
    \shadowbox{#1}%
  \end{center}
  \vspace{1ex minus 1ex}}

\newcommand{\headl}[1]{%
  \begin{center}
    \large\bf
    \shadowbox{#1}%
  \end{center}
  \vspace{1ex minus 1ex}}

\newcommand{\headn}[1]{%
  \begin{center}
    \normalsize\bf
    \shadowbox{#1}%
  \end{center}
  \vspace{1ex minus 1ex}}

\newcommand{\heads}[1]{%
  \begin{center}
    \small\bf
    \shadowbox{#1}%
  \end{center}
  \vspace{1ex minus 1ex}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\SlideColors{blue}{blue}{white}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\pagestyle{fancy}
%\setcounter{slide}{-1}
\setcounter{slide}{0}

% slide 1: Title
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}

\headL{\Cred{\mysemtitle}}

\headn{\myname}

\heads{(\myaffiliation)}
\vfill

\footnotesize
\begin{center}
{\scriptsize
Work in collaboration with \Cgre{A. Galluccio, J. Lukic, O. C. Martin and
G. Rinaldi} ({\tt cond-mat 0309238}, in print on PRL).  }
{\scriptsize
Compute \Cgre{(many)} \Cbla{exact partition functions} of
\Cgre{(large)}  \Cbla{2D Ising SG, $J=\pm 1$ with PBC}.
\Cgre{Regge and Zecchina} \Cbla{and} 
\CVio{\Cgre {Galluccio, L\"obl and Vondr\'ak}: Pfaffians, modular
arithmetics, Chinese remainder theorem.} Results:
}
\begin{itemize}

\item \Cbla{Solve dispute}. Physical scaling as $\beta\longrightarrow\infty$
\Cred{$c_V\sim \beta^2 e^{-2\beta}$} (anomalous, see $1D$ Ising).

\item \Cred{$\xi\sim e^{\beta}$}, and \COra{hyperscaling works}.

\item \COra{Ground state properties} (\Cred{$\theta^E=\theta_{DW}=0$} etc...).

\item \Cbla{Number of excitations} (possible mechanism for anomalous scaling).

\item \Cbla{MKA} anomalous scaling (to be published).

\end{itemize}

\end{center}

\vfill 

\headn{\Cgre{\mysemplace, \mysemdate}}

\end{slide*}



% slide 2: Summary
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\Cgre{\Large \underline{Summary}}

\begin{itemize}

\item
\Cbla{
Spin glasses, $2D$ Ising spin glasses. The quenched physics.
}

\item
\Cbla{
$T=0$ and low $T$ physics. Choice of couplings and
  ``universality''. 
}

\item
\Cbla{
Monte Carlo versus ground states computations. Computations of
  $Z_{\beta}$. 
}

\item
\Cbla{
The dispute: Swendsen and Wang with (optimized) Monte Carlo
  versus Kardar-Saul with exact transfer matrix.
}

\item
\Cbla{
The Galluccio-L\"obl-Vondr\'ak algorithm.
}

\item
\Cbla{
Our findings. The anomalous scenario.
}

\end{itemize}
\end{center}
\end{slide*}



% slide 3: Spin Glasses
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\small

\begin{center}

\Cbla{SG: frustration + disorder (complexity)}

Quenched averages
\Cgre{$$H=-\sum_{{\tt nn}\ i,j} J_{ij}\sigma_i\sigma_j$$}
couplings \Cred{$J_{ij}$} are \CVio{random quenched}.

Huge interest:
\begin{enumerate}
\item \CVio{Parisi solution} of mean field SK theory.
\item \CVio{paradigmatic} role (boring as materials, as such).
\end{enumerate}

\COra{Open debate on behavior in finite $D$.}

\Cbla{``For sure''}: \Cred{$D_c^L\ge 2$}, no transition in $2D$ for $T>0$.

\COra{As $T\longrightarrow 0$}: \Cbla{scaling theory.} Coarse graining and
scaling Ansatz.
\Cred{$$\tilde{J}(l)\sim l^\theta$$}
effective coupling among (block) spins at large distance.

\CVio{$2D$}: \Cred{$\theta<0$} (and/or zero, see later). Coupling
becomes \CVio{weaker} at large scale, and the ordered state is unstable and
breaks down.

\end{center}
\end{slide*}

% slide 4: mainly Amoruso et al.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}

\footnotesize

\begin{center}

\Cbla{Typical choices} for the probability distribution of quenched
couplings: \Cgre{$P(J)\sim \exp(-J^2/2)$} or \CVio{$J=\pm 1$} with uniform
probabilities, or many other possibilities (but equivalent, see
later). 

In $2D$ this can play (and does play) a role in deciding the
\CVio{``critical behavior''} as \CVio{$T\longrightarrow 0$}
(see \Cgre{\scriptsize C. Amoruso, EM, O. Martin and A. Pagnani, PRL
  {\bf 91} (2003) 087201}).

Starting point is
\Cgre{$$ \delta E \equiv E_{GS}^{(P)} - E_{GS}^{(AP)}$$}
and as $L\longrightarrow\infty$
\Cred{$$\overline{\left(\delta E - \overline{\delta E}\right)^2}\sim
  L^{2\theta}$$} 
While for Gaussian $J$ one has \Cbla{$\theta=-0.28$} for binary couplings one
finds clearly (\Cgre{\scriptsize Hartmann and Young}) \Cred{$\theta=0$}.

We find that all $P(J)$ which can only produce \Cgre{quantized energies} give
\Cgre{$\theta=0$}, while all distribution that can generate \COra{continuous
energies without a gap give $\theta\simeq -0.28$} (even if for example
are built on only two coupling values, but with an irrational ratio). 

\begin{enumerate}

\item $D\le D_c^L\Longrightarrow$ \Cgre{small $\delta E$ values are relevant}
  for the large distance behavior of the system $\Longrightarrow$ gap
  in coupling distribution can play a role.

\item $\theta_{(D)}=0$ does only mean \Cred{$D\le D_c^L$}, \Cbla{not 
$D=D_C^L$}. 

\end{enumerate}

\end{center}
\end{slide*}

% slide 5: MC versus GS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

\Cbla{Monte Carlo versus Ground State computations.}

\begin{enumerate}

\item \Cred{MC for Spin Glasses is \underline{very} difficult.}

\Cgre{``Naive'' MC is basically of no use.}
\Cbla{High free energy barriers make impossible exploring the full
  phase space.}

Optimized Monte Carlo (multicanonical, replica MC, parallel tempering)
helps. 

Still: it is difficult to go at low T. You are never sure you
thermalized... 

\item \Cred{Computing GS you study directly T=0 physics.}
No problems with thermalization.

Main problem: what do you learn, say, about finite $T$ physics? (it
seems it works...).

\item \Cred{A third approach: compute directly the full partition
  function.}  ``Best of both worlds''\\
\Cgre{(but: depending on the algorithm only reach some observables)}
\CVio{(but: can only do it in some models, see later...)}.

\end{enumerate}

\end{center}
\end{slide*}

% slide 6: The dispute: Wang and Swendsen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\scriptsize
\Cbla{\underline{The dispute}}

\Cgre{\scriptsize Saul and Swendsen (PRL {\bf 38} (1988) 4840)} after
a very accurate optimized MC simulation claimed to detect an anomalous
scaling behavior.

\Cbla{2D Ising Spin Glass, $J=\pm 1$, Periodic Boundary
Conditions}. \CVio{V=$128^2$} 
\Cred{$$c_V\sim\beta^2 e^{-A\beta}\ \ , \ \ \ \  A=2\ .$$}
Would expect $A=4$, since minimal excitation costs $4J$.

\COra{Periodic Boundary Conditions 1D Ising model analogy}. Minimal
excitation is $4J$, since \Cbla{$\Downarrow \Cred{\Uparrow} \Downarrow$}

\includegraphics[width=0.5\textwidth,angle=0]{k-ak.eps}

Still, an easy computation gives $c_V\sim\beta^2 e^{-2\beta}$.

Now. With fixed boundary conditions minimal excitation only costs $2J$.

\includegraphics[width=0.5\textwidth,angle=0]{k.eps}

But infinite volume limit does not depend on boundary conditions...
\Cred{Answer: kink-antikink excitation is no elementary. Notice that there
are too many of them, $O(V^2)$}.

$T\longrightarrow 0$, $V$ fixed: eventually find $e^{-4\beta}$. But
scaling limit, small $T$ and large $V$:  $e^{-2\beta}$.

\end{center}
\end{slide*}

% slide 7: Saul and Kardar, algorithm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

\footnotesize

\Cgre{\scriptsize Kardar and Saul, NP B {\bf 432} (1994) 641.} They
reanalyzed the problem by \Cgre{computing exactly the full partition
function}. \CVio{$2D$ Ising Spin Glass with PBC, $J=\pm 1$.}

They follow Kac and Ward:

\begin{enumerate}

\item From high $T$ expansion, in terms of closed graphs on the square
  lattice (including graphs wrapping around the lattice).
\Cred{$$
Z=2^V\left(\cosh\left(\beta J\right)\right)^{2V}
\sum_{c:B}
A_B \tanh\left(\beta J\right)^B
$$}
where the sum is on closed graphs with $B$ bonds.

\item Kac-Ward $\longrightarrow$ the problem is rephrased in a \CVio{local
  random walk with non-trivial weights. $4V\times 4V$ hopping matrix.}

\end{enumerate}

PBC: need four matrices (see later Regge-Zecchina and
Galluccio-L\"obl theorem for graphs
  of bounded genus).
In this case one finds (Potts-Ward, 1955):
\Cgre{$$
Z = \frac12 \left(-Z_1+Z_2+Z_3+Z_4\right)
$$
$$
Z_\lambda=2^V \left(\cosh\left(\beta J\right)\right)^V
\sqrt{\det\left(1-U_\lambda\tanh\left(\beta J\right)\right)}
$$}
$U_\lambda$: $4$ different hopping matrices, of size $4V\times 4V$.

So: \Cbla{$\left\{J_{ij}\right\}$\Cred{$\longrightarrow$} four matrices
$U_\lambda$\Cred{$\longrightarrow$} traces  of $U_\lambda^W$ for $W\le
V$\Cred{$\longrightarrow$} polynomial in $e^{-\beta}$, density of states
\Cred{$\longrightarrow$} $Z=\sum_E N(E) e^{-\beta E}$.}

\end{center}
\end{slide*}

% slide 8: Saul and Kardar, physics
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\small

\begin{center}

Lot of precautions to deal with \Cgre{large numbers} (Kardar and Saul also
compute zeroes of $Z$). 

Polynomial time estimated roughly as \Cgre{$\sim V^{3.2}$}. 

They have basically:

\Cbla{
\begin{tabular}{|c|c|}\hline
L&S\\
4-8&8000\\
10-14&2000\\
16-18&800\\ \hline
\end{tabular}}
and few samples for larger lattices. 
\Cbla{This turns out to be too small...}

So, \Cgre{they disagree with Swendsen-Wang}, and claim
\Cred{$$
c_V \sim \beta^3 e^{-4\beta}
$$}
(note the anomalous power, see fully frustrated Ising model in $2D$). 

\Cgre{Number of excitations looks smaller than in $1D$ Ising}. Claim is here
that 
\Cgre{$$
\log V < S_1-S_0 < \log V^2
$$}
But, again, the authors notice (as a sign of severe warning) 
that they cannot clearly detect the
asymptotic behavior.

\end{center}
\end{slide*}

% slide 9: Our approach.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

\small

\Cbla{\underline{Our approach}}\Cgre{\scriptsize (Galluccio, L\"obl and
Vondr\'ak PRL {\bf 84} (2000) 5924)}

{\footnotesize
Similar to Kardar-Saul, but many further:
\begin{enumerate}
\item theoretical results
\item technical improvements
\end{enumerate}
}

\Cred{Summary:}

$\CVio{Z_\beta^{ISG2D}}\longrightarrow$ \Cgre{generating function of
  cuts} \Cgre{\scriptsize Galluccio-L\"obl: it is possible to solve
  the Max Cut problem in polynomial time for any graph of genus
  bounded by a constant. The method provides directly the generating
  function of cuts.}

$\longrightarrow$ \Cgre{Eulerian subgraphs}

$\longrightarrow$ \Cgre{perfect matching}

$\longrightarrow$ (on graphs of bounded genus) \Cgre{Pfaffian
  computation} (square root of the determinant of an antisymmetric
  matrix). Need $4^g$ Pfaffians.

$\longrightarrow$ compute Pfaffian by using \Cgre{modular arithmetics}
(no need for infinite precision).

$\longrightarrow$ use the \Cgre{Chinese Remainder Theorem} to
reconstruct the exact partition function.

\end{center}
\end{slide*}

% slide 10: a few technical points, 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

\Cred{\underline{Cut}} of a graph $G=(V,E)$ (vertices, edges) is a
partition of its vertices into two disjoint subsets $V_1,V_2\subset V$
and the implied set of edges between the two parts (each edge can
carry a weight $w_e$, and the total weight of the cut is $w(C)$).

\Cred{\underline{Max Cut}}
(\Cred{\underline{min Cut}}):
divide vertices in two parts so that total weight of edges between the
two parts is max (min).

\Cred{\underline{Generating function of cuts}}: polynomial
$$
\sum_{\mbox{over all cuts}} x^{w(C)}\ .
$$

\Cred{\underline{Eulerian subgraph}}: set of edges $U$ such that each
vertex of $V$ is incident with an even number of edges from $U$.

\Cred{\underline{Perfect matching}}: set of edges $P$ such that each
vertex of $V$ is incident with exactly one edge from $P$.

\end{center}
\end{slide*}

% slide 11: a few technical points, 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\scriptsize
\Cred{\underline{From Ising to Cuts}}\\
Assign spins to $+1$ or $-1$.
\Cgre{$V_+=\left\{ i\in V | \sigma_i=+1  \right\}$ }
\Cgre{$V_-=\left\{ i\in V | \sigma_i=-1  \right\}$}.
Let \COra{$C(V_+,V_-)$} be the \COra{cut} of spins~$+1$ and $-1$. 
$W\equiv\sum_{\{i,j\}\in E}J_{ij}$ is the sum of all edge weights in
$G$. 
$$
H=\sum_{\{i,j\}\in C}J_{ij}-\sum_{\{i,j\}\in (E-C)}J_{ij}=2 w(C)-W
$$
Let the \CBro{generating function of cuts} be
\CBro{$$
{\cal C}(G,x)=\sum_{\mbox{cuts in G}}c_k x^{W(C)}\ ,
$$}
where $c_k$ is the number of cuts with weight $k$.
$$
\Cred{Z(\beta)}=\sum_{\{\sigma\}}e^{-\beta H}
\simeq\sum_{\mbox{cuts}}e^{-2\beta w(C)+\beta V}
\simeq e^{\beta V}\Cred{{\cal C}(G,e^{-2\beta})}
$$
\Cred{\underline{From cuts to Eulerian  subgraphs}}
\begin{eqnarray}\nonumber
%\scriptstyle
\COra{{\cal C}(G,e^{-2\beta})} \sim 
&x^{\frac{V}2}&
\prod_{\{i,j\}\in E}\left(
\frac
{x^{ \frac{w_{ij}}{2}}+ 
 x^{-\frac{w_{ij}}{2}}}
{2}\right)\\ \nonumber
&{\COra{\cal E}}&\COra{\left(G,
\frac
{x^{ \frac{w_{ij}}{2}}-
 x^{-\frac{w_{ij}}{2}}}
{x^{ \frac{w_{ij}}{2}}+ 
 x^{-\frac{w_{ij}}{2}}}
\right)}
\end{eqnarray}
\COra{$\cal E$}: generating function of Eulerian subgraphs.

By the Fischer construction Eulerian subgraphs can be rewritten as a
\Cred{\underline{perfect matching}} problem.
\end{center}
\end{slide*}

% slide 12: a few technical points, 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\footnotesize
\begin{center}

\begin{itemize}

\item \Cgre{Kasteleyn for planar graphs}\\
\Cgre{Galluccio-L\"obl for graphs of bounded genus}\\
\Cred{Perfect matching can be translated to a Pfaffian computation (of $4^g$
Pfaffian).}

\item \Cred{Modular arithmetics}. \Cgre{Work modulo some given prime 
number.}\\
\CVio{\underline{Theorem}}: Let $P(x)$ be a polynomial of degree $n$
with integer coefficients, $\Phi(p)$ a finite field of size $p>n$, and
$x_0$, $x_1$, $\ldots$ $x_n$ distinct elements of $\Phi(p)$. Then
there exists a \Cred{unique} polynomial of degree $n$ over $\Phi(p)$
such that
$$
Q(x_i) = P(x_i) \mbox{ mod  } p,\ \ i=0,\ldots,n\ .
$$
The coefficients of $Q(x)$ are equal to the coefficients of $P(x)$ mod $p$.

\item \Cred{The Chinese Remainder Theorem}.\\
If we work in a number large enough of fields, i.e. $p_1$, $p_2$,
$\ldots$, $p_k$ such that
$$
\prod_{i=1}^k p_i > 2^n
$$
we can reconstruct the exact polynomial, i.e. the exact partition
function. \Cred{Great!}

\end{itemize}

\end{center}
\end{slide*}

% slide 13:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\footnotesize
\begin{center}

\underline{\Cred{Summary of the Algorithm}}

\begin{enumerate}

\item Find prime numbers $p_i$ such that
$$
\prod_{i=1}^k p_i > 2^V\ .
$$
For each of them repeat steps 2, 3, 4 performing all operations in
$\Phi(p_i)$. 

\item Select $(m+1)$ distinct elements $x_j$ of $\Phi(p_i)$. For each
  of them repeat step 3.

\item Write the $4^g$ matrices encoding the relevant orientations of
  the modified graph. This gives $Z_\beta$ (in the point
  $e_\beta=x_j$).

\item From these values of $Z_\beta(\mbox{ mod }p_i)$ in given points
  interpolate in $\Phi(p_i)$ and get the coefficients of the polynomial.

\item Apply the Chinese Remainder Theorem: compose the results from
  each $\Phi(p_i)$ to get the full $Z_\beta$.

\end{enumerate}

\Cred{Complexity}: \Cgre{$O(V)$} finite fields, 
\Cgre{$O(V)$} evaluations in each field
(for edge weights bounded by a constant), 
\Cgre{$O(V^{\frac32})$} operations
for a single evaluation of a polynomial \Cbla{$\Longrightarrow$} 
\Cred{Total
$O(V^{\frac72})$}.

\end{center}
\end{slide*}

% slide 14: my comments to the algorithm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}

\begin{center}
\Cbla{Technically this approach and implementation by GLR looks to a ``naive
beginner'' like me full of very brilliant ideas.}

Main features:

\begin{itemize}

\item \Cgre{parallel;}

\item \COra{no problems with precision;}

\item basically only \CVio{bound by CPU time}, not by memory or word length;

\item \Cred{scaling $V^{\frac72}$}.

\end{itemize}

\end{center}
\end{slide*}

% slide 15: details about our work
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

Our work. \Cgre{\scriptsize J. Lukic, A. Galluccio, EM, O. Martin,
  G. Rinaldi}.

\COra{$2D$ Ising Spin Glass, PBC, $J=\pm 1$.}

For example:

\CBro{
\begin{tabular}{|c|c|}\hline
L&S\\
6&400000\\
10&100000\\
30&10000\\ 
40&1000\\ 
50&300\\ \hline
\end{tabular}}

(and similar values for different $L$ values).
\COra{$$
F_J(\beta) = -\frac1\beta \log Z_J(\beta)\ \ ,\ 
U_J(\beta)=\langle H_J\rangle\ \ ,\ 
$$
$$
c_V=L^{-2} \frac{dU_J}{dT}\ ,
$$}
and average over samples.
\Cbla{We mainly look at $c_V$} (irrelevant constants are already subtracted).
\end{center}
\end{slide*}

% slide 16: First picture for specific heat
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\scriptsize
\Cgre{$$ c_V \sim \beta^2 e^{-A\beta} $$}
(we have checked that $p=2$ is the best available choice for power
  corrections).
$$\log \frac{c_V}{\beta^2}\sim -A\beta$$
$$y\equiv\left( \log \frac{c_V}{\beta^2}
  +4\beta\right)=\left(4-A\right)\beta$$
So if we have naive scaling $y\sim \mbox{ constant}$ in the scaling
  regime. If not: slope is $(4-A)$.
\includegraphics[width=0.7\textwidth,angle=270]{cv1.eps}
Small $T$: saturation at constant value.\\
Intermediate $T$: \Cred{$A\sim2$}.\\
Straight line: best fit $\beta \in [2.5,5.5]$ gives \Cbla{$A=2.02\pm 0.03$}.
\end{center}
\end{slide*}

% slide 17: Second picture for specific heat
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}

\begin{center}
\Cbla{
$$
-T\log\left(T^2c_V\right)\sim A
$$}
So look at limit $T\longrightarrow 0$. 

\Cgre{Very interesting scaling pattern.}
\includegraphics[width=0.7\textwidth,angle=270]{cv2.eps}
Three regions:
\begin{itemize}
\item \Cbla{high $T$} \Cred{``no scaling''};
\item \Cbla{low $T$} \Cred{$A=4$ naive behavior};
\item \Cbla{intermediate $T$, large lattices}: \Cred{$A=2$}.
\end{itemize}
\end{center}
\end{slide*}

% slide 18: T=0 subtracted energy and entropy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\small
\Cred{\underline{$T=0$ properties.}}

Lines in the plot are best fits.
$$
e_0(L) = e_0^* + a L^{-2+\theta^e}
$$
$e_0^*=-1.4017(3)$, $\theta^e=-0.08(7)$. We see that as good evidence
that $\theta^e=\theta_{DW}=0$ (\Cgre{\scriptsize Hartmann-Young}).
\includegraphics[width=0.7\textwidth,angle=270]{eneent.eps}
$$
s_0(L) = s_0^* + a L^{-2+\theta^s}
$$
$s_0^*=0.0714(2)$ (most precise estimate available), 
$\theta^s=0.42(2)$. Could be that $\theta^s=0.5$.
\end{center}
\end{slide*}

% slide 19: S1-S0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}

\Cred{\underline{Anomalous density of excitations.}}
$$
S_1-S_0=S(E_0+4J)-S(E_0)
$$
Straight lines: $\log V$, $2 \log V$.

On large lattices: $2\log V$ (Kardar-Saul could only see the transient
behavior on smaller lattices).

\includegraphics[width=0.7\textwidth,angle=270]{dS.eps}

\Cgre{$4J$ excitations ``not elementary'' (following the $1D$ Ising model
terminology)?}
\end{center}
\end{slide*}

% slide 20: csi and FSS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\Cred{\underline{Finite Size Scaling.}}

\Cgre{Difficult} to fit from the numerical data the exact scaling law. 
We use two approaches.

\begin{enumerate}
\item For each $L$ value we determine $T^*(L)$ as the temperature
  where \COra{``something happens''} (where the data separate from the
  envelope). 

Scaling of such $\xi(T)$ obtained by inverting $T^*(L)$ prefers
\Cred{$$ \xi\sim e^\beta
$$}
\Cbla{far over $\xi\sim e^{2\beta}$}. \Cred{Hyperscaling works}.

\item
\CBro{We can use a simple scaling argument based on the finding $S_1-S_0\sim
2\log V$ to find the same behavior}.

\end{enumerate}

\end{center}
\end{slide*}

% slide 21: MKA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide*}
\begin{center}
\small
\Cred{MKA approximation} \Cgre{(to be published)}.\\
\COra{Very similar scaling pattern!}\\
But \Cred{$A=1$}?
Here: MKA, $b=3$ branches, $s=3$ segments.
\includegraphics[width=0.7\textwidth,angle=270]{mka.eps}
$10^4$ samples for $3$ generations. $200$ samples for $9$
generations. 

Here we know that $\theta=0$ (Amoruso et al.). 

Gaussian couplings:
$c_V\sim T^\alpha$ as $T\longrightarrow 0$.

$J=\pm 1$: figure here. \Cbla{Very similar to $2D$ EA spin glass}.

\end{center}
\end{slide*}



% slide X:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{slide*}
%\begin{center}
%\end{center}
%\end{slide*}

\end{document}
