Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Complexity of Contextuality

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Deciding whether a prepare-measure experiment admits a noncontextual model of a given dimension $k$ costs at most $\mathrm{poly}(b,m,n)^{O(k^2)}$ and, under the Exponential Time Hypothesis, at least $(nm)^{\Omega(r)}$; the smallest such…

desk verdict Useful ENMF-based reduction and a credible size-gap example, but the complexity results hinge on an unproved same-author equivalence between contextuality and equirank factorization. read the letter →

arxiv 2506.09133 v1 pith:A4GOV4RI submitted 2025-06-10 quant-ph cs.CCcs.CG

Theodoros Yianni , Farid Shahandeh This is my paper
classification quant-phcs.CCcs.CG MSC 68Q1715A2352B1181P13
keywords generalizedcontextualityontologicalmodelsequiranknonnegativematrixfactorizationrankintermediatesimplexproblemCOPEcomputationalcomplexityonticsize
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Generalized contextuality marks the boundary between classical and nonclassical explanations of prepare-measure experiments. This paper takes the rank-separation criterion, which identifies a noncontextual ontological model with an equirank nonnegative matrix factorization (ENMF) of the COPE matrix, and turns it into a geometry problem: a noncontextual model of size $k$ exists exactly when a simplex can be sandwiched between two polytopes derived from the data. Using that translation, it proves that deciding existence for a specified $k$ costs at most $\mathrm{poly}(b,m,n)^{O(k^2)}$ time, and at least $(nm)^{\Omega(r)}$ under the Exponential Time Hypothesis, so computing the smallest noncontextual model is inefficient in general. It also exhibits an explicit $5\times5$ rank-3 COPE whose smallest noncontextual model needs five ontic states while its smallest unconstrained ontological model needs only four. The upshot is that a classical explanation is not only computationally costly to find; it is a genuinely different optimization target from merely explaining the statistics.

What carries the argument

The central object is the equirank nonnegative matrix factorization (ENMF), a factorization $C=RE$ with nonnegative $R,E$ and equal ranks $\operatorname{rank} R = \operatorname{rank} E = \operatorname{rank} C$; its smallest inner dimension is the equirank nonnegative rank (ENNR), and Corollary 2 equates ENNR with the minimum ontic size of a noncontextual model. The geometric engine is the nested-simplex reformulation (Lemmas 5 and 8): an ENMF of inner dimension $k$ exists exactly when a $(k-1)$-simplex fits between the inner polytope $B$ (the convex hull of epistemic states) and the outer polytope $A$ (the duality-defined set of logically possible states). Theorem 10 converts that sandwich condition into the nonnegative rank of an explicitly constructed slack matrix, and Lemma 6 supplies a polynomial-time linear-programming test for whether a candidate simplex's vertices can be mapped onto $B$ with the correct rank. The size-gap proof uses a pentagon-with-nested-quadrilateral obstruction: Lemma 14 shows no quadrilateral can meet the required five triangular regions, and a dual linear program certifies that the only candidate quadrilateral produces a positive objective, ruling out inner dimension four.

What would settle it

Compute the linear program of Lemma 6 for the matrices $G_2$ and $B_I$ defined in Proposition 15: if the optimum objective is exactly zero rather than about $0.146$, then $C_1$ would have an ENMF of inner dimension four, directly contradicting Proposition 15 and the claimed 5-versus-4 gap. Separately, any COPE matrix that admits a generalized-noncontextual ontological model yet violates Corollary 2's rank equality would falsify the rank-separation premise on which all bounds rest.

Watch

Extended reading notes

Core claim

The paper's central claim is that the equirank nonnegative matrix factorization (ENMF) problem captures generalized noncontextuality: a COPE matrix $C$ with a rank factorization $C=AB$ admits a noncontextual ontological model of inner dimension $k$ if and only if the constructed polytopes $B \subseteq A$ admit a nested $(k-1)$-simplex $G$ whose vertices can be mapped to the vertices of $B$ by a rank-$r$ nonnegative stochastic matrix. Theorem 10 turns this into a reduction to the nonnegative rank problem: one builds a larger nonnegative matrix whose nonnegative rank equals $k$ exactly when such a simplex exists. Composing that reduction with a known almost-optimal nonnegative-rank decision algorithm gives the upper bound $\mathrm{poly}(b,m,n)^{O(k^2)}$ for deciding noncontextual models of dimension $k$, while Corollary 3, assuming the Exponential Time Hypothesis, gives a lower bound of $(nm)^{\Omega(r)}$ for computing the size of the smallest such model. The paper also proves the two optimization problems are different by constructing a $5\times5$ rank-3 COPE whose equirank nonnegative rank is 5 while its nonnegative rank is 4, with explicit factorizations for both.

Load-bearing premise

The load-bearing premise is that a COPE admits a noncontextual ontological model if and only if it admits an equirank nonnegative matrix factorization, a criterion imported from an earlier paper by the same authors and not rederived here; if that equivalence fails for some operational theories, the complexity results describe a matrix property rather than generalized contextuality.

Editorial extensions

If this is right

  • For COPE matrices of fixed rank $r$, deciding whether any noncontextual model exists becomes polynomial in $m,n$ and bit length $b$; the hardness appears only when the model dimension $k$ is allowed to grow.
  • For general rank, the decision problem for dimension $k$ is solvable in $\mathrm{poly}(b,m,n)^{O(k^2)}$ time, so any exponential dependence on the model size is a genuine barrier, and computing the ENNR rather than deciding a single $k$ is inefficient in the worst case.
  • The explicit COPE $C_1$ shows $\operatorname{ENNR}(C_1)=5$ while $\operatorname{NNR}(C_1)=4$, so the smallest noncontextual model and the smallest ordinary ontological model differ, and results about one cannot be read as results about the other.
  • Because every ENNR is at most $O(r^2)$ for rank $r$, the gap between the minimal GPT dimension and the smallest noncontextual ontic dimension is polynomially bounded, limiting the advantage a noncontextually explainable protocol can display.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the rank-separation equivalence is correct, the reduction works in the opposite direction too: any faster algorithm for nonnegative rank would immediately give a faster search over noncontextual model sizes, and any hardness proof for ENNR would transfer to a hardness proof for NNR on the constructed matrices.
  • The size gap between ENNR and NNR suggests a quantitative measure: the difference $\operatorname{ENNR}(C)-\operatorname{NNR}(C)$, whenever a noncontextual model exists, could serve as a resource quantifier for contextuality in operational theories, with the paper's $C_1$ as a minimal witness.
  • The polynomial fixed-rank result depends on vertex enumeration of the outer polytope; for structured generalized probabilistic theories whose state spaces are simplexes or simple polytopes, one could exploit those structures to make ENNR computation practically efficient even when rank is not fixed.
  • A direct test of the paper's conjecture that contextuality detection is computationally hard would be to search for families of COPE matrices for which the constructed nonnegative-rank instances in Theorem 10 are themselves hard for the nonnegative rank problem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The manuscript studies the computational complexity of deciding whether a COPE matrix admits a noncontextual ontological model of a given inner dimension, and of computing the minimal such dimension. Using the rank-separation criterion imported from Ref. [9], the authors reformulate noncontextuality as equirank nonnegative matrix factorization (ENMF), provide a geometric reduction to an intermediate-simplex problem, and derive an upper bound poly(b,m,n)^{O(k^2)} via Moitra's NMF algorithm, together with an ETH-based lower bound (nm)^{Ω(r)} for computing the minimal ontic size. They also present a 5×5 rank-3 COPE matrix for which the minimum noncontextual ontic size is claimed to be 5 while the unconstrained minimum is 4.

Significance. If the central equivalence between noncontextuality and ENMF and the various proof steps were correct, this would be the first nontrivial complexity characterization of generalized contextuality in the COPE/GPT framework, and the explicit separation between NNR and ENNR would be a valuable contribution. The paper has concrete strengths: the example in Section V comes with closed-form factorizations, and Appendix D provides a dual LP certificate for the infeasibility claim. However, because the key equivalence is imported without proof and several load-bearing arguments are incomplete or logically inverted, the significance of the results is currently conditional on substantial revision.

major comments (4)
  1. [Section II.C] The equivalence between noncontextuality and ENMF is the central premise of the paper, but it is imported from Ref. [9] without proof. Specifically, Lemma 1 and Corollary 2 state that a COPE admits a noncontextual ontological model if and only if it admits an ENMF with rank C = rank R = rank E. All downstream results (Corollary 3, Corollary 13, and Proposition 15) are statements about ENMF existence. If the converse direction of Corollary 2 fails, the paper solves a matrix factorization problem rather than the contextuality problem advertised in the abstract. Because Ref. [9] is a same-author preprint and the present manuscript neither reproduces the proof nor verifies the equivalence independently, the reader cannot check that the results concern generalized contextuality. Please provide a self-contained proof of Corollary 2, or clearly state that the contextuality claims are conditional on the criterion from Ref. [9].
  2. [Theorem 10] The dimensions in the statement and proof of Theorem 10 are inconsistent. The theorem statement defines \bar C as an (m+k-r)×(n+2k-2r) matrix, while the proof constructs \bar C as the (m+2k-2r)×(n+k-r) slack matrix of \bar A_b \bar B_b; the proof also refers to \bar B_b as an (m+k-r)×k matrix and to \bar A_b as a k×(n+2k-2r) matrix. These mismatches make the reduction unverifiable as written. More importantly, the forward direction asserts without proof that the vertices of a nested simplex G between \bar B and \bar A can be 'rescaled along the h_i directions' to obtain a nested simplex between \bar B and \bar A_b. This rescaling is the key step that connects the bounded full-dimensional pair to the original unbounded non-full-dimensional pair, and no rigorous demonstration is given. A complete proof of this equivalence is needed before the reduction can support Corollary 13.
  3. [Corollary 7] The proof of Corollary 7 claims that choosing G = A is without loss of generality because 'Since A is the largest possible nested polytope, such a matrix exists if and only if an ENMF exists.' This monotonicity is not valid: the existence of a rank-r nonnegative matrix mapping the vertices of a smaller nested polytope G to the vertices of B does not imply the existence of such a matrix mapping the vertices of the larger polytope A to B. No extension argument is provided, so the polynomial-time decidability of ENMF existence for fixed rank r, which is stated in the Discussion as a proven result, is not established.
  4. [Section V (Proposition 15)] The proof excluding all quadrilateral nested polytopes is logically inverted. It states that for any larger polytope G2 containing G1, there is a nonnegative rank-3 matrix E2 = W E1 mapping the vertices of G2 to B_I, where W maps the vertices of G2 to G1. However, a nonnegative W mapping the vertices of a larger polytope into a smaller one cannot exist unless the larger polytope is contained in the smaller one. Lemma 14 gives G1 ⊆ G2, which is the opposite containment. Consequently, the LP infeasibility certificate for the specific hexagon G2 does not rule out maps from all quadrilaterals G1 contained in G2, and the claimed ENNR=5 / NNR=4 separation is not proved.
minor comments (5)
  1. [Corollary 3] The lower bound is written as (nm)^{O(r)} in both the statement and the proof; a lower bound should be (nm)^{Ω(r)}. This notational error should be corrected.
  2. [Lemma 6] The dimensions in the statement of Lemma 6 are inconsistent with the equation GE = B: G is given as k×r and B as m×r, whereas the surrounding usage (Lemma 5 and the proof of Lemma 6) requires G to be r×k and B to be r×n. Please align the conventions.
  3. [Lemma 5 proof] In the proof of Lemma 5, the text introduces R = AF and later writes 'Since R=AG is nonnegative' without defining G at that point; this notation should be harmonized to avoid confusion.
  4. [Algorithm (Section III)] Step 2 initializes 'EN ER=0', which appears to be a typo for 'ENNR=0', and step 12 misspells 'algorithm' as 'algroithm'.
  5. [Section IV] The identification of \bar G with T∘κ and \bar G^{-1} with T†∘ι is stated as a sketch without derivation; please provide the maps explicitly or label the connection as a conjecture. Also, the citation 'Ref. [19]' for a linear program deciding simplex embeddability points to Craven and Mond (1981), which appears unrelated; please verify the reference.

Circularity Check

1 steps flagged · score 4.0 of 10

The ENMF-to-NNR complexity derivation is genuine and externally anchored, but the semantic bridge from ENMF existence to noncontextuality is imported wholesale from a same-author preprint (Ref [9]); every contextuality claim reduces to that unverified self-citation, while the matrix-complexity content retains independent value.

  1. self citation load bearing [Section II.C (Lemma 1 and Corollary 2, from Ref [9]); inherited by Corollaries 3, 7, 13, the Section III algorithm, and Section V (Proposition 15).]
    "This leads us to the following lemma and corollary from Ref. [9]. ... Corollary 2. A noncontextual operational theory with a COPE C admits an NMF C=RE such that rankC=rankR=rankE. ... Furthermore, we define the equirank nonnegative rank (ENNR) of C as the smallest inner dimension where an ENMF is possible, which is equal to the smallest possible ontic size of a noncontextual model for C."

    Every central result—Corollary 3's ETH lower bound, Corollary 13's upper bound, the ENNR algorithm's output, and Proposition 15's 5-vs-4 'noncontextual ontic size' separation—is a statement about ENMF/ENNR, converted into a statement about noncontextuality only through Lemma 1 and Corollary 2 from Ref [9], a preprint by Shahandeh, Yianni, and Doosti (two are the present authors). The equivalence is neither rederived nor independently verified here; the critical direction (ENMF yields a noncontextual model) is asserted, not proved, and the box-world vignette only motivates it. If the rank-separation criterion failed, the bounds would survive as matrix results but not as contextuality results.

full rationale

No step in the mathematical core reduces to its own inputs by construction. Theorem 4, Lemma 5, and Lemma 8 (ENMF iff nested intermediate simplex) are proved in-paper; Theorem 10's reduction of ENMF-at-k to NNR-of-Cbar=k rests on Vavasis's theorem [22]; Corollary 13's upper bound composes this with Moitra's external algorithm [21]; Corollary 3's ETH lower bound is a correct transfer from the external NMF-decision hardness [25,26], using that for a rank-r matrix any NMF at inner dimension r is automatically equirank; Corollary 7's fixed-rank polynomiality uses Dyer's external vertex-enumeration result [29]. Section V's size separation is verified by explicit factorizations and a provable LP dual certificate (Appendix D gives a feasible Y* with objective (7-3*sqrt(5))/2 > 0), not by fitting. The sole load-bearing step not anchored to external, verified mathematics is the semantic bridge: noncontextuality iff ENMF (Lemma 1, Corollary 2, and the ENNR = smallest-noncontextual-size identification), imported from Ref [9], a preprint by the same authors. The paper never rederives the converse direction (ENMF yields a noncontextual model), which underlies the algorithm's output and the claimed 5-vs-4 'contextuality' gap; the box-world example motivates but does not prove it. Section IV's identification of Gbar with the simplex-embedding maps is presented as 'we can identify', i.e., an asserted sketch rather than a proof, but that section is comparative rather than load-bearing. Appendix B flags that Moitra's stable-NMF restriction 'could rule out the simplest ENMF'—a self-acknowledged limitation that belongs to correctness risk, not circularity. Overall, the central complexity derivations stand as results about ENMF, and their contextual reading rests on the imported same-author criterion: partial circularity via load-bearing self-citation, not by-construction equivalence.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The paper adds no fitted constants. Its central machinery is the ENMF concept, defined in the paper, and several imported results from the authors' own prior work plus standard complexity results. No new physical entities are postulated.

assumptions (5)
  • domain assumption Rank-separation criterion: a COPE admits a noncontextual ontological model iff it has an ENMF with rank C = rank R = rank E.
    Imported from Ref [9] by the same authors; not rederived. Underlies Lemmas 1, 5, 8 and the whole ENMF framework.
  • domain assumption Exponential Time Hypothesis (ETH) and the cited (nm)^Ω(r) lower bound for NMF decision.
    Used in Corollary 3 to translate the known NMF lower bound into (nm)^Ω(r) for computing the smallest noncontextual model.
  • standard math Moitra's algorithm runs in poly(b,m,n)^O(k^2) for the nonnegative rank decision problem.
    Accepted uncritically from Ref [21] and used in Corollary 13 and the algorithm.
  • standard math Vavasis equivalence between NMF/rank and the nested simplex problem.
    Theorem 10 and the reduction to NNR rely on Ref [22].
  • domain assumption Simplex embeddability characterization of noncontextuality.
    Section IV compares ENMF geometry to simplex embeddability from Refs [24,35], which include the present authors.
invented entities (1)
  • Equirank nonnegative matrix factorization (ENMF) and equirank nonnegative rank (ENNR)
    purpose: Formalize the existence and size of noncontextual ontological models as a matrix factorization problem.
    These are new mathematical definitions, not experimentally falsifiable entities; their connection to contextuality rests on the imported rank-separation criterion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of Contextuality." pith.science (2026). https://pith.science/paper/A4GOV4RI

@misc{pith2026250609133,
  author       = {Pith},
  title        = {Pith review of: Complexity of Contextuality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4GOV4RI}},
  note         = {Machine review of arXiv:2506.09133}
}
abstract

Generalized contextuality is a hallmark of nonclassical theories like quantum mechanics. Yet, three fundamental computational problems concerning its decidability and complexity remain open. First, determining the complexity of deciding if a theory admits a noncontextual ontological model; Second, determining the complexity of deciding if such a model is possible for a specific dimension $k$; Third, efficiently computing the smallest such model when it exists, given that finding the smallest ontological model is NP-hard. We address the second problem by presenting an algorithm derived from a geometric formulation and its reduction to the intermediate simplex problem in computational geometry. We find that the complexity of deciding the existence of a noncontextual ontological model of dimension $k$ is at least exponential in the dimension of the theory and at most exponential in $k$. This, in turn, implies that computing the smallest noncontextual ontological model is inefficient in general. Finally, we demonstrate the fundamental difference between finding the smallest noncontextual ontological model and the smallest ontological model using an explicit example wherein the respective minimum ontic sizes are five and four.

Figures

Figures reproduced from arXiv: 2506.09133 by the authors.

Figure 1
Figure 1. FIG. 1: 2D cross-section of the nested polytopes [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Inner (green) and outer (black) pentagons with [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Linear Algebra of Generalized Contextuality in All Prepare-Transform-Measure Scenarios

    quant-ph 2026-07 conditional novelty 6.0 of 10

    A rank-based linear-algebra criterion and decision algorithm certify generalized (non)contextuality in prepare-transform-measure scenarios with any number of sequential transformations.

Reference graph

Works this paper leans on

43 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [9]

    Quantum computational advantage im- plies contextuality,

    F. Shahandeh, “Quantum computational advantage im- plies contextuality,” (2021), arXiv:2112.00024 [quant- ph]

    arXiv 2021

  2. [1]

    Decide if the nonnegative rank and the rank ofC are equal

    work page

  3. [2]

    Here, the polytopesAandBare defined via a decomposition of the form given in Theorem 4

    Decide if a nested simplexGexists such thatB ⊆ G ⊆ A. Here, the polytopesAandBare defined via a decomposition of the form given in Theorem 4. We generalize this result to map the problem of deciding whether an ENMF of inner dimensionkofCexists to a nested simplex problem. Lemma 5.LetCbe a nonnegativem×nmatrix of rank rwhose columns each sum tol, and suppo...

    work page

  4. [3]

    R. W. Spekkens, Physical Review A71(2005)

    work page 2005

  5. [4]

    E. S. Simon Kochen, Indiana Univ. Math. J.17, 59 (1968)

    1968

  6. [5]

    N. D. Mermin, Reviews of Modern Physics65, 803 (1993)

    work page 1993

  7. [6]

    Schmid, H

    D. Schmid, H. Du, J. H. Selby, and M. F. Pusey, Phys. Rev. Lett.129, 120403 (2022)

    2022

  8. [7]

    Bermejo-Vega, N

    J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, Phys. Rev. Lett.119, 120505 (2017)

    2017

Show all 43 references
  1. [8]

    It follows from the fact thatI ⊂ Uthat there ex- ists a nested simplexGbetween ¯BI and ¯AU . Therefore, Lemma 8 can be used to show that there is a noncontex- tual model of ontic size five forC 1, given byC 1 =A 1B1, where, A1 =   5− √ 5 10 √ 5 5 5− √ 5 10 0 0 0 5− √ 5 ...

  2. [10]

    Gupta, D

    S. Gupta, D. Saha, Z.-P. Xu, A. Cabello, and A. S. Majumdar, Phys. Rev. Lett.130, 080802 (2023)

    2023

  3. [11]

    Schmid and R

    D. Schmid and R. W. Spekkens, Phys. Rev. X8, 011015 (2018)

    2018

  4. [12]

    Character- izing contextuality via rank separation with applications to cloning,

    F. Shahandeh, T. Yianni, and M. Doosti, “Character- izing contextuality via rank separation with applications to cloning,” (2024), arXiv:2406.19382 [quant-ph]

    2024

  5. [13]

    Lostaglio and G

    M. Lostaglio and G. Senno, Quantum4, 258 (2020)

    2020

  6. [14]

    Korzekwa and M

    K. Korzekwa and M. Lostaglio, Physical Review X11 (2021)

    2021

  7. [15]

    Havl ´ ıˇ cek and J

    V. Havl ´ ıˇ cek and J. Barrett, Physical Review Research2 (2020)

    2020

  8. [16]

    Montina, Physical Review A77(2008)

    A. Montina, Physical Review A77(2008)

    2008

  9. [17]

    Hardy, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics35, 267 (2004)

    L. Hardy, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics35, 267 (2004)

    2004

  10. [18]

    Shitov, Discrete & Computational Geometry61, 653 (2019)

    Y. Shitov, Discrete & Computational Geometry61, 653 (2019)

    2019

  11. [19]

    Gitton and M

    V. Gitton and M. P. Woods, Quantum6, 732 (2022)

    2022

  12. [20]

    E. F. Galv˜ ao and L. Hardy, Phys. Rev. Lett.90, 087902 (2003)

    2003

  13. [21]

    J. H. Selby, E. Wolfe, D. Schmid, A. B. Sainz, and V. P. Rossi, Physical Review Letters132(2024)

    2024

  14. [22]

    Craven and B

    B. Craven and B. Mond, Linear Algebra and its Appli- cations38, 73 (1981)

    1981

  15. [23]

    Noncontextuality inequal- ities for prepare-transform-measure scenarios,

    D. Schmid, R. D. Baldij˜ ao, J. H. Selby, A. B. Sainz, and R. W. Spekkens, “Noncontextuality inequal- ities for prepare-transform-measure scenarios,” (2024), arXiv:2407.09624 [quant-ph]

    2024 arXiv

  16. [24]

    Moitra, SIAM Journal on Computing45, 156 (2016)

    A. Moitra, SIAM Journal on Computing45, 156 (2016)

    2016

  17. [25]

    S. A. Vavasis, SIAM Journal on Optimization20, 1364 (2010)

    2010

  18. [26]

    The ontological identity of empir- ical indiscernibles: Leibniz’s methodological principle and its significance in the work of einstein,

    R. W. Spekkens, “The ontological identity of empir- ical indiscernibles: Leibniz’s methodological principle and its significance in the work of einstein,” (2019), arXiv:1909.04628 [physics.hist-ph]

    2019 arXiv

  19. [27]

    Shahandeh, PRX Quantum2, 010330 (2021)

    F. Shahandeh, PRX Quantum2, 010330 (2021)

    2021

  20. [28]

    Computing a nonnegative matrix factorization – provably,

    S. Arora, R. Ge, R. Kannan, and A. Moitra, “Computing a nonnegative matrix factorization – provably,” (2011), 14 arXiv:1111.0952 [cs.DS]

    2011 arXiv

  21. [29]

    Impagliazzo and R

    R. Impagliazzo and R. Paturi, Journal of Computer and System Sciences62, 367 (2001)

    2001

  22. [30]

    Aspvall and R

    B. Aspvall and R. E. Stone, Journal of Algorithms1, 1 (1980)

    1980

  23. [31]

    Renegar, Mathematical Programming40, 59 (1988)

    J. Renegar, Mathematical Programming40, 59 (1988)

    1988

  24. [32]

    M. E. Dyer, Mathematics of Operations Research8, 381 (1983)

    1983

  25. [33]

    Khachiyan, E

    L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, and V. Gurvich, Discrete & Computational Geometry39, 174 (2008)

    2008

  26. [34]

    Das and D

    G. Das and D. Joseph, in The 2nd Canadian Conference on Computational Geometry (1990) p. 296–301

    1990

  27. [35]

    A universality theorem for nested polytopes,

    M. G. Dobbins, A. Holmsen, and T. Miltzow, “A universality theorem for nested polytopes,” (2019), arXiv:1908.02213 [cs.CG]

    2019 arXiv

  28. [36]

    Storjohann, Computational Complexity24, 777 (2015)

    A. Storjohann, Computational Complexity24, 777 (2015)

    2015

  29. [37]

    Schmid, J

    D. Schmid, J. H. Selby, E. Wolfe, R. Kunjwal, and R. W. Spekkens, PRX Quantum2, 010331 (2021)

    2021

  30. [38]

    Schmid, J

    D. Schmid, J. H. Selby, E. Wolfe, R. Kunjwal, and R. W. Spekkens, PRX Quantum2(2021)

    2021

  31. [39]

    Tight bounds for the randomized and quantum communica- tion complexities of equality with small error,

    O. Lalonde, N. S. Mande, and R. de Wolf, “Tight bounds for the randomized and quantum communica- tion complexities of equality with small error,” (2023), arXiv:2107.11806 [quant-ph]

    2023 arXiv

  32. [40]

    Simple information processing tasks with unbounded quantum advantage,

    T. Heinosaari, O. Kerppo, L. Lepp¨ aj¨ arvi, and M. Pl´ avala, “Simple information processing tasks with unbounded quantum advantage,” (2024), arXiv:2308.07727 [quant-ph]. A. Explanation of Linear Programs Our task is to find a matrixDthat minimizes the sum of the moduli of ne...

    2024 arXiv

  33. [41]

    For each columnC :i, the support ofE :i is the lexicographically first admissible subset (of columns ofR) for C:i

  34. [42]

    Now, we will prove that restricting search of factorizations to stable NMFs prevents the algorithm from finding the ENNR in general

    For each rowC j,:, the support ofR j,: is the lexicographically first admissible subset (of rows ofE) forC j,:. Now, we will prove that restricting search of factorizations to stable NMFs prevents the algorithm from finding the ENNR in general. Lemma 17.Not every nonnegative m...

    1919

  35. [43]

    The dual objective value ofY ∗ can be calculated as 1 2 7−3 √ 5 ≈0.145898

    1 3− √ 5 0 0   ⊤ .(D.6) By plugging in{a 1, a2, a3},{b 1, b2, b3}, ¯E2 andY ∗ into the constrains of the dual program, it can be shown thatY ∗ is in the feasible region. The dual objective value ofY ∗ can be calculated as 1 2 7−3 √ 5 ≈0.145898. E. Explicit Models A nonc...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.