Pith. sign in

REVIEW 1 major objections 5 minor 34 references

Quasirandom quantum channels

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For irreducibly covariant quantum channels, spectral expansion is bounded by $2\pi^2$ times uniformity, making the two notions equivalent.

desk verdict A genuine quantum analog of the Chung-Graham-Wilson/Conlon-Zhao equivalence with clean proofs and optimal constants; the main theorem is solid and worth refereeing. read the letter →

arxiv 1908.06310 v3 pith:SQA72DMA submitted 2019-08-17 quant-ph math.CO

Tom Bannink , Jop Briët , Farrokh Labib , Hans Maassen This is my paper · ORCID
classification quant-phmath.CO MSC 81P45
keywords quasirandomquantumchannelsspectralexpansionuniformityGrothendieckinequalityirreduciblycovariantexpandercutnormvertex-transitivegraph
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

The paper lifts the classical graph-theoretic phenomenon of quasirandomness into quantum information. In graphs, spectral expansion (fast mixing of random walks) and uniformity (edge counts resembling random graphs) are equivalent for dense and vertex-transitive graphs. The paper defines quantum analogues: the expansion parameter $\lambda(\Phi)$ measures how far a channel is from the completely depolarizing channel in the Hilbert-Schmidt norm, and the uniformity parameter $\epsilon(\Phi)$ measures the same distance only on pairs of projections. Its main result, a converse quantum expander mixing lemma, states that for an irreducibly covariant channel $\lambda(\Phi) \leq 2\pi^2 \epsilon(\Phi)$, so the two notions are equivalent in this symmetric setting. The paper also proves that each step's constant is optimal and that the symmetry assumption is necessary, via an embedded sparse graph counterexample.

What carries the argument

The load-bearing mechanism is irreducible covariance together with the exact averaging step it enables. A superoperator is irreducibly covariant when $\Phi(U(g) X U(g)^*) = V(g) \Phi(X) V(g)^*$ for some irreducible unitary representations $U,V$ of a compact group. The proof applies a factorization form of the non-commutative Grothendieck inequality: for every superoperator there exist density matrices $\rho_1, \rho_2, \sigma_1, \sigma_2$ such that $|\langle Y, \Phi(X) \rangle| \leq \|\Phi\|_{S_\infty \to S_1} (\mathrm{Tr}[\rho_1 X^* X] + \mathrm{Tr}[\rho_2 X X^*])^{1/2} (\mathrm{Tr}[\sigma_1 Y^* Y] + \mathrm{Tr}[\sigma_2 Y Y^*])^{1/2}$. Averaging over the group collapses the terms $X_g^* X_g$ and $X_g X_g^*$ to $\|X\|_{S_2}^2$ times the identity exactly when the representation is irreducible; this exact collapse is what produces the factor 2. A second, purely norm-theoretic ingredient is the comparison $\|\Phi\|_{S_\infty \to S_1} \leq \pi^2 \|\Phi\|_{\mathrm{cut}}$, whose constant is optimal.

What would settle it

An irreducibly covariant superoperator with $\lambda(\Phi) > 2\pi^2 \epsilon(\Phi)$ would refute Corollary 3.4; the concrete test is to evaluate the ratio $\lambda(\Phi')/\epsilon(\Phi')$ for the antisymmetric exterior-power family of Section 4.2 for growing $n$ and check whether it ever exceeds $2\pi^2$, which would also settle whether the combined constant is optimal.

Watch

Extended reading notes

Core claim

The central claim is that for irreducibly covariant superoperators, expansion and uniformity are equivalent up to a universal factor. If $\Phi$ is a completely positive trace-preserving map satisfying $\Phi(U(g) X U(g)^*) = V(g) \Phi(X) V(g)^*$ for irreducible unitary representations $U,V$ of a compact group, then $\lambda(\Phi) = \|\Phi - \Pi\|_{S_2 \to S_2}$ obeys $\lambda(\Phi) \leq 2\pi^2 \epsilon(\Phi)$, where $\epsilon(\Phi) = \|\Phi - \Pi\|_{\mathrm{cut}}$ is the largest deviation measured on pairs of projectors. Since $\epsilon(\Phi) \leq \lambda(\Phi)$ always holds, the two parameters are equivalent inside the class. The proof splits into two individually optimal bounds: the non-commutative Grothendieck inequality gives $\|\Phi\|_{S_\infty \to S_1} \leq \|\Phi\|_{S_2 \to S_2} \leq 2\|\Phi\|_{S_\infty \to S_1}$ under irreducible covariance, and a general cut-norm comparison gives $\|\Phi\|_{S_\infty \to S_1} \leq \pi^2 \|\Phi\|_{\mathrm{cut}}$. In the commutative case the same steps reproduce the sparse vertex-transitive graph theorem, with the complex Grothendieck constant replacing the factor 2.

Load-bearing premise

The proof needs the covariance group to act irreducibly, so that the group average of $X^*X$ or $XX^*$ is exactly the identity times the normalized squared Hilbert-Schmidt norm; if the symmetry is reducible, this exact collapse fails and the factor 2, hence the full inequality, is no longer guaranteed.

Editorial extensions

If this is right

  • An irreducibly covariant quantum channel that is $\epsilon$-uniform is automatically a $(2\pi^2 \epsilon)$-expander, so mixing and approximate 1-design properties follow from checking only projector pairs.
  • The graph-theoretic converse expander mixing lemma for vertex-transitive graphs becomes a special case: the embedding that sends a normalized adjacency matrix to a superoperator preserves both spectral and uniform parameters.
  • The symmetry assumption is essential: sparse regular graphs can be embedded to give quantum channels with $\epsilon = o(1)$ yet $\lambda = \Omega(1)$, so no converse holds for general channels.
  • For randomizing channels, the quantum analogue of dense graphs, the bounds yield $\lambda(\Phi) \leq O(\epsilon(\Phi)^{1/4})$, extending the classical dense-graph equivalence to this class.
  • The two constants in the proof are individually tight: an irreducibly covariant family approaches the factor 2 in the $S_\infty \to S_1$ to $S_2 \to S_2$ bound, and the factor $\pi^2$ in the cut-norm comparison is optimal; whether the combined constant $2\pi^2$ is optimal is left open.

Reading between the lines

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

  • If the combined factor $2\pi^2$ is also optimal, the single inequality would show that the non-commutative and commutative Grothendieck constants combine with no additional loss; a natural numerical check is to evaluate the antisymmetric exterior-power family of Section 4.2 for growing $n$ and track the ratio $\lambda(\Phi')/\epsilon(\Phi')$.
  • The proof suggests a general recipe: any symmetry whose invariant algebra is as small as possible should force expansion-uniformity equivalence, and approximate or finite symmetry analogues might relax the constant continuously.
  • Because superoperators correspond to bilinear forms in quantum XOR games and Bell-type inequalities, the equivalence may translate into a statement about covariant game values: the worst-case value over local settings is controlled by the maximum over projector pairs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. This paper introduces a quantum analog of graph uniformity for superoperators, defined as the maximum deviation of the channel from the completely depolarizing channel when evaluated on pairs of projectors. The main result is Corollary 3.4: for every irreducibly covariant superoperator Φ, the spectral expansion parameter λ(Φ) is bounded by 2π² times the uniformity parameter ε(Φ). The proof combines a factorization form of Haagerup's noncommutative Grothendieck inequality (Theorem 3.5), an averaging identity for irreducible representations (Lemma 3.6), and a cut-norm comparison (Lemma 2.2). The paper also embeds graphs into quantum channels in a way that preserves norms and vertex transitivity, gives an example of non-covariant channels for which uniformity does not imply expansion, proves an analogue for randomizing channels (Proposition 3.9), and analyzes optimality of the constants, including optimality of the factor 2 in Theorem 3.3 via a covariant version of the Haagerup–Itoh construction.

Significance. If the main theorem is correct, it establishes a clean noncommutative analogue of the Conlon–Zhao equivalence between spectral expansion and uniformity, and it introduces a natural uniformity parameter for quantum channels. The central derivation is short and checkable: Haagerup's inequality supplies density-matrix states, Lemma 3.6 collapses the group average to the normalized trace, and Lemma 2.2 converts the S∞→S1 norm to the cut norm. I verified that no hidden dimension factor enters in the averaging step, so the constant 2π² is exactly as claimed. The paper also gives explicit optimality constructions and is honest about the open problem of the optimal combined constant. The embedding results and the randomizing-channel proposition broaden the applicability of the framework.

major comments (1)
  1. [Section 4.1, Lemma 4.2] As written, the proof of Lemma 4.2 does not work in the stated complex setting. The sphere S^{2n-1} is defined as the unit sphere in C^{2n}, the functions f_i(x)=x_i are complex-valued coordinate functions, and the average is over U(2n). For Haar measure on U(2n), the integral of U_{ka}U_{kb} is zero for all a,b, so the displayed identity (1/(2n))Σ_i ⟨f_i,B(f_i)⟩ = ‖A‖_G cannot hold; the subsequent bound also implicitly replaces Σ_i x_i^2 by Σ_i |x_i|^2. The construction appears to require the real unit sphere in R^{2n}, the orthogonal group, and a preliminary realification of the complex matrix A representing the complex Grothendieck norm. Please correct the statement and proof of Lemma 4.2 and check that Theorem 4.1's claimed optimality of π² K_G^C follows after this correction.
minor comments (5)
  1. [Section 4.1, definition of S^{m-1}] The definition of S^{m-1} as the unit sphere in C^m is inconsistent with calling it (m−1)-dimensional; the unit sphere in C^m has real dimension 2m−1. Please clarify whether the real or complex sphere is intended.
  2. [Section 2 and Section 3.1] The inner products for vectors and functions are written without complex conjugation (e.g., ⟨y,x⟩=E_i y_i x_i and Eq. (5)), while the matrix inner product uses Y^*X. This is confusing for complex-valued functions; please state the convention explicitly, preferably using conj(y_i)x_i everywhere.
  3. [Theorem 3.3, first line of proof] The equality |⟨Y,Φ(X)⟩| = E_g |⟨Y_g,Φ(X_g)⟩| is correct because ⟨Y_g,Φ(X_g)⟩ = ⟨Y,Φ(X)⟩ for every g, but the proof would be easier to follow if this observation were stated explicitly.
  4. [Lemma 2.2] The step 'the set of matrices X with ‖X‖_{S∞}≤1 is the convex hull of the set of unitary matrices' is a nontrivial fact (Russo–Dye); please add a citation or a parenthetical proof sketch.
  5. [Lemma 4.6] In the proof of Lemma 4.6, the notation ⟨c_i,c_j⟩ and the normalization of the trace should be defined in one place to avoid confusion, since the factor d^{-1} appears both in the inner product and in the Schatten norms.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the central norm equivalence is derived from external inequalities and standard group-theoretic facts.

full rationale

The main result Corollary 3.4 follows by combining Theorem 3.3 with Lemma 2.2. Theorem 3.3 is proved from Haagerup's non-commutative Grothendieck inequality (Theorem 3.5), which supplies density matrices rho1, rho2, sigma1, sigma2 for an arbitrary superoperator, and from Lemma 3.6, an independently proved Schur-lemma characterization of irreducible representations. Neither input is defined in terms of the expansion or uniformity parameters; the proof computes the norm comparison directly. Lemma 2.2 is self-contained: the inequality ||Phi||_cut <= ||Phi||_{S_infty->S_1} <= pi^2 ||Phi||_cut is established by convex-hull and unitary-diagonalization arguments, with only the optimality example imported from Conlon and Zhao. The uniformity parameter epsilon(Phi) is a definition (the cut norm of Phi - Pi), not a fitted quantity, and lambda(Phi) is an independent norm; Corollary 3.4 is an inequality between them, not an identity by construction. The only self-citation is [6] (Briet's thesis) in Lemma 4.2, where it is credited for an 'idea' in an optimality construction; the construction is reproduced in the paper and this lemma is not load-bearing for the central equivalence. The paper even states the optimality of the combined constant 2 pi^2 as open, further showing the result is not forced. No circular step is present.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The proofs rely on external theorems from functional analysis (Grothendieck and Haagerup inequalities), representation theory (Schur's lemma, Fulton-Harris irreducibility, Hodge duality), and classical probability/combinatorics (Russo-Dye, Birkhoff, Conlon-Zhao). No numerical parameters are fitted to data; the Grothendieck constants are universal constants of the problem, not free parameters. No new physical entities are introduced; the quantum uniformity parameter is a definition, not a postulated entity.

assumptions (8)
  • standard math Commutative Grothendieck inequality (factorization form, Theorem 3.2): for any linear A, |⟨g,Af⟩| ≤ K_C^G ‖A‖_{L∞→L1} (∫|f|²dλ)^{1/2} (∫|g|²dν)^{1/2}.
    External theorem used in Theorem 3.1 to bound the L2→L2 norm of transitive covariant maps by the L∞→L1 norm; standard result due to Grothendieck.
  • standard math Haagerup's non-commutative Grothendieck inequality (Theorem 3.5): factorization of bilinear forms on M_n by density matrices with constant 1.
    Core ingredient in Theorem 3.3 and hence Corollary 3.4; this is the quantum analog of the commutative Grothendieck inequality.
  • standard math Schur's lemma (Lemma 3.6): an irreducible unitary representation U satisfies E_g U_g X U_g* = (Tr X/n) Id for all X.
    Used in Theorem 3.3 to evaluate group averages of X_g*X_g and in Proposition 3.8 to establish irreducibility.
  • standard math Russo-Dye theorem: the unit ball of M_n(C) is the convex hull of the unitary group.
    Used in Lemma 2.2 to restrict the S∞→S1 supremum to unitary X,Y.
  • standard math Birkhoff's theorem: every doubly stochastic matrix is a convex combination of permutation matrices.
    Used in Proposition 3.8 to show covariance of the embedded channel implies graph automorphisms.
  • standard math Irreducibility of the action of SO(N,C) on (C^N)^{∧k} (Fulton-Harris) and unitary equivalence of R_k and R_{N-k} (Simon).
    Used in Proposition 4.5 to construct an irreducibly covariant superoperator from the Haagerup-Itoh example.
  • standard math Conlon-Zhao constructions: sparse regular graphs with o(1) uniformity and λ≥1/2; example showing π² optimal in the commutative cut norm.
    Used in Section 3.3 to embed a counterexample for non-covariant channels and in Lemma 2.2 to show π² is best possible.
  • standard math Haagerup-Itoh example: the non-commutative Grothendieck constant satisfies K'_G ≥ 2 (Lemma 4.6).
    Basis for Proposition 4.5 establishing optimality of the factor 2 in Theorem 3.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quasirandom quantum channels." pith.science (2026). https://pith.science/paper/SQA72DMA

@misc{pith2026190806310,
  author       = {Pith},
  title        = {Pith review of: Quasirandom quantum channels},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQA72DMA}},
  note         = {Machine review of arXiv:1908.06310}
}
read the original abstract

Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality. Here we generalize these results to the non-commutative, or `quantum', case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 20 canonical work pages

  1. [1]

    Small pseudo-random families of matrices: Derandomizing approximate quantum encryption

    Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages 249–260. Springer, 2004. DOI: 10.1007/978- 3-540-27821-4˙23. URL http://dx.doi.org/10.1007/978-3-540-27821-4_23 . Accepted in Quantum 2020...

    doi:10.1007/978- 2004

  2. [2]

    On almost randomizing channels with a short Kraus decomposition

    Guillaume Aubrun. On almost randomizing channels with a short Kraus decomposition. Comm. Math. Phys. , 288(3):1103–1116, 2009. ISSN 0010-3616. DOI: 10.1007/s00220-008- 0695-y. URL https://doi.org/10.1007/s00220-008-0695-y

    work page doi:10.1007/s00220-008- 2009

  3. [3]

    Quantum expanders: Motivation and construction

    Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma. Quantum expanders: Motivation and construction. Theory of Computing , 6(1):47–79, 2010. DOI: 10.4086/toc.2010.v006a003. URL https://doi.org/10.4086/toc.2010.v006a003

    doi:10.4086/toc.2010.v006a003 2010

  4. [4]

    Hermitian matrices and graphs: singular val- ues and discrepancy

    B´ ela Bollob´ as and Vladimir Nikiforov. Hermitian matrices and graphs: singular val- ues and discrepancy. Discrete Math. , 285(1-3):17–32, 2004. ISSN 0012-365X. DOI: 10.1016/j.disc.2004.05.006. URL https://doi.org/10.1016/j.disc.2004.05.006

    work page doi:10.1016/j.disc.2004.05.006 2004

  5. [5]

    Braverman, K

    M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck con- stant is strictly smaller than Krivine’s bound. Forum Math. Pi , 1:453–462, 2013. DOI: 10.1017/fmp.2013.4. URL http://dx.doi.org/10.1017/fmp.2013.4. Preliminary version in FOCS’11. arXiv: 1103.6161

    arXiv 2013

  6. [6]

    PhD thesis, Institute for Logic, Language and Computation, 2011

    Jop Bri¨ et.Grothendieck inequalities, nonlocal games and optimization . PhD thesis, Institute for Logic, Language and Computation, 2011

    work page 2011

  7. [7]

    Sparse quasi-random graphs

    Fan Chung and Ronald Graham. Sparse quasi-random graphs. Combinatorica, 22(2):217– 244, 2002. ISSN 0209-9683. DOI: 10.1007/s004930200010. URL https://doi.org/10.1007/ s004930200010. Special issue: Paul Erd˝ os and his mathematics

    work page doi:10.1007/s004930200010 2002

  8. [8]

    Fan R. K. Chung, Ronald L. Graham, and Richard M. Wilson. Quasi-random graphs. Combi- natorica, 9(4):345–362, 1989. DOI: 10.1007/BF02125347. URL https://doi.org/10.1007/ BF02125347

    doi:10.1007/bf02125347 1989

Show all 34 references
  1. [9]

    Quasirandom Cayley graphs

    David Conlon and Yufei Zhao. Quasirandom Cayley graphs. Discrete Anal., pages Paper No. 6, 14, 2017. ISSN 2397-3129. DOI: 10.19086/da.1294. URL http://dx.doi.org/10.19086/ da.1294

    2017 doi

  2. [10]

    Rank-one quantum games

    Tom Cooney, Marius Junge, Carlos Palazuelos, and David P´ erez-Garc´ ıa. Rank-one quantum games. computational complexity, 24(1):133–196, 2015. DOI: 10.1007/s00037-014-0096-x. URL http://dx.doi.org/10.1007/s00037-014-0096-x

    2015 doi

  3. [11]

    A. Davie. Lower bound for KG. Unpublished, 1984

    1984

  4. [12]

    Representation theory: a first course , volume 129

    William Fulton and Joe Harris. Representation theory: a first course , volume 129. Springer Science & Business Media, 2013. DOI: 10.1007/978-1-4612-0979-9. URL http://dx.doi. org/10.1007/978-1-4612-0979-9

    2013 doi

  5. [13]

    Grothendieck

    A. Grothendieck. R´ esum´ e de la th´ eorie m´ etrique des produits tensoriels topologiques.Bol. Soc. Mat. S˜ ao Paulo, 8:1–79, 1953

    1953

  6. [14]

    The Grothendieck inequality for bilinear forms on C∗-algebras

    Uffe Haagerup. The Grothendieck inequality for bilinear forms on C∗-algebras. Adv. in Math., 56(2):93–116, 1985. ISSN 0001-8708. DOI: 10.1016/0001-8708(85)90026-X. URL https://doi.org/10.1016/0001-8708(85)90026-X

    1985 doi

  7. [15]

    A new upper bound for the complex Grothendieck constant

    Uffe Haagerup. A new upper bound for the complex Grothendieck constant. Israel J. Math. , 60(2):199–224, 1987. ISSN 0021-2172. DOI: 10.1007/BF02790792. URL http://dx.doi.org/ 10.1007/BF02790792

    1987 doi

  8. [16]

    Grothendieck type norms for bilinear forms on C∗-algebras

    Uffe Haagerup and Takashi Itoh. Grothendieck type norms for bilinear forms on C∗-algebras. J. Operator Theory, 34(2):263–283, 1995. ISSN 0379-4024

    1995

  9. [17]

    Aram W. Harrow. Quantum expanders from any classical cayley graph expander. Quan- tum Information & Computation , 8(8):715–721, 2008. URL http://www.rintonpress.com/ xxqic8/qic-8-89/0715-0721.pdf

    2008

  10. [18]

    Hastings

    Matthew B. Hastings. Random unitaries give quantum expanders. Phys. Rev. A (3) , 76 (3):032315, 11, 2007. ISSN 1050-2947. DOI: 10.1103/PhysRevA.76.032315. URL https: //doi.org/10.1103/PhysRevA.76.032315

    2007 doi

  11. [19]

    Superadditivity of communication capacity using entangled inputs

    Matthew B Hastings. Superadditivity of communication capacity using entangled inputs. Nature Physics , 5(4):255, 2009. DOI: 10.1038/nphys1224. URL http://dx.doi.org/10. 1038/nphys1224

    2009 doi

  12. [20]

    Hastings and Aram W

    Matthew B. Hastings and Aram W. Harrow. Classical and quantum tensor product expanders. Quantum Information & Computation , 9(3):336–360, 2009. URL http://www.rintonpress. com/xxqic9/qic-9-34/0336-0360.pdf

    2009

  13. [21]

    Remarks on the classical capacity of quantum channel

    Alexander S Holevo. Remarks on the classical capacity of quantum channel. arXiv preprint quant-ph/0212025, 2002. Accepted in Quantum 2020-06-17, click title to verify. Published under CC-BY 4.0. 17

    2002 arXiv

  14. [22]

    Alexander S. Holevo. The additivity problem in quantum information theory. In International Congress of Mathematicians. Vol. III , pages 999–1018. Eur. Math. Soc., Z¨ urich, 2006

    2006

  15. [23]

    Expander graphs and their applications

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. , 43:439–561, 2006. DOI: 10.1090/S0273-0979-06-01126-8. URL http: //dx.doi.org/10.1090/S0273-0979-06-01126-8

    2006 doi

  16. [24]

    Discrepancy and eigenvalues of Cayley graphs

    Yoshiharu Kohayakawa, Vojtˇ ech R¨ odl, and Mathias Schacht. Discrepancy and eigenvalues of Cayley graphs. Czechoslovak Math. J. , 66(141)(3):941–954, 2016. ISSN 0011-4642. DOI: 10.1007/s10587-016-0302-x. URL https://doi.org/10.1007/s10587-016-0302-x

    2016 doi

  17. [25]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and num- bers, volume 15 of Bolyai Soc. Math. Stud. , pages 199–262. Springer, Berlin, 2006. DOI: 10.1007/978-3-540-32439-3˙10. URL https://doi.org/10.1007/978-3-540-32439-3_10

    2006 doi

  18. [26]

    Ramanujan graphs

    Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinator- ica, 8(3):261–277, 1988. DOI: 10.1007/BF02126799. URL http://dx.doi.org/10.1007/ BF02126799

    1988 doi

  19. [27]

    Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators

    Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission, 24(1):39–46, 1988

    1988

  20. [28]

    Efficient rounding for the noncom- mutative Grothendieck inequality

    Assaf Naor, Oded Regev, and Thomas Vidick. Efficient rounding for the noncom- mutative Grothendieck inequality. Theory Comput. , 10(11):257–295, 2014. DOI: 10.1145/2488608.2488618. URL http://dx.doi.org/10.1145/2488608.2488618. Earlier version in STOC’13

    2014

  21. [29]

    Grothendieck’s theorem, past and present

    Gilles Pisier. Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc. (N.S.) , 49 (2):237–323, 2012. ISSN 0273-0979. DOI: 10.1090/S0273-0979-2011-01348-9. URL https: //doi.org/10.1090/S0273-0979-2011-01348-9

    2012 doi

  22. [30]

    J. Reeds. A new lower bound on the real Grothendieck constant. Available at http://www. dtc.umn.edu/˜reedsj/bound2.dvi, 1991

    1991

  23. [31]

    Quantum XOR games

    Oded Regev and Thomas Vidick. Quantum XOR games. ACM Trans. Comput. Theory , 7 (4):Art. 15, 43, 2015. ISSN 1942-3454. DOI: 10.1145/2799560. URL https://doi.org/10. 1145/2799560

    2015 doi

  24. [32]

    Representations of finite and compact groups

    Barry Simon. Representations of finite and compact groups . Number 10. American Mathe- matical Soc., 1996. DOI: 10.1090/gsm/010. URL http://dx.doi.org/10.1090/gsm/010

    1996 doi

  25. [33]

    Pseudorandom graphs

    Andrew Thomason. Pseudorandom graphs. In Random graphs ’85 (Pozna´ n, 1985), volume 144 of North-Holland Math. Stud. , pages 307–331. North-Holland, Amsterdam, 1987

    1985

  26. [34]

    Random graphs, strongly regular graphs and pseudorandom graphs

    Andrew Thomason. Random graphs, strongly regular graphs and pseudorandom graphs. In Surveys in combinatorics 1987 (New Cross, 1987) , volume 123 of London Math. Soc. Lecture Note Ser., pages 173–195. Cambridge Univ. Press, Cambridge, 1987. Accepted in Quantum 2020-06-17, click...

    1987

Pith tools

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