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 .
  • 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 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?

Advertisement