**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 .
- Intuitively, this is because parity is a “high-degree” problem
*.* - Can we show that MaxFlow is also a high-degree problem, in some sense?

- Intuitively, this is because parity is a “high-degree” problem
- §3.1. Parametric complexity of convex optimization problems.
- Linear parametrizations: each numerical parameter is a linear function of a parameter 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?