Arvind gave a talk about linear programs, LP duality, and how to solve LP’s using interior point methods.
If time permits, I may also talk about a faster
(\tilde{O}(n^omega) 👀) version of IPMs.
(My talk was somewhat based on this paper:
https://arxiv.org/abs/2108.04734).
Oh btw one can use LP duality to prove max flow = min cut over the integers.
But you need to utilize additional properties
(one of them is that A is totally unimodular
https://theory.stanford.edu/~jvondrak/MATH233B-2017/lec3.pdf).
Previous: Formal Security in Cryptography
Today Neil talked about a variety of (symmetric) cryptography topics and formal security models for them.
continue reading ❯