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?
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s