PaperlayerView exact revision on arXiv

Source-linked AI summary

Inapproximability of the independent set polynomial in the complex plane

Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic

arXiv:1711.00282v4cs.CCcs.DM

TL;DR

For complex activities, known approximation results did not settle whether the tree-occupation region ΛΔ captures the full approximability boundary. The paper proves hardness outside that region using reductions from approximation to exact independent-set counting. Approximation is NP-hard outside ΛΔ and #P-hard off the positive real axis, with a stronger positivity-decision result for sufficiently negative real activities.

  • Problem

    For complex λ, known FPTAS regions did not settle whether the tree-occupation convergence region ΛΔ captures the full approximability boundary.

    Source: §1 · p. 2

  • Method

    The proof shows that an approximation algorithm for Z_G(λ) can be converted into a polynomial-time algorithm for exactly counting independent sets.

    Source: §1 · p. 3

  • Results

    Outside ΛΔ, approximation is NP-hard; outside it and off the positive real axis it is #P-hard, while for λ < −λ* deciding whether Z_G(λ) > 0 is #P-hard.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The tree-derived region ΛΔ identifies a boundary beyond which approximation is NP-hard for graphs of maximum degree Δ.

    Source: §1 · pp. 2–3

    A proof lemma requires |z| < 1 and fails, for example, at z = i.

    Source: §7.2 · p. 44

Abstract

from arXiv · show

We study the complexity of approximating the independent set polynomial $Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. This problem is already well understood when $\lambda$ is real using connections to the $\Delta$-regular tree $T$. The key concept in that case is the "occupation ratio" of the tree $T$. This ratio is the contribution to $Z_T(\lambda)$ from independent sets containing the root of the tree, divided by $Z_T(\lambda)$ itself. If $\lambda$ is such that the occupation ratio converges to a limit, as the height of $T$ grows, then there is an FPTAS for approximating $Z_G(\lambda)$ on a graph $G$ with maximum degree $\Delta$. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where $\lambda$ is complex is more challenging. Peters and Regts identified the complex values of $\lambda$ for which the occupation ratio of the $\Delta$-regular tree converges. These values carve a cardioid-shaped region $\Lambda_\Delta$ in the complex plane. Motivated by the picture in the real case, they asked whether $\Lambda_\Delta$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$, the problem of approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$ is indeed NP-hard. In fact, when $\lambda$ is outside of $\Lambda_\Delta$ and is not a positive real number, we give the stronger result that approximating $Z_G(\lambda)$ is actually #P-hard. If $\lambda$ is a negative real number outside of $\Lambda_\Delta$, we show that it is #P-hard to even decide whether $Z_G(\lambda)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis -- specifically the study of iterative multivariate rational maps.

1 Introduction

The paper establishes hardness for approximating the independent set polynomial outside the tree-defined region ΛΔ and outlines a gadget-based proof using complex rational maps. It also records later developments within that region.

1 Introduction

  • For real activities, occupation-ratio convergence on the Δ-regular tree corresponds to the interval [−λ*, λc], while the complex case remains less understood.Peters and Regts identified the cardioid-shaped region ΛΔ where the tree occupation ratio converges and asked whether it marks the general complex approximability threshold.Source: §1 · p. 2
  • Outside ΛΔ, approximating Z_G(λ) on graphs of maximum degree at most Δ is NP-hard, and is #P-hard when λ is not a positive real number.For negative real λ < −λ*, deciding whether Z_G(λ) > 0 is #P-hard, resolving [8, Conjecture 5.1].Source: §1 · p. 3

1.1 Proof approach

  • The proof uses gadgets to implement target activities with exponentially small error, drawing on repelling fixed points and iterated rational maps.A multivariate Fibonacci-type construction supplies nearby points; contracting maps that cover a neighborhood then enable exponentially precise implementations.Source: §1.1 · p. 5

1.2 New Developments

  • Later work found a new zero-free region inside ΛΔ where the Patel–Regts algorithm gives an FPTAS, and also found zeros near its boundary.The cited developments are by Bencs and Csikvári [2], Rivera-Letelier, and Buys [4].Source: §1.2 · p. 5

2 Proof Outline

The proof outline reduces hardness to efficiently implementing target activities with bounded-degree bipartite graphs. It uses iterates of a complex rational map to generate values that yield those implementations.

2 Proof Outline

  • A graph’s partition function is split into contributions from independent sets that include or exclude a chosen vertex.These contributions define the ratio used to describe an implemented activity.Source: §2 · p. 6
  • The reductions rely on implementing arbitrary target activities with exponentially small accuracy using polynomial-time constructed bipartite graphs of maximum degree Δ.The implementation notion uses a degree-one terminal and the ratio of partition-function contributions for sets excluding versus including that terminal.Source: §2 · p. 6
  • For λ outside ΛΔ and the real axis, Proposition 6 supplies the activity-implementation result needed for the hardness reductions.The outline adapts the approach for negative rational activities outside ΛΔ.Source: §2 · p. 6
  • The multivariate map (x1, …, xd) ↦ 1/(1 + λx1⋯xd), with d = Δ−1, defines the operations used to generate values.Starting from 1, generated values correspond to implementable activities: generating x permits implementation of λx.Source: §2 · pp. 6–7
  • The outline studies the map’s univariate specialization f(x) = 1/(1 + λx^d) using complex rational-map iteration theory.The authors note that multivariate iteration is less understood and draw on established complex-dynamics tools.Source: §2 · p. 7

2.1 Iteration of complex rational maps

This section introduces complex rational-map dynamics and the Julia-set property used to expand neighborhoods under iteration. That property supports constructions involving values associated with the map.

2.1 Iteration of complex rational maps

  • The chordal metric extends distance to the Riemann sphere C ∪ {∞}, where the rational maps are considered.The metric remains bounded for all pairs of points on that sphere.Source: §2.1 · p. 7
  • The Julia set consists of points where the iterates are not equicontinuous, while the Fatou set consists of points where they are.The definitions measure sensitivity of orbits to small perturbations of their starting points.Source: §2.1 · p. 7
  • For a Julia-set point, iterating any neighborhood covers the sphere except possibly the rational map’s exceptional set.The section also notes that repelling fixpoints belong to the Julia set; the exceptional set has at most two points and is empty in the paper’s applications.Source: §2.1 · pp. 7–8
  • Peters and Regts used a version of this neighborhood-iteration result to find trees and activities near the boundary of ΛΔ with zero partition function.The paper applies the theorem as a tool for its hardness results outside ΛΔ.Source: §2.1 · p. 8

2.2 A characterisation of the cardioid

The section characterizes the fixed points of f(z) = 1/(1 + λz^(Δ−1)) according to whether λ lies inside, on, or outside the cardioid boundary.

2.2 A characterisation of the cardioid

  • For λ inside ΛΔ but not on its boundary, f has one attracting fixed point and all other fixed points are repelling.The map’s fixed points are the object of the section’s characterization.Source: §2.2 · p. 8
  • For λ on the boundary ϑΛΔ, f has one neutral fixed point and all other fixed points are repelling.The boundary curve is identified as the boundary of ΛΔ.Source: §2.2 · p. 8
  • For λ outside ΛΔ, every fixed point of f is repelling.This case supplies the fixed-point condition used in the following section’s construction.Source: §2.2 · p. 8

2.3 Applying the theory

Outside ΛΔ, all fixed points of the map are repelling, so neighborhood iteration can generate arbitrary complex values. The section turns local activity implementations near a fixed point into implementations of general target activities.

2.3 Applying the theory

  • For nonreal λ outside ΛΔ, all fixed points are repelling, and iterating a neighborhood of one can reach any complex value.The argument combines the fixed-point characterization with the Julia-set neighborhood property.Source: §2.3 · p. 8
  • Near λω, where ω is the smallest-norm fixed point, a polynomial-time algorithm implements target activities on bipartite graphs of maximum degree Δ.Proposition 10 gives this local implementation for rational complex targets and accuracy ϵ.Source: §2.3 · p. 8
  • The construction reaches a neighborhood of a pole, then uses the map recurrence to implement large-norm activities and extends to small and moderate norms.A Lipschitz bound before reaching the pole limits accuracy distortion to a constant factor.Source: §2.3 · p. 9

2.4 Chasing repelling fixpoints

A multivariate recurrence reaches the smallest-norm fixpoint of the univariate map even though that fixpoint is repelling. A Fibonacci-type tree construction realizes the recurrence, and a linear recurrence helps prove convergence.

2.4 Chasing repelling fixpoints

  • The sequence is well-defined, converges to the smallest-norm fixpoint ω, and differs from ω for infinitely many indices.This supplies points arbitrarily close to ω despite its repelling behavior in the complex nonreal setting described in the section.Source: §2.4 · p. 9
  • A Fibonacci-type tree realizes each recurrence step by combining the values generated by its d preceding trees.Tree T_k has a root whose child subtrees are T_{k−d}, …, T_{k−1}.Source: §2.4 · p. 9
  • Writing x_k = R_k/R_{k+1} reduces the recurrence analysis to R_{k+1} = R_k + λR_{k−d}, with R_0 through R_d equal to 1.The proof interprets R_k as an independent set polynomial of a claw-free graph and uses Chudnovsky and Seymour to show R_k is nonzero.Source: §2.4 · pp. 9–10

2.5 Exponential precision via contracting maps that cover

To generate any target near a repelling fixpoint with exponentially small error, the proof uses multiple contracting maps whose images cover a neighborhood. A path construction then realizes the resulting iterated map as a graph activity.

2.5 Exponential precision via contracting maps that cover

  • The maps arise by fixing d−1 inputs of the multivariate map, which makes the remaining one-variable map contracting near ω.Here d = Δ−1, and z satisfies 0 < |z| < 1 and z ∉ R.Source: §2.5 · p. 10
  • A family of contracting maps is used so that their images cover U, keeping a suitable preimage inside U at each backward step.A single map may eventually send the preimage outside U; the family addresses this while relaxing the required accuracy by a factor tied to |z| < 1.Source: §2.5 · p. 10
  • The covering condition lets the algorithm approximate any target x in U by an iterated sequence of maps, with error at most ϵ.The output is a point x̂ and indices i_1, …, i_k selecting the maps; the passage states the bound |x̂ − x| ≤ ϵ.Source: §2.5 · p. 10
  • Given the sequence of map indices, a path of length k implements the corresponding activity λx̂.The construction accounts for an extra factor of λ.Source: §2.5 · p. 10

2.6 Constructing the maps

The maps are constructed by populating a small ball around the fixpoint with generated activities. Polynomial values at z provide a finite covering, yielding the relaxed implementation guarantee of Lemma 14.

2.6 Constructing the maps

  • An ϵ-covering places a point within distance ϵ of every point in the set, while a dense set is an ϵ-covering for every ϵ > 0.The proof uses this notion to cover a slightly enlarged ball and choose an input that keeps the preimage in U.Source: §2.6 · p. 11
  • For every ϵ, κ > 0, some radius ρ < κ lets each activity λ′ in B(λω, ρ) be implemented by a degree-Δ tree with accuracy ρϵ.Lemma 14 assumes Δ ≥ 3 and λ ∈ C\R.Source: §2.6 · p. 11
  • The operation (a_1, …, a_d) ↦ z(a_1 + ··· + a_d) builds displacements from ω through a finite sequence of operations.The resulting generated points have form ω + z^N p(z), where p has nonnegative integer coefficients; choosing δ = z^N scales a finite covering into the ball around ω.Source: §2.6 · pp. 11–12
  • Polynomials with nonnegative integer coefficients evaluated at z are dense in C when z ∉ R and 0 < |z| < 1.A finite set of these values can form an ϵ/2-covering of the unit disk.Source: §2.6 · p. 12

2.7 Fitting the pieces together and proof for the real case

The complex-case proof builds from points near a repelling fixpoint to exponential precision and then propagates that precision across the complex plane. For negative real activities, a separate proposition gives polynomial-time bipartite graph implementations.

2.7 Fitting the pieces together and proof for the real case

  • In the complex case, the proof progresses from points close to a repelling fixpoint to a moderately dense neighborhood, exponential precision, and then precision across the plane.These stages correspond to Lemmas 11, 14, and 12, followed by Proposition 10.Source: §2.7 · p. 12
  • For λ < −λ*, an algorithm outputs in polynomial time a degree-Δ bipartite graph with terminal v implementing λ′ to accuracy ϵ.The proposition assumes Δ ≥ 3 and λ ∈ Q.Source: §2.7 · p. 12
  • The cited real-activity result guarantees implementations for every real λ′, but does not bound graph size in terms of accuracy.The proof therefore also uses contracting maps that cover to obtain exponential precision.Source: §2.7 · p. 12

2.8 Dependencies between Lemmas

Table 1 helps track dependencies among the paper’s results. Theorems 1 and 2 follow directly from Theorems 35 and 37, respectively.

2.8 Dependencies between Lemmas

  • Table 1 records dependencies among the paper’s theorems, propositions, and lemmas.The authors provide it to help readers keep track of those dependencies.Source: §2.8 · p. 12, Table 1 · p. 13
  • Theorem 1 follows directly from Theorem 35.Source: §2.8 · p. 12
  • Theorem 2 follows directly from Theorem 37.Source: §2.8 · p. 12

3 Preliminaries

The preliminaries define a way to implement vertex activities with bounded-degree bipartite graphs and establish tools for polynomial-time root approximation, algebraic lower bounds, and rational-map exceptional sets.

3.1 Implementing activities

  • An activity is implemented when a bipartite graph of maximum degree Δ realizes the target activity; attaching such graphs converts non-uniform activities to a uniform model.The construction preserves bipartiteness and keeps the degree of vertices already at activity λ unchanged, while other vertices gain one degree.Source: §3.1 · pp. 13–14

3.2 Finding roots of polynomials

  • Roots of polynomials with complex rational coefficients can be approximated to accuracy ε in time polynomial in the degree, coefficient sizes, and ε’s size.The size measure for a complex rational number is defined from the integer numerators and denominators of its real and imaginary parts.Source: §3.2 · p. 14

3.3 Lower bounds on polynomials evaluated at algebraic numbers

  • Liouville’s inequality gives an effective lower bound on |P(y)| when an integer polynomial P does not vanish at an algebraic number y.The bound depends on the polynomial’s degree and height and on y; the height is the largest absolute coefficient.Source: §3.3 · p. 14

3.4 Characterising the exceptional set

  • A rational map of degree at least two has at most two exceptional points; one exceptional point is a fixed point of multiplier zero, and two are fixed points of its square with multiplier zero.Source: §3.4 · p. 15

4 Proving the properties of the cardioid

The section characterizes the fixed points of the map f(z) = 1/(1 + λz^(Δ−1)) according to λ’s position relative to ΛΔ. It also proves that nonreal λ gives fixed points with pairwise distinct norms.

Cardioid parameterization

  • For λ in ΛΔ, there is a unique z with |z| ≤ 1/(Δ−1) satisfying λ = z(1−z)^Δ.The proof establishes uniqueness by ruling out distinct x and y in that disk with the same image.Source: §4 · p. 15

Fixed-point classification

  • Outside ΛΔ, all fixed points are repelling; inside ΛΔ but off its boundary, there is one attractive fixed point and all others are repelling.On the boundary region ϑΛΔ, there is one neutral fixed point and all others are repelling.Source: §4 · p. 16

Distinct fixed-point norms

  • For nonreal λ, the fixed points of f have pairwise distinct norms.The proof shows that two roots of the reparameterized equation with equal norm would be conjugates and would force λ to be real.Source: §4 · p. 17

5 Impementing activities with exponential precision

This section develops implementations of activities using contracting rational maps, iterates, and path or tree constructions. It establishes real- and complex-case results for constructing bounded-degree bipartite graphs or gadgets that implement target activities to specified accuracy.

5.1 Contracting maps that cover yield exponential precision

  • Contracting maps enable polynomial-time approximation of a target by a composition of maps, with the recursive procedure using O(size(ϵ)) calls.The procedure also returns the sequence of maps used in the composition.Source: §5.1 · pp. 18–19
  • A path construction encodes successive map applications and computes the associated partition-function quantities.The path construction is paired with the approximation lemmas for the real and complex cases.Source: §5.1 · pp. 19–20

5.2 Proof of Proposition 15 (real case)

  • For λ′1 and λ′2 within 10^-10 of −1/4 and −6/25, their maps are contracting on [7/4, 11/6] and their images cover that interval.This real-case lemma supplies maps used with the contraction argument to obtain exponentially accurate implementations.Source: §5.2 · p. 20
  • For Δ≥3 and rational λ < -λ*, a polynomial-time algorithm outputs a bipartite graph of maximum degree at most Δ implementing any rational target activity λ′ to accuracy ϵ.The graph has a terminal vertex, and the running time is polynomial in size(λ′, ϵ).Source: §5.2 · p. 20

5.3 Proof of Proposition 6 (complex case)

  • For nonreal λ outside ΛΔ, Lemma 29 selects an iterate and pole so that the iterate is Lipschitz on a ball around the smallest-norm fixed point.For x1, x2 in B(ω, r), the stated bound is |f^N(x1) − f^N(x2)| ≤ L|x1 − x2|.Source: §5.3 · p. 24
  • For Δ≥3 and λ∈CQ outside ΛΔ∪R, the algorithm implements any input λ′∈CQ to rational accuracy ϵ>0 in time polynomial in size(λ′, ϵ).It outputs a bipartite graph of maximum degree at most Δ with a terminal implementing λ′.Source: §5.3 · p. 26
  • The construction divides targets by magnitude and uses iterates of f(x)=1/(1+λx^d), with d=Δ−1, and tree gadgets to implement the resulting activity.For large |λ′|, it chooses w so λ/(1+λ(f^N(w))^d) approximates λ′, then uses a tree construction; iterates are kept away from poles to ensure the construction is valid.Source: §5.3 · pp. 26–30
  • For small nonzero |λ′|, the proof transforms the target to a sufficiently large activity and applies the large-magnitude case.The algorithm also has an intermediate-magnitude case, whose details are stated to be almost identical to those for the real case.Source: §5.3 · p. 30
  • Adding a leaf adjacent to the terminal of G produces a bipartite graph of maximum degree Δ that implements λ′ with accuracy ε.The construction follows the method of Case II of Proposition 15.Source: §5.3 · p. 30
  • When λ′ = 0, the proof instead implements a nonzero activity ε′′/2 with accuracy ε′′/2, choosing ε′′ below min{ε, |λ|/(M + 1)} and of polynomial size in ε.This handles the zero target using the preceding technique.Source: §5.3 · p. 30
  • For |λ|/(M + 1) < |λ′| < M, the proof implements λ′ with accuracy ε using a gadget for λ′^4 and one for the scaled activity λx∗.It bounds |x∗| by 1/(M + 1), implements λx∗ with precision ε′ in polynomial time, and combines the gadgets by identifying their terminals and adding a leaf.Source: §5.3 · pp. 30–31
  • The three cases complete the algorithm and the proof of Proposition 6.Source: §5.3 · p. 31

6 #P-hardness

This section establishes #P-hardness for multivariate independent-set problems and, for rational complex λ outside Λ_Δ ∪ ℝ≥0, for single-activity bipartite problems. It uses equality gadgets to reduce degrees, restricts to bipartite graphs, and reduces multivariate problems to single-activity cases.

6 #P-hardness

  • The multivariate problems allow vertex activities from L(λ), with vertices whose activity differs from λ restricted to degree at most 2.The section introduces these multivariate problems as a step toward proving the paper’s main theorems.Source: §6 · p. 31

6.1 Reducing the degree using equality gadgets

  • Equality gadgets enforce matching endpoint inclusion states in nonzero-weight independent sets and replace selected vertices with degree-at-most-3 subgraphs while preserving outside vertices’ degrees and activities.The replacement uses at most 8|V|^2 new vertices; non-λ replacement vertices have degree at most 2.Source: §6.1 · pp. 32–34

6.2 #P-hardness of the multivariate problem

  • For ∆≥3 and rational complex λ outside Λ_∆ ∪ R_≥0, both multivariate norm approximation with K=1.02 and argument approximation with ρ=9π/24 are #P-hard.The result applies to #MVHardCoreNorm and #MVHardCoreArg, respectively.Source: §6.2 · p. 34
  • Binary search recovers the exact independent-set count using norm estimates or argument-based sign tests to shrink the search interval.The norm method shrinks the interval to 7/8 of its length per step; the argument method shrinks it to 5/6.Source: §6.2 · p. 36

6.3 Restricting to bipartite graphs

  • The reductions to bipartite inputs enlarge the allowed activity set to L_bip(λ)={λ, −λ−1, −1, 1, −2, −1/4}.The section defines bipartite norm and argument variants with maximum degree at most ∆ and non-λ vertices restricted to degree at most 2.Source: §6.3 · pp. 36–37
  • For Δ≥3 and rational complex λ outside Λ_Δ ∪ R≥0, both #MVBipHardCoreNorm(λ, Δ, 1.02) and #MVBipHardCoreArg(λ, Δ, 9π/24) are #P-hard.The hardness holds on bipartite graphs with activities from L_bip(λ).Source: §6.3 · p. 38
  • For activities from L_bip(λ), the partition function is either zero or has magnitude greater than C_λ^-n for some rational C_λ > 1.This lower bound applies to any n-vertex graph and supports the subsequent approximation-preserving reduction.Source: §6.3 · p. 38

6.4 Reduction from the multivariate problem to the single-activity problem

  • For Δ≥3 and rational complex λ outside Λ_Δ ∪ R≥0, polynomial-time Turing reductions map the multivariate bipartite norm and argument problems to single-activity versions.The respective tolerances are 1.02 to 1.01 for norm and 9π/24 to π/3 for argument.Source: §6.4 · p. 38
  • For an n-vertex bipartite G of maximum degree Δ with activities in L_bip(λ), replacing degree-at-most-2 vertices in U1,…,U5 by bipartite gadgets implementing their activities yields partition-function arguments differing by at most π/30.The constructed bipartite graph H has maximum degree at most Δ.Source: §6.4 · p. 39

7 Proof of Proposition 10

The proof develops tree-implementable activities via recursive hard-core programs, using recurrence-polynomial properties and polynomial-value density to approach a repelling fixpoint and extend a nearby point to an ε-covering. Local perturbation bounds and contracting maps then yield polynomial-time implementation of activities in a neighborhood of the scaled value λω.

7 Proof of Proposition 10

  • A hard-core program generating a_k can be realized by a tree of maximum degree at most Δ implementing activity λa_k.Near ω, the recurrence approximates an operation with error bounded by C_0 max_j |a_j|^2; straight-line programs use it to generate polynomial values up to powers of z.Source: §7 · pp. 40–41, §7.2 · p. 45

7.1 Getting close to a repelling fixpoint

  • The recurrence polynomials p_k have only real roots because they are independent set polynomials of claw-free graphs, whose roots are real by [5, Theorem 1.1].Source: §7.1 · pp. 41–42
  • The sequence defined by the recurrence is well-defined, converges to the smallest-norm fixpoint ω, and differs from ω for infinitely many indices.The convergence proof uses the recurrence for R_k and its characteristic roots; the non-equality claim follows by contradiction from the recurrence.Source: §7.1 · pp. 42–43
  • For nonreal λ and d ≥ 2, the smallest-norm fixpoint satisfies ω ∈ C\R and 0 < |ω − 1| < 1.Source: §7.1 · p. 43

7.2 Bootstrapping a point next to a fixpoint to an ϵ-covering

  • If z ∈ C\R and |z| < 1, values at z of polynomials with non-negative integer coefficients are dense in C.The proof handles rational and irrational arguments of z separately; the strict bound |z| < 1 is necessary, as z = i shows.Source: §7.2 · p. 44
  • For Δ≥3 and λ∈C_Q\R, every activity in a sufficiently small ball around λω can be implemented by a maximum-degree-Δ tree to the stated accuracy.For any ε, κ > 0, some ρ ∈ (0, κ) works for all λ′ ∈ B(λω, ρ), with implementation accuracy ρε.Source: §7.2 · pp. 46–47
  • The 7.2 induction converts a straight-line program into a hard-core program whose final value lies within rϵ of ω + u.The construction bounds the accumulated error inductively and uses the initial hard-core-program values to generate the resulting sequence.Source: §7.2 · pp. 47–48

7.3 Bootstraping ϵ-covering to arbitrary density

  • For λ ∈ C\R, local perturbations around the smallest-norm fixpoint have quadratic error in Lemma 47 and linear error in Lemma 48.The bounds apply when each perturbation has magnitude at most the corresponding positive threshold δ1 or δ2.Source: §7.3 · pp. 48–49
  • Starting from an ϵ-covering near ω, the proof constructs finitely many CQ activities whose maps are contracting near ω and whose bipartite graph gadgets support arbitrary nearby activity implementation.The construction combines local perturbation estimates with the covering and attaches the gadgets along a path to realize the target activity.Source: §7.3 · pp. 50, 51, 53
  • A polynomial-time algorithm implements any rational activity λ′ in a rational-radius neighborhood of λω to accuracy ε using a bipartite graph of maximum degree at most Δ.The algorithm also outputs the associated implementation values.Source: §7.3 · p. 52
Loading 1711.00282v4…