equal
deleted
inserted
replaced
135 |
135 |
136 \begin{center} |
136 \begin{center} |
137 \includegraphics[scale=0.15]{../pics/cake.jpg} |
137 \includegraphics[scale=0.15]{../pics/cake.jpg} |
138 \end{center}\pause\bigskip |
138 \end{center}\pause\bigskip |
139 |
139 |
|
140 \small |
140 Solves the problem of communication when both parties |
141 Solves the problem of communication when both parties |
141 distrust each other, |
142 distrust each other. |
142 |
143 |
143 \end{frame} |
144 \end{frame} |
144 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 |
146 |
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
214 |
215 |
215 \end{itemize} |
216 \end{itemize} |
216 \end{frame}} |
217 \end{frame}} |
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
218 |
219 |
219 |
|
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
221 \begin{frame}[c] |
221 \begin{frame}[c] |
222 \frametitle{Graph Isomorphism} |
222 \frametitle{Graph Isomorphism} |
223 |
223 \mbox{}\\[-20mm]\mbox{} |
224 \begin{center} |
224 |
225 \begin{tabular}{l@{\hspace{10mm}}r} |
225 \begin{center} |
226 \includegraphics[scale=0.8]{../pics/graphs.png}\\ |
226 \begin{tabular}{@{}ccc} |
|
227 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} & |
|
228 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}& |
|
229 |
|
230 \footnotesize |
|
231 \begin{tabular}{rl} |
|
232 Graph A & Graph B\\ |
|
233 0 & 0\\ |
|
234 1 & 3\\ |
|
235 2 & 1\\ |
|
236 3 & 2\\ |
|
237 4 & 5\\ |
|
238 5 & 4\\ |
|
239 \end{tabular} |
227 \end{tabular} |
240 \end{tabular} |
228 \end{center} |
241 \end{center} |
229 |
242 |
230 Finding an isomorphism between two graphs is an NP-complete |
243 Finding an isomorphism between two graphs is an NP-complete |
231 problem. |
244 problem. |
232 |
245 |
233 \end{frame} |
246 \end{frame} |
234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
248 |
|
249 |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 \begin{frame}[c] |
|
252 \begin{center} |
|
253 \includegraphics[scale=0.8]{../pics/graphs.png} |
|
254 \end{center} |
|
255 |
|
256 Creating a new isomorphic graph is easy; finding an |
|
257 isomorphism is hard; checking an isomorphism is easy again |
|
258 |
|
259 \end{frame} |
|
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
261 |
|
262 |
235 |
263 |
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
237 \begin{frame}[c] |
265 \begin{frame}[c] |
238 \frametitle{\Large Graph Isomorphism Protocol} |
266 \frametitle{\Large Graph Isomorphism Protocol} |
239 |
267 |
471 \begin{frame}[c] |
499 \begin{frame}[c] |
472 \frametitle{Take Home Points} |
500 \frametitle{Take Home Points} |
473 |
501 |
474 \begin{itemize} |
502 \begin{itemize} |
475 \item this is pretty old work (in theory); seems |
503 \item this is pretty old work (in theory); seems |
476 little used in practice (surprising) |
504 little used in practice (surprising)\bigskip |
477 |
505 |
478 \item for use in privacy the incentives are |
506 \item for use in privacy the incentives are |
479 not yet right |
507 not yet right\bigskip |
480 |
508 |
481 \item digital cash (Bitcoins are not yet good enough) |
509 \item digital cash (Bitcoins are not yet good enough) |
482 |
510 |
483 \end{itemize} |
511 \end{itemize} |
484 |
512 |