\documentclass[handout]{beamer} 

\usepackage{myslides}
\usepackage{mycitations}
\addbibresource{refs.bib}

\usepackage{localstyle}

\usepackage{mdframed}


\title{Minimum Circuit Size, Graph Isomorphism, and Related Problems}
\author{Andrew Morgan\\
  {\footnotesize University of Wisconsin--Madison}%
}
\institute{Based on work with E. Allender, J. Grochow, D. van
  Melkebeek, and C. Moore}
\date{November 1st, 2018}

\begin{document}



\begin{frame}
  \titlepage
\end{frame}


\begin{frame}
\frametitle{Minimum Circuit Size}

  %Circuit complexity of $x$  = smallest size of circuit with truth-table $x$

  $\MCSP = \{ (x,\theta) :\text{ $x$ has circuit complexity at most $\theta$} \}$

  How hard is $\MCSP$?

\end{frame}


\begin{frame}
\frametitle{How hard is MCSP?}

	Some known reductions:
	\begin{itemize}
    \item<+-> $\pp{Factoring} \in \ZPP^\MCSP$ \hfill
      \mycite{ABKvMR'02/'06}\\
      \hfill\mycitelong{Allender--Buhrman--Kouck\'y--van
      Melkebeek--Ronneburger}
    \item<+-> $\pp{DiscreteLog} \in \ZPP^\MCSP$ \hfill
      \mycite{ABKvMR'02/'06, Rud'16}\\
      \hfill\mycitelong{Allender--Buhrman--Kouck\'y--van
      Melkebeek--Ronneburger, Rudow}
    \item<+-> $\GI \in \RP^\MCSP$ \hfill
      \mycite{AD'14/'17}\mycitelong{Allender--Das}
    \item<+-> $\SZK \subseteq \BPP^\MCSP$ \hfill
      \mycite{AD'14/'17}\mycitelong{Allender--Das}
	\end{itemize}
  \uncover<3->{where}\\
  \uncover<3->{$\GI = $ graph isomorphism }\\
  \uncover<4->{$\SZK = $ problems with statistical zero knowledge
  protocols}

  \uncover<5->{%
	\medskip
	Can replace $\MCSP$ by $\MmuP$ for any complexity measure $\mu$
	polynomially related to circuit size
  }
\end{frame}


\begin{frame}
\frametitle{KT Complexity}
  Describe a string $x$ by a program $p$ so that $p(i) = i$-th bit
  of $x$

	$\KT(x) =$ smallest $|p| + T$, where
	\begin{itemize}
	\item $p$ describes $x$
	\item $p$ runs in at most $T$ steps for all $i$
	\end{itemize}

  %\begin{footnotesize}
  %  (Formally: fix an efficient, universal TM $U$ where
  %  $U(\langle p \rangle,i) = p(i)$.
  %  Measure $|p| = |\langle p \rangle|$ and $T$ wrt $U$.)
  %\end{footnotesize}

  \pause
  \medskip
	$\MKTP = \{ (x,\theta) : \KT(x) \le \theta \}$

	\pause
  \medskip
	Time-bounded Turing machines with advice $\cong$ Circuits\\
	$\implies$ $\KT$ polynomially-related to circuit complexity
\end{frame}


\begin{frame}
\frametitle{How hard is M$\mu$P?}

	Some known reductions:
	\begin{itemize}
    \item $\pp{Factoring} \in \ZPP^\MmuP$ \hfill \mycite{ABKvMR'02/'06}
    \item $\pp{DiscreteLog} \in \ZPP^\MmuP$ \hfill \mycite{ABKvMR'02/'06, Rud'16}
    \item $\GI \in \RP^\MmuP$ \hfill \mycite{AD'14/'17}
    \item $\SZK \subseteq \BPP^\MmuP$ \hfill \mycite{AD'14/'17}
	\end{itemize}
	where\\
	$\GI = $ graph isomorphism \\
	$\SZK = $ problems with statistical zero knowledge protocols
	$\MmuP = \MCSP, \MKTP, \ldots$

  \pause
	\medskip
	Eliminate error in $\GI$ and $\SZK$ reductions?
\end{frame}


\begin{frame}
  \frametitle{A zero-error reduction}

  \begin{mdframed}
    \textbf{Theorem.} $\GI \in \ZPP^\MKTP$ \hfill \myciteme{AGM'15,AGvMMM'18/'18}
  \end{mdframed}

  \pause
  \medskip
  Fundamentally different reduction from before

  \pause
  Extends to any `explicit' isomorphism problem, including several where
  the best known algorithms are still exponential

  \pause
  Doesn't (yet) work for $\MCSP$

\end{frame}


\begin{frame}
  \frametitle{How do the old reductions work?}

  \pause
  Hinge on $\MmuP$ breaking PRGs

  \pause
  PRG from any one-way function
  \hfill\mycite{HILL'89/'99}\mycitelong{H\aa{}stad--Impagliazzo--Levin--Luby}

  \pause
  \medskip
  \begin{mdframed}
    \textbf{Inversion Lemma.} \mycite{ABKvMR'02/'06} There
    is a poly-time randomized Turing machine $M$ using oracle access to
    $\MmuP$ so that the following holds. For any circuit $C$, if
    $\sigma\sim\{0,1\}^n$,
    \[
      \mathrm{Pr}[C(\tau) = C(\sigma)] \ge 1/\poly(|C|)
        \text{ where $\tau = M(C, C(\sigma))$}
    \]
    \hfill\mycitelong{Allender--Buhrman--Kouck\'y--van
    Melkebeek--Ronneburger}
  \end{mdframed}

  \pause
  \medskip
  Example: Fix a graph $G$. Let $C$ map a permutation
  $\sigma$ to $\sigma(G)$.

  $M$ inverts $C$:
  if $\sigma(G)$ is a random permutation of $G$,
  then $M(C, \sigma(G))$ finds $\tau$ s.t. $\tau(G) = \sigma(G)$
  with good probability

\end{frame}


\begin{frame}
  \frametitle{Example: GI in RP\^{}MCSP
  \hfill\mycite{AD'14/'17}\mycitelong{Allender--Das}}

  \begin{mdframed}
    \textbf{Theorem.}
    $\GI \in \RP^\MmuP$
    \hfill \mycite{AD'14/'17}\mycitelong{Allender--Das}
  \end{mdframed}

  \smallskip
  Given $G_0 \cong G_1$, use $M$ to find an isomorphism

  \pause
  \medskip
  
  Let $C(\sigma) = \sigma(G_0)$ where $\sigma \sim S_n$

  \pause
  $M$ inverts $C$: given random $\sigma(G_0)$, $M$ finds $\tau$
  with $\tau(G_0) = \sigma(G_0)$

  \pause

  $G_0 \cong G_1$ implies that
  $\sigma(G_1)$ is distributed the same as $\sigma(G_0)$

  \pause
  So $M(C, \sigma(G_1))$ finds $\tau$ with $\tau(G_0) = \sigma(G_1)$

  \medskip

  \pause
  $\implies$ $\GI \in \RP^\MmuP$
\end{frame}


\begin{frame}
  \frametitle{Eliminating error?}

  Similar results:
	\begin{itemize}
    \item $\pp{Factoring} \in \ZPP^\MmuP$ \hfill \mycite{ABKvMR'02/'06}
    \item $\pp{DiscreteLog} \in \ZPP^\MmuP$ \hfill \mycite{ABKvMR'02/'06, Rud'16}
    \item $\GI \in \RP^\MmuP$ \hfill \mycite{AD'14/'17}
    \item $\SZK \subseteq \BPP^\MmuP$ \hfill \mycite{AD'14/'17}
	\end{itemize}

	How to eliminate error?

	\pause
  $\MmuP$ is only used to \emph{generate} witnesses, which are then
  checked in deterministic polynomial time

  \pause
  Thus, showing $\GI \in \coRP^\MmuP$ using a similar approach
  implicitly requires $\GI \in \coNP$, \textit{i.e.,} $\NP$-witnesses
  for \textbf{non}isomorphism

  \pause
  \textbf{Approach uses $\MKTP$ to help with verification}
\end{frame}

\begin{frame}
  \frametitle{A zero-error reduction}

  \begin{mdframed}
    \textbf{Theorem.} $\GI \in \ZPP^\MKTP$ \hfill \myciteme{AGM'15,AGvMMM'18/'18}
  \end{mdframed}

  \pause
  \bigskip

  Nonisomorphism has $\NP^\MKTP$ witnesses.

  \pause
  \bigskip
  \textbf{Key idea}: $\KT$ complexity is a good estimator for the
  entropy of samplable distributions
\end{frame}



\section{Graph Isomorphism in ZPP\^{}MKTP}

%\AtBeginSubsection[]{%
%\begin{frame}
%  \tableofcontents[sectionstyle=show/hide,%
%    subsectionstyle=show/shaded/hide]
%\end{frame}
%}

\subsection{Definitions}


\begin{frame}
\frametitle{Graph Isomorphism}
  $\GI = $ decide whether two given graphs ($G_0$, $G_1$) are isomorphic

  \pause
  $\Aut(G)$ = group of automorphisms of $G$

  \pause
  Number of distinct permutations of $G$ = $n!/|\Aut(G)|$

  \pause
  To show $\GI \in \ZPP^\MKTP$, suffices to show $\GI\in\coRP^\MKTP$,
  \ie, to witness nonisomorphism
\end{frame}


\begin{frame}
\frametitle{KT Complexity}
  Recall: $\KT(x) =$ smallest $|p| + T$ where $p$ describes $x$ in time
  $T$

  \pause
  Intuition for bounding $\KT(x)$:
	describe a string $x$ by a program $p$ taking advice $\alpha$ so that
	$p^\alpha(i) = i$-th bit of $x$

  \pause
  $\KT(x)$ is smallest $|p|+|\alpha|+T$ where
	\begin{itemize}
	\item $p$ with advice $\alpha$ describes $x$
	\item $p$ runs in at most $T$ steps for all $i$
	\end{itemize}

\end{frame}


\begin{frame}
  \frametitle{KT Complexity}

  Examples:
  \pause
  \begin{enumerate}
    \item<1-|handout:1-> $\KT(0^n) = \polylog(n)$ \\
      \uncover<3-|handout:1->{%
        Store $n$ in advice, define $p(i)$ to output 0 if $i \le n$, and
        end-of-string otherwise
      }
    \item<4-|handout:1-> $G = $ adjacency matrix of a graph\\
      $\KT(G) \le $ \uncover<5-|handout:1->{${n \choose 2} + \polylog(n)$}
    \item<6-|handout:1-> Let $y = $ $t$ copies of $G$ \\
      $\KT(y) \le $ \uncover<7-|handout:1->{$\KT(G) + \polylog(nt)$}
    \item<8-|handout:1->
      Let $y = $ sequence of $t$ numbers from
        $\{5,10,10^{300},-46\}$\\
      \uncover<9-|handout:1->{
          $O(1)$ bits to describe the set, plus $2t$ bits to describe
          the sequence given the set}\\
      \uncover<9-|handout:1->{$\KT(y) \le 2t + \polylog(t)$}
  \end{enumerate}
\end{frame}


\subsection{Rigid graphs}

\begin{frame}
  \frametitle{Witnessing nonisomorphism: rigid graphs}

  Let $G_0, G_1$ be \emph{rigid} graphs, \ie, no non-trivial automorphisms

  \pause
  Key fact: if $G_0 \cong G_1$, there are $n!$ distinct graphs among
  permutations of $G_0$ and $G_1$;
  if $G_0 \not\cong G_1$, there are $2(n!)$.

  \pause
  Consider sampling $r \sim \{0,1\}$ and $\pi \sim S_n$ uniformly,
  and outputting the adjacency matrix of $\pi(G_r)$.
  \begin{itemize}
    \item<4-> If $G_0 \cong G_1$, this has entropy $s \doteq \log(n!)$
    \item<5-> If $G_0 \not\cong G_1$, this has entropy $s+1$
  \end{itemize}

  \pause
  \pause
  \pause
  Main idea: use $\KT$-complexity of a random sample to estimate the entropy

\end{frame}


\begin{frame}
  \frametitle{Witnessing nonisomorphism: rigid graphs}
  Let $y = \pi(G_r)$, $\pi \sim S_n$, $r \sim \{0,1\}$.

  Hope: $\KT(y)$ is \textit{typically near} the entropy,
  \textbf{never} much larger
  \begin{center}
  \begin{tikzpicture}
    \coordinate (nls) at (2,3);
    \coordinate (nlI) at (4,3);
    \coordinate (nlT) at (5,3);
    \coordinate (nlN) at (6,3);
    \coordinate (nlt) at (7,3);
    \node (iso) at (0,2) {$G_0 \cong G_1$};
    \node (non) at (0,1) {$G_0 \not\cong G_1$};
    \coordinate (isos) at (2,2);
    \coordinate (isot) at (4,2);
    \coordinate (nisos) at (2,1);
    \coordinate (nisot) at (6,1);
    \coordinate (nlTb) at (5,0.5);
    \draw[black,ultra thick] (nls) -- (nlt);
    \draw[black,thick,dotted] (isos) -- ($(isot) + (-0.3,0)$);
    \draw[black,thick,dotted] (nisos) -- ($(nisot) + (-0.3,0)$);
    \draw[black,thick,dashed] (nlT) -- (nlTb);
    \draw[|-|,solid] ($(isot) + (-0.3,0)$) -- ($(isot) + (0.3,0)$);
    \draw[|-|,solid] ($(nisot) + (-0.3,0)$) -- ($(nisot) + (0.3,0)$);
    \draw[|-,ultra thick] (nlI) -- ($(nlI)+(0.01,0)$);
    \draw[|-,ultra thick] (nlN) -- ($(nlN)+(0.01,0)$);
    \node at ($(nlI) + (0,1.3em)$) {\footnotesize $s$};
    \node at ($(nlN) + (0.5em,1.3em)$) {\footnotesize $s+1$};
    \node at ($(nlT) + (0,1.3em)$) {$\theta$};
  \end{tikzpicture}
  \end{center}
  where $s = \log(n!)$

  Then $\KT(y) > \theta$ is a witness of nonisomorphism.
\end{frame}


\begin{frame}
  \frametitle{Witnessing nonisomorphism: rigid graphs}
  Let $y = \pi_1(G_{r_1})\pi_2(G_{r_2})\cdots\pi_t(G_{r_t})$,
  $\pi_i \sim S_n$, $r_i \sim \{0,1\}$.

  Truth: $\KT(y)/t$ is \textit{typically near} the entropy,
  \textbf{never} much larger
  \begin{center}
  \begin{tikzpicture}
    \coordinate (nls) at (2,3);
    \coordinate (nlI) at (4,3);
    \coordinate (nlT) at (5,3);
    \coordinate (nlN) at (6,3);
    \coordinate (nlt) at (7,3);
    \node (iso) at (0,2) {$G_0 \cong G_1$};
    \node (non) at (0,1) {$G_0 \not\cong G_1$};
    \coordinate (isos) at (2,2);
    \coordinate (isot) at (4,2);
    \coordinate (nisos) at (2,1);
    \coordinate (nisot) at (6,1);
    \coordinate (nlTb) at (5,0.5);
    \draw[black,ultra thick] (nls) -- (nlt);
    \draw[black,thick,dotted] (isos) -- ($(isot) + (-0.3,0)$);
    \draw[black,thick,dotted] (nisos) -- ($(nisot) + (-0.3,0)$);
    \draw[black,thick,dashed] (nlT) -- (nlTb);
    \draw[|-|,solid] ($(isot) + (-0.3,0)$) -- ($(isot) + (0.3,0)$);
    \draw[|-|,solid] ($(nisot) + (-0.3,0)$) -- ($(nisot) + (0.3,0)$);
    \draw[|-,ultra thick] (nlI) -- ($(nlI)+(0.01,0)$);
    \draw[|-,ultra thick] (nlN) -- ($(nlN)+(0.01,0)$);
    \node at ($(nlI) + (0,1.3em)$) {\footnotesize $s$};
    \node at ($(nlN) + (0.5em,1.3em)$) {\footnotesize $s+1$};
    \node at ($(nlT) + (0,1.3em)$) {$\theta$};
  \end{tikzpicture}
  \end{center}
  where $s = \log(n!)$

  Then $\KT(y)/t > \theta$ is a witness of nonisomorphism.
\end{frame}


\begin{frame}
  \frametitle{Bounding KT in isomorphic case}
  Let $y = \pi_1(G_{r_1})\pi_2(G_{r_2})\cdots\pi_t(G_{r_t})$.
  Goal: $\KT(y) \ll ts + t$.

  \pause
  Since $G_0 \cong G_1$, rewrite
  $y = \tau_1(G_0)\tau_2(G_0)\cdots\tau_t(G_0)$.

  \pause
  Describe $y$ as\\
  \begin{itemize}
    \item<3-> Fixed data: $n$, $t$, adjacency matrix of $G_0$
    \item<4->
      Per-sample data: $\tau_1,\ldots,\tau_t$
    \item<5->
      Decoding algo:
      to output $j$-th bit of $y$, look up appropriate $\tau_i$
      and compute $\tau_i(G_0)$
  \end{itemize}

  \pause\pause\pause
  Suppose each $\tau_i$ can be encoded into $s$ bits:
  \begin{align*}
    \KT(y) &<
    \underbrace{O(1)}_{|p|}
    + \underbrace{\poly(n,\log t) + ts}_{|\alpha|}
    + \underbrace{\poly(n,\log t)}_{T} \\
    &= ts + \poly(n,\log t) \ll ts+t \text{ ($t$ large)}
  \end{align*}
\end{frame}


\begin{frame}
  \frametitle{Rigid graphs: Isomorphic case}
  \begin{mdframed}
  \textbf{Lehmer Code.} There is an indexing of $S_n$ by the numbers
  $1,\ldots,n!$ so that the $i$-th permutation can be decoded from the
  binary representation of $i$ in time $\poly(n)$.
  \end{mdframed}

  \pause
  Na\"ive conversion to binary: $\KT(y) < t\ceil{s} + \poly(n,\log t)$

  \only<1-2>{\hspace{14.7em} }
  \only<3>{\hspace{14.7em} $\ll ts + t$ ?}
  \only<4->{\hspace{14.7em} $\not\ll ts + t$ \hspace{0.25cm}}
  \pause
  \pause

  \pause
  Blocking trick: amortize encoding overhead across samples
  
  \pause
  Yields for some $\delta > 0$, $\KT(y) \le ts + t^{1-\delta} \poly(n)$,

  i.e., $\KT(y)/t \le s + \poly(n)/t^\delta$
\end{frame}


\begin{frame}
  \frametitle{Rigid graphs: Recap}

  Let $y = \pi_1(G_{r_1})\pi_2(G_{r_2})\cdots\pi_t(G_{r_t})$.

  If $G_0 \cong G_1$, then $\KT(y)/t \le s + o(1)$ always holds

  If $G_0 \not\cong G_1$, then as $y$ is $t$ independent samples from a
  distribution of entropy $s+1$, $\KT(y)/t \ge s+1-o(1)$ holds w.h.p.

  \pause
  \medskip
  $\implies$ $\coRP^\MKTP$ algorithm for $\GI$ on rigid graphs
\end{frame}


\subsection{General graphs}

\begin{frame}
  \frametitle{General graphs}

  Assume for simplicity that there are as many distinct permutations of
  $G_0$ as of $G_1$.

  \pause
  Let $s$ be entropy in random permutation of $G_i$: $\log(
  n!/|\Aut(G_i)|)$

  \pause
  Sample $y = \pi_1(G_{r_1})\cdots\pi_t(G_{r_t})$,
  hope $\KT(y)/t$ looks the same:

  \begin{center}
    \begin{tikzpicture}[yscale=0.6]
    \coordinate (nls) at (2,3);
    \coordinate (nlI) at (4,3);
    \coordinate (nlT) at (5,3);
    \coordinate (nlN) at (6,3);
    \coordinate (nlt) at (7,3);
    \node (iso) at (0,2) {$G_0 \cong G_1$};
    \node (non) at (0,1) {$G_0 \not\cong G_1$};
    \coordinate (isos) at (2,2);
    \coordinate (isot) at (4,2);
    \coordinate (nisos) at (2,1);
    \coordinate (nisot) at (6,1);
    \coordinate (nlTb) at (5,0.5);
    \draw[black,ultra thick] (nls) -- (nlt);
    \draw[black,thick,dotted] (isos) -- ($(isot) + (-0.3,0)$);
    \draw[black,thick,dotted] (nisos) -- ($(nisot) + (-0.3,0)$);
    \draw[black,thick,dashed] (nlT) -- (nlTb);
    \draw[|-|,solid] ($(isot) + (-0.3,0)$) -- ($(isot) + (0.3,0)$);
    \draw[|-|,solid] ($(nisot) + (-0.3,0)$) -- ($(nisot) + (0.3,0)$);
    \draw[|-,ultra thick] (nlI) -- ($(nlI)+(0.01,0)$);
    \draw[|-,ultra thick] (nlN) -- ($(nlN)+(0.01,0)$);
    \node at ($(nlI) + (0,1.3em)$) {\footnotesize $s$};
    \node at ($(nlN) + (0.5em,1.3em)$) {\footnotesize $s+1$};
    \node at ($(nlT) + (0,1.3em)$) {$\theta$};
  \end{tikzpicture}
  \end{center}

  \only<4-5|handout:1>{%
    If $G_0 \not\cong G_1$, $\KT(y)/t > s+1-o(1)$ w.h.p.
  }

  \only<5|handout:1>{%
    If $G_0 \cong G_1$, $y$ has entropy $ts$, hope a similar encoding
    shows $\KT(y)/t \le s + o(1)$.
  }
  
  \uncover<6-7|handout:2>{%
  Two complications:\\
  \begin{itemize}
  \item<6-7|handout:2>
    Encoding distinct permutations of $G_0$ as numbers $1,\ldots,n!$ is too
    expensive
  \item<7|handout:2>
    Knowing $\theta$ requires knowing $|\Aut(G_i)|$
  \end{itemize}
  }

\end{frame}


\begin{frame}
\frametitle{General graphs: encoding permutations of graphs}

  Indexing the various permutations of a non-rigid graph $G$ as numbers
  $1,\ldots,n!$ is too expensive

  Need to use numbers $1,\ldots,N$ where $N = n!/|\Aut(G)|$

  Such a specific encoding exists, but will see a more
  general-purpose substitute soon

\end{frame}


\begin{frame}
\frametitle{General graphs: computing $\theta$}

\pause
It suffices to give a \emph{probably-approximately-correct overestimator} (PAC
overestimator) for $\theta$:
\begin{center}
\begin{tikzpicture}
	\coordinate (nls) at (2,4);
	\coordinate (nlI) at (4,4);
	\coordinate (nlT) at (5,4);
	\coordinate (nlN) at (6,4);
	\coordinate (nlt) at (7,4);
	\node (pcoe) at (0,3) {$\widetilde{\theta}$};
	\node (iso) at (0,2) {$KT(y)/t, G_0 \cong G_1$};
	\node (non) at (0,1) {$KT(y)/t, G_0 \not\cong G_1$};
	\coordinate (pcoes) at (5,3);
	\coordinate (pcoet) at (7,3);
	\coordinate (isos) at (2,2);
	\coordinate (isot) at (4,2);
	\coordinate (nisos) at (2,1);
	\coordinate (nisot) at (6,1);
	\coordinate (nlTb) at (5,0.5);
	\draw[black,ultra thick] (nls) -- (nlt);
  \draw[black,thick,dotted] ($(pcoes) + (0.3,0)$) -- (pcoet);
  \draw[black,thick,dotted] (isos) -- ($(isot) + (-0.3,0)$);
  \draw[black,thick,dotted] (nisos) -- ($(nisot) + (-0.3,0)$);
	\draw[black,thick,dashed] (nlT) -- (nlTb);
	\draw[|-|,solid] ($(pcoes) + (-0.3,0)$) -- ($(pcoes) + (0.3,0)$);
	\draw[|-|,solid] ($(isot) + (-0.3,0)$) -- ($(isot) + (0.3,0)$);
	\draw[|-|,solid] ($(nisot) + (-0.3,0)$) -- ($(nisot) + (0.3,0)$);
	\draw[|-,ultra thick] (nlI) -- ($(nlI)+(0.01,0)$);
	\draw[|-,ultra thick] (nlN) -- ($(nlN)+(0.01,0)$);
	\node at ($(nlI) + (0,1.3em)$) {\footnotesize $s$};
	\node at ($(nlN) + (0.5em,1.3em)$) {\footnotesize $s+1$};
	\node at ($(nlT) + (0,1.3em)$) {$\theta$};
\end{tikzpicture}
\end{center}

\pause
Equivalently, it suffices to give a PAC \emph{under}estimator for $\log|\Aut(G_i)|$,
since $\theta = (\log n! - \log|\Aut(G_i)|) + 1/2$

\end{frame}


\begin{frame}
\frametitle{General graphs: computing $\theta$}

  \textbf{Claim.} There is an efficient randomized algorithm using
  $\MKTP$ to PAC underestimate $\log|\Aut(G)|$ when given $G$.

  \pause
  \bigskip
  \textit{Proof.}
  Recall that there is a deterministic algorithm using an oracle for
  $\GI$ that computes generators for $\Aut(G)$.

  \pause
  Plug in an existing $\RP^\MKTP$ algorithm for the oracle: this gives
  us generators for a group $A$ with $A = \Aut(G)$ w.h.p.

  \pause
  Prune generators of $A$ not in $\Aut(G)$ $\implies A \le \Aut(G)$

	\pause
	$|A|$ can be computed efficiently from its generators.
  Output $\log|A|$.

\end{frame}


\begin{frame}
  \frametitle{General graphs: Recap}

  $y = \pi_1(G_{r_1})\pi_2(G_{r_2})\cdots\pi_t(G_{r_t})$

  $s = \log n!/|\Aut(G_i)|$

  \begin{center}
  \begin{tikzpicture}[yscale=0.8]
    \coordinate (nls) at (2,4);
    \coordinate (nlI) at (4,4);
    \coordinate (nlT) at (5,4);
    \coordinate (nlN) at (6,4);
    \coordinate (nlt) at (7,4);
    \node (pcoe) at (0,3) {$\widetilde{\theta}$};
    \node (iso) at (0,2) {$KT(y)/t, G_0 \cong G_1$};
    \node (non) at (0,1) {$KT(y)/t, G_0 \not\cong G_1$};
    \coordinate (pcoes) at (5,3);
    \coordinate (pcoet) at (7,3);
    \coordinate (isos) at (2,2);
    \coordinate (isot) at (4,2);
    \coordinate (nisos) at (2,1);
    \coordinate (nisot) at (6,1);
    \coordinate (nlTb) at (5,0.5);
    \draw[black,ultra thick] (nls) -- (nlt);
    \draw[black,thick,dotted] ($(pcoes) + (0.3,0)$) -- (pcoet);
    \draw[black,thick,dotted] (isos) -- ($(isot) + (-0.3,0)$);
    \draw[black,thick,dotted] (nisos) -- ($(nisot) + (-0.3,0)$);
    \draw[black,thick,dashed] (nlT) -- (nlTb);
    \draw[|-|,solid] ($(pcoes) + (-0.3,0)$) -- ($(pcoes) + (0.3,0)$);
    \draw[|-|,solid] ($(isot) + (-0.3,0)$) -- ($(isot) + (0.3,0)$);
    \draw[|-|,solid] ($(nisot) + (-0.3,0)$) -- ($(nisot) + (0.3,0)$);
    \draw[|-,ultra thick] (nlI) -- ($(nlI)+(0.01,0)$);
    \draw[|-,ultra thick] (nlN) -- ($(nlN)+(0.01,0)$);
    \node at ($(nlI) + (0,1.3em)$) {\footnotesize $s$};
    \node at ($(nlN) + (0.5em,1.3em)$) {\footnotesize $s+1$};
    \node at ($(nlT) + (0,1.3em)$) {$\theta$};
  \end{tikzpicture}
  \end{center}

  Witness of nonisomorphism: $\KT(y)/t > \tilde{\theta}$

  \begin{mdframed}
    \textbf{Theorem.} $\GI \in \ZPP^\MKTP$ \hfill \myciteme{AGvMMM'18/'18}
  \end{mdframed}
\end{frame}

%\AtBeginSubsection[]{}


\section{Generic Encoding Lemma}

\begin{frame}
  \frametitle{Encoding outputs of samplable distributions}

  We saw that for any rigid graph $G$, the $n!$ distinct permutations of
  $G$ can be encoded as integers $1,\ldots,n!$.

  \pause
  This can be extended to general graphs,
  but still involves heavy use of the structure of the symmetric group.

  \pause
  What about other groups?

  \pause
  Is algebraic structure necessary?
\end{frame}


\begin{frame}
  \frametitle{Encoding outputs of samplable distributions}

  Turns out: can encode the outcomes of \emph{any} samplable
  distribution.

  Flatter distributions $\implies$ better encodings.

  \pause
  Rare events are hard to encode. So assume that all outcomes
  are somewhat likely.

  \pause
  Define the \emph{max-entropy} of a distribution to be the
  smallest $s$ such that all outcomes occur with probability
  at least $2^{-s}$ (or zero).

  \pause
  \begin{mdframed}
  \textbf{Encoding Lemma.}
  Let $C$ be a circuit sampling a distribution of max-entropy $s$.
  There is a circuit $D$ of size $\poly(|C|)$ and, for each outcome $y$,
  a string $i_y$ of length $s + \log s + O(1)$, s.t. $D(i_y) = y$.
  \end{mdframed}

  \pause
  Proof based on hashing
\end{frame}


\begin{frame}
\frametitle{Encoding outputs of samplable distributions}
  Example: $C$ samples a random permutation of a graph $G$.
  Then each permutation of $G$ can be decoded from a string of length
  $s + \log s + O(1)$, where $s = \log( n!/|\Aut(G)| )$

  \pause
  Overhead of $\log s + O(1)$ is worse than $\ceil{s} - s$,
  but can still be amortized out.

  \pause
  End result: for any graph $G$, any $t$ permutations of $G$ has
  $\KT$-complexity at most $ts + t^{1-\delta}\poly(n)$.

  \pause
  In general, for any circuit $C$ of max-entropy $s$, any $t$
  samples from $C$ has $\KT$-complexity at most
  $ts + t^{1-\delta}\poly(|C|)$.

\end{frame}


\begin{frame}
  \frametitle{Entropy estimation}

  \begin{mdframed}
    \textbf{Entropy Estimator Theorem.} \hfill \myciteme{AGvMMM'18/'18} \\
    Let $C$ be any circuit sampling a distribution of max-entropy
    $s_\text{max}$ and min-entropy $s_\text{min}$.
    Let $y$ be the concatenation of $t$ independent samples from $C$.
    Then $\KT(y)/t$ is typically between $s_\text{min}-o(1)$ and
    $s_\text{max}+o(1)$, and never much larger.
  \end{mdframed}

  \begin{center}
  \begin{tikzpicture}[yscale=0.8]
    \coordinate (nls) at (2,4);
    \coordinate (nl0) at (4,4); %min entropy
    \coordinate (nlX) at (6,4); %max entropy
    \coordinate (nlt) at (7,4);
    \node (kty) at (0,3) {$KT(y)/t$};
    \coordinate (ktys) at (2,3);
    \coordinate (kty0) at (4,3);
    \coordinate (ktyX) at (6,3);
    \draw[black,ultra thick] (nls) -- (nlt);
    \draw[black,thick,dotted] (ktys) -- ($(kty0) + (-0.3,0)$);
    \draw[|-|,solid,thick] ($(kty0) + (-0.3,0)$) -- ($(ktyX) + (0.3,0)$);
    \draw[|-,ultra thick] (nl0) -- ($(nl0)+(0.01,0)$);
    \draw[|-,ultra thick] (nlX) -- ($(nlX)+(0.01,0)$);
    \node at ($(nl0) + (0,1.3em)$) {\footnotesize $s_\text{min}$};
    \node at ($(nlX) + (0,1.3em)$) {\footnotesize $s_\text{max}$};
  \end{tikzpicture}
  \end{center}

  \pause
  Nice case: $s_\text{max} - s_\text{min} = o(1)$.
  $C$ is ``almost flat''.

\end{frame}


\section{Extensions for General Isomorphism Problems}


\begin{frame}
  \frametitle{General isomorphism problem}

  Group $H$ acts on a universe $\Omega$. Given $\omega_0, \omega_1 \in
  \Omega$, decide whether some $h \in H$ sends $\omega_0$ to $\omega_1$.
  Assume products, inverses, etc.\ are efficiently computable.

  \pause
  \medskip
  Example 1: With $\GI$, $H = S_n$, $\Omega = $ labeled $n$-vertex graphs,
  where $H$ acts by permuting labels.
  $\omega_0 = G_0$ and $\omega_1 = G_1$.
  Find a permutation sending $G_0$ to $G_1$.

  \pause
  \medskip
  Example 2: ``Matrix Subspace Conjugacy''.
  \pause
  $\Omega = $ subspaces of $\FF^{n\times n}$,
  given by a basis (a set of \emph{matrices}).
  $H = \GL_n(\FF)$, acting by conjugation.
  \pause
  Given $\{M_1, M_2, \ldots, M_k\}$
  and $\{N_1, N_2, \ldots, N_k\}$,
  is there $T$ so that\\
  \begin{small}$\VSspan\{ T^{-1}M_1T, T^{-1}M_2T, \ldots, T^{-1}M_kT \}
  = \VSspan\{ N_1, N_2, \ldots, N_k \}$\end{small}?
\end{frame}


\begin{frame}
\frametitle{Beyond GI}

  With the entropy estimator theorem in hand, the techniques for $\GI$
  mostly generalize

  \pause
  Only obstacle: PAC overestimating $\theta$/underestimating $\log|\Aut(G)|$

  \pause
  Recall, we did this by
  \begin{enumerate}
    \item
      using a search-to-decision reduction to find generators for
      $\Aut(G)$, and 
    \item
      computing $|\Aut(G)|$ efficiently from its generators
  \end{enumerate}

  \pause
  What to do when a search-to-decision reduction isn't known?
  What if the ambient group isn't $S_n$?
\end{frame}


\begin{frame}
  \frametitle{PAC underestimating log \textbar{}Aut(G)\textbar{}}

  Idea: PAC underestimate $\log|\Aut(G)|$ using the entropy estimator
  theorem again

  \pause
  $\Aut(G)$ efficiently samplable implies amortized $\KT$-complexity PAC
  underestimates $\log|\Aut(G)|$

  \pause
  Let $y' = \pi_1\pi_2\cdots\pi_t$ be $t$ random elements of $\Aut(G)$

  \pause
  Need $\Aut(G)$ efficiently samplable twice:\\
  - Construction of $y'$ in the algorithm\\
  - Analysis of $\KT(y')$

  \pause
  Note: these sampling procedures \emph{need not be the same}.

  \pause
  Show \\
  - how to use $\MKTP$ to sample $\Aut(G)$ with only $G$ on hand \\
  - for every $G$, there is a circuit $C_{G}$ which samples
    $\Aut(G)$ uniformly

\end{frame}


\begin{frame}
\frametitle{How to sample Aut(G) with MKTP}

  Recall that $\MKTP$ can be used to invert circuits.

  \pause
  \begin{mdframed}
    \textbf{Inversion Lemma.} \mycite{ABKvMR'02/'06} There
    is a poly-time randomized Turing machine $M$ using oracle access to
    $\MmuP$ so that the following holds. For any circuit $C$, if
    $\sigma\sim\{0,1\}^n$,
    \[
      \mathrm{Pr}[C(\tau) = C(\sigma)] \ge 1/\poly(|C|)
        \text{ where $\tau = M(C, C(\sigma))$}
    \]
    \hfill\mycitelong{Allender--Buhrman--Kouck\'y--van
    Melkebeek--Ronneburger}
  \end{mdframed}

  \pause
  Let $C$ sample a random permutation $\pi$ and output $\pi(G)$

  Pick $\pi \sim S_n$ at random, let $\tau = M(C, \pi(G))$.
  With probability $1/\poly(n)$, $\tau(G) = \pi(G)$,
  so $\tau^{-1} \circ \pi \in \Aut(G)$.

  \pause
  Conditioned on $\pi(G)$, $\tau$ and $\pi$ are independent,
  so $\tau^{-1} \circ \pi$ is uniform on $\Aut(G)$.

\end{frame}


\begin{frame}
\frametitle{How to sample Aut(G) with a small circuit}

\pause
A sequence $\pi_1,\pi_2,\ldots,\pi_k$ of elements of a finite group
  $\Gamma$ is said to be \emph{Erd\H{o}s--R\'enyi} if the `random
  subproduct'
  \[
    \pi_1^{r_1}\pi_2^{r_2}\cdots \pi_k^{r_k}, \quad r_i \sim \{0,1\}
  \]
  is distributed approximately uniformly on $\Gamma$.
  ($s_\text{max} - s_\text{min} = o(1)$)

  \pause
  Erd\H{o}s and R\'enyi showed that every finite group has such a
  generating set of size $\poly(\log|\Gamma|)$. \mycite{ER'65}

  \pause
  With $\Gamma = \Aut(G)$, obtain an ER generating set of size
  $\poly(n)$.

  \pause
  Hardwire the ER set into a circuit sampling the random subproduct.

\end{frame}



\section{Other Applications of KT v.\ Entropy}

\begin{frame}
  \frametitle{KT versus entropy: other applications}
  More theorems and consequences:
  \begin{itemize}
    \item<+->
      Any `explicit' iso.\ problem is in $\ZPP^\MKTP$ \hfill\myciteme{AGvMMM'18/'18}
    \item<+->
      New proof of $\SZK \subseteq \BPP^\MKTP$ \hfill\myciteme{AGvMMM'18/'18}
    \item<+->
      $\DET \subseteq \AC_0^\MKTP$. Consequently, $\MKTP \not\in
      \AC^0[p]$\\
      \hfill\mycite{AH'17}\mycitelong{Allender--Hirahara}
    \item<+->
      Random-3SAT, Planted Clique $\le$ $\MKTP$\\
      \hfill\mycite{HS'17}\mycitelong{Hirahara--Santhanam}
    %\item
    %  $\pp{MAJORITY} \le \MKTP$ by a very simple reduction \hfill\mycite{unpub}
  \end{itemize}
\end{frame}



\section{Open Problems}


\begin{frame}
\frametitle{Open problem: SZK?}

  Techniques essentially boil down to estimating entropy by
  $\KT$-complexity

  Complete problem for $\SZK$:
  determine whether a given samplable distribution has entropy at least
  a given threshold

  \pause
  Entropy estimator theorem can reproduce $\SZK \subseteq \BPP^\MKTP$

  \pause
  $\SZK \subseteq \ZPP^\MKTP$ ?

  \pause
  Obstacle is devising witnesses for non-flat distributions

  \pause
  There are distributions with low entropy but supported on every
  string---nontrivial worst-case bound on $\KT$-complexity is
  impossible.

\end{frame}


\begin{frame}
\frametitle{Open problem: What about MCSP?}

  \pause
  The argument should work for $\MCSP$, but fails for annoying technical
  reasons. This is true even for rigid-$\GI$.

  %\pause
  %Morally sufficient to have the following: some efficiently computable
  %function $L : \NN \to \NN$ such that
  %\begin{itemize}
  %  \item
  %    Every truth table of size $N$ has circuits of size $\le L(N)$
  %  \item
  %    For some $\delta < 1$, a random $N$-bit truth table requires
  %    circuits of size $\ge L(N) - (L(N))^{\delta}$
  %\end{itemize}
  %\pause
  %We know $L(N) \approx N/\log N$, but lower-order terms matter

  %\pause
  %Best $L$ known to satisfy first condition guarantees only
  %$\ge L(N) - L(N)/\polylog L(N)$ in second

  \pause
  Use $\KT$ complexity in two ways:
  \begin{itemize}
    \item<4-> Counting argument: $\KT(y) \gtrsim ts + t$ whp
    \item<5-> Encoding: any string of length $ts$ has $\KT \lesssim ts$
  \end{itemize}

  \pause
  \pause
  \pause
  For circuits, we get:
  \begin{itemize}
    \item<7-> Counting argument: $\CSIZE(y) \gtrsim (ts+t)/\log(ts+t)$
      whp
    \item<8-> Encoding: any string of length $ts$ has
      $\CSIZE \lesssim ts/\log(ts)$
  \end{itemize}

  \pause
  \pause
  \pause
  Low-order terms matter: best known bounds require exponentially-large
  $t$ to force gap between the isomorphic and nonisomorphic cases

\end{frame}


\begin{frame}
\frametitle{Open problem: What about MCSP?}

  Resolving these bounds is only so satisfactory:
  the answer probably depends on the precise measure of circuit
  complexity.

  \pause
  Better: boost the gap in entropy between the isomorphic and
  nonisomorphic cases, then use polynomial relationship between $\KT$
  and circuit size

\end{frame}


\begin{frame}
  \frametitle{Summary}

  \begin{itemize}
    \item<+->
      Reviewed old reductions to $\MCSP/\MKTP$ based on Inversion Lemma
    \item<+->
      Showed a different kind of reduction from $\GI$ to $\MKTP$ based
      on estimating entropy by $\KT$ complexity
    \item<+->
      Stated Encoding Lemma and Entropy Estimator Theorem
    \item<+->
      Sketched extension to general isomorphism problems
    \item<+->
      Listed other uses of estimating entropy by $\KT$ complexity
    \item<+->
      Open problems: $\SZK$? $\MCSP$?
  \end{itemize}

  \uncover<7>{\textbf{Questions?}}
\end{frame}


\section{Thank you!}


\begin{frame}
  \frametitle{Random-3SAT reduces to MKTP \hfill
  \mycite{HS'17}\mycitelong{Hirahara--Santhanam}}

  Random-3SAT (baby version): Given either
  \begin{itemize}
    \item Satisfiable 3-CNF
    \item Random 3-CNF with many clauses (likely unsatisfiable)
  \end{itemize}
  distinguish between the two cases.

  \pause
  Idea: Existence of a satisfying assignment gives information about
  the 3-CNF, so it should be easier to describe.

  \pause
  For a satisfying assignment $x$, sample a random clause that $x$
  satisfies. Entropy: $\log{n\choose 3} + \log(7)$. \\
  \pause
  $\implies$ amortized $\KT$-complexity \textbf{always} bounded

  \pause
  For random 3-CNF: random clause has entropy $\log{n\choose 3} + \log(8)$ \\
  \pause
  $\implies$ amortized $\KT$-complexity typically high
\end{frame}


\begin{frame}
  \frametitle{Planted Clique reduces to MKTP
  \hfill\mycite{HS'17}\mycitelong{Hirahara--Santhanam}}

  Planted clique: Given either
  \begin{itemize}
    \item Uniformly random graph
    \item Uniformly random graph union with a random $k$-clique
  \end{itemize}
  distinguish between the two cases.

  \pause
  \medskip
  Uniformly random graph has entropy ${n\choose 2}$

  \pause
  Random graph with clique has entropy at most
  ${n\choose 2} + \log{n\choose k} - {k\choose 2}$

  \pause
  \mycite{HS'17}\mycitelong{Hirahara--Santhanam} show $\KT$-complexity closely matches entropy
\end{frame}

\end{document}
