02. Parametric complexity

Summary

Section numbers refer to Mulmuley’s paper. Here is a write-up of some of the stuff below.

• §2.2. We show that we can not get the $n$-th bit of a given number in $\mathrm{KC}(2^{o(\sqrt n)}, o(\sqrt n))$.
• Intuitively, this is because parity is a “high-degree” problem.
• Can we show that MaxFlow is also a high-degree problem, in some sense?
• §3.1. Parametric complexity of convex optimization problems.
• Linear parametrizations: each numerical parameter is a linear function of a parameter $\lambda$ in some interval.
• Complexity of a given linear parametrization = number of different slopes in the graph.
• Parametric complexity = complexity of most complex linear parametrization.
• In the next class we will see that problems with high parametric complexity are “high-degree” in some sense. The proof is similar to, but more sophisticated than, (§2.2).
• §3.2. Parametric complexity of max-flow.
• Via max-flow, min-cut theorem.
• Construction was started in class.
• Open problem. What is the parametric complexity of (weighted) perfect matching?