Pith. sign in

REVIEW 2 major objections 5 minor 4 cited by

Factorization norms and an inverse theorem for MaxCut

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every Boolean matrix with bounded $\gamma_2$-norm contains a linear-sized all-zeros or all-ones submatrix, and derives an inverse theorem for MaxCut: graphs with near-minimal maximum cut must contain a clique of size…

desk verdict Strong main results (Theorem 1.1 and the MaxCut inverse theorem) but a genuine gap in Lemma 7.1's proof currently leaves Theorem 1.5 and its corollaries unsupported. read the letter →

arxiv 2506.23989 v1 pith:7NZQRWAX submitted 2025-06-30 math.CO cs.CCcs.DM

Igor Balla , Lianna Hambardzumyan , István Tomon This is my paper · ORCID
classification math.COcs.CCcs.DM MSC 05C3505C5015A2315A60
keywords $\gamma_2$-normfactorizationnormMaxCutinversetheoremBooleanmatricestracemonochromaticsubmatrixgraphenergy
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 proves that any Boolean matrix with $\gamma_2$-factorization norm at most $\gamma$ contains an all-zeros or all-ones submatrix whose dimensions are a constant fraction of the original, with the fraction at least $2^{-O(\gamma^3)}$. This verifies a conjecture of [HHH23], and the same conclusion is shown to hold under the weaker hypothesis of bounded normalized trace norm. As a key application, the paper establishes an inverse theorem for MaxCut: if a graph with $m$ edges has maximum cut at most $m/2 + \alpha\sqrt{m}$, then it contains a clique of size $2^{-O(\alpha^9)}\sqrt{m}$. This is the first inverse theorem in the near-minimal regime, and it is tight up to the constant in the exponent.

What carries the argument

The key object is the $\gamma_2$ factorization norm, defined as $\gamma_2(M) = \min_{M=UV} \|U\|_{\mathrm{row}}\|V\|_{\mathrm{col}}$, which measures how much a matrix action is distorted when factored through $\ell_2$ and serves as a smooth surrogate for rank. The proof of the main structural result runs through an iterative sparsification lemma (Lemma 5.3): starting from a matrix of density at most $1/2$, it repeatedly finds a large submatrix whose $\gamma_2$-norm drops by $\Omega(1/\gamma)$ per step, using "brilliant" rows and columns and orthogonal projection, until the submatrix is all-zero after $O(\gamma^2)$ steps. For the MaxCut theorem, the load-bearing mechanism is the energy-surplus bound $\mathrm{sp}(G) = \Omega(E(G))$, proved by a hyperplane-rounding argument applied to a positive-semidefinite factorization of the adjacency matrix, together with the classical bound $\mathrm{sp}(G) \ge n/6$ that absorbs the linear error term; this converts a near-minimal MaxCut into a bound on the trace norm, enabling Corollary 1.2 to locate a large complete bipartite subgraph, from which Tur\'an's theorem produces the clique.

What would settle it

Calculate the surplus-to-energy ratio $\mathrm{sp}(G)/E(G)$ for a growing family of graphs with no isolated vertices, for instance random regular graphs of increasing degree; Lemma 9.4 predicts this ratio is bounded below by a universal constant, so any sequence with the ratio tending to zero would falsify the inverse MaxCut theorem.

Watch

Extended reading notes

Core claim

The central discovery is that the $\gamma_2$ factorization norm is a structural parameter for Boolean matrices: a bounded $\gamma_2$-norm forces a linear-sized monochromatic submatrix, with quantitative bound $\delta_1,\delta_2 \ge 2^{-O(\gamma^3)}$ in Theorem 1.1. The same structural conclusion follows from a bounded normalized trace norm (Corollary 1.2), and a construction shows the dependence cannot be improved below $2^{-O(\gamma)}$ (Theorem 1.4). For four-cycle-free matrices, the paper proves $\gamma_2(M) = \Theta(\sqrt{d})$ where $d$ is the degeneracy (Theorem 1.5), yielding a Zarankiewicz-type theorem (Theorem 1.6). On the MaxCut side, the proof shows that the surplus $\mathrm{sp}(G) = \mathrm{MaxCut}(G) - e(G)/2$ of any graph with no isolated vertices is at least a constant times the energy $E(G)$ (the trace norm of the adjacency matrix), improving a previous bound with a logarithmic loss (Lemma 9.4). Combining this energy-surplus inequality with the trace-norm corollary produces a complete bipartite subgraph of size $2^{-O(\alpha^9)}\sqrt{m}$, from which Tur\'an's theorem yields the large clique (Theorem 1.7).

Load-bearing premise

The inverse MaxCut theorem rests on the new inequality that a graph's cut surplus is at least a constant fraction of its energy (the trace norm of the adjacency matrix); if that inequality fails for some family of graphs, the clique conclusion collapses.

Editorial extensions

If this is right

  • Any Boolean matrix with constant $\gamma_2$-norm contains a linear-sized all-zeros or all-ones submatrix, removing the main structural barrier toward the randomized communication complexity conjecture of [CLV19, HHH23].
  • The same conclusion holds under the weaker hypothesis of constant normalized trace norm, so the result applies directly to adjacency matrices of graphs with small energy, including those arising in spectral graph theory.
  • Graphs with $m$ edges and MaxCut at most $m/2 + O(\sqrt{m})$ contain a clique of size $\Omega(\sqrt{m})$, settling the clique case of the Alon\,--\,Krivelevich\,--\,Sudakov conjecture at the extreme end of the spectrum.
  • Four-cycle-free matrices have $\gamma_2$-norm comparable to the square root of their degeneracy, giving sharp bounds for the hereditary discrepancy of geometric set systems such as point-line incidence matrices.
  • Graphs with smallest eigenvalue at least $-\lambda$ contain cliques of size $\Omega_\lambda(d)$ where $d$ is the average degree, a strengthening that follows from the Zarankiewicz-type theorem.

Reading between the lines

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

  • A natural extension beyond the paper is to ask whether the energy-surplus inequality $\mathrm{sp}(G) = \Omega(E(G))$ generalizes to hypergraph cuts, where an analogous trace norm of a tensor could play the role of energy.
  • The gap between the upper bound $2^{-O(\gamma^3)}$ in Theorem 1.1 and the lower bound $2^{-O(\gamma)}$ in Theorem 1.4 suggests that the true exponent may be closer to linear; tightening this gap would directly improve bounds for the approximate-$\gamma_2$ version relevant to randomized communication complexity.
  • The MaxCut proof method, which routes through the trace norm of the adjacency matrix, may adapt to other cut-like optimization problems (for instance Max $k$-Cut or bisection) once a version of the energy-surplus bound is established for those objectives.
  • Theorem 1.6 and its corollaries such as Theorem 2.4 currently rely on the unpublished Lemma 7.4 used as a black box; a public proof of that lemma would remove the only conditional component from these consequences.
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

2 major / 5 minor

Summary. The paper develops structural results for Boolean matrices with bounded gamma_2-norm. Theorem 1.1 asserts that an m x n Boolean matrix with gamma_2(M) <= gamma contains a delta_1 m x delta_2 n all-zero or all-one submatrix with delta_1, delta_2 >= 2^{-O(gamma^3)}, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. Corollary 1.2 extends this to bounded normalized trace norm, Corollary 1.3 handles integer matrices, and Theorem 1.4 gives a matching construction. The paper also proves that four-cycle-free Boolean matrices satisfy gamma_2(M) = Theta(sqrt(d)) where d is the degeneracy (Theorem 1.5), derives a Zarankiewicz-type consequence (Theorem 1.6), and proves an inverse theorem for MaxCut: if a graph with m edges has surplus at most alpha sqrt(m), then it contains a clique of size 2^{-O(alpha^9)} sqrt(m) (Theorem 1.7). The proofs combine matrix factorization, discrepancy sparsification, spectral arguments, and a semidefinite-programming-based energy bound for MaxCut.

Significance. If the central claims hold, the paper resolves a conjecture of Hambardzumyan, Hatami, and Hatami and gives the first inverse theorem for MaxCut in the near-minimal regime, a substantial result in extremal graph theory. The main derivations in Sections 5 and 9 are coherent and proceed from first principles, with explicit quantitative bounds and no fitted parameters. The paper also gives a tight construction and connects the results to communication complexity, operator theory, discrepancy theory, and spectral graph theory. However, the proof of Theorem 1.5 currently rests on a false step in Lemma 7.1, and Theorem 1.6 depends on an unpublished lemma from overlapping authors; these issues affect the supporting structural claims but not the main Theorem 1.1 or the MaxCut inverse theorem.

major comments (2)
  1. [7, Lemma 7.1] The proof of Lemma 7.1 contains a false step. After deleting the high-degree set C from the larger part A0, the paper claims that the induced subgraph G1 on A1 union B0 satisfies e(G1) >= d0 |A1|/2. This is unjustified and is false in general. For example, take A1 = {a_1,...,a_N}, C = {c}, B0 = {b_1,...,b_N}, with edges from c to every vertex in A1 union B0 and no other edges. Then G0 is the whole graph, with average degree d0 = 4N/(2N+1), and C is the only vertex of degree larger than 2d0, so A1 has size N. But G1 = G0[A1 union B0] has no edges, while d0|A1|/2 is about N. Thus e(G1) >= d0|A1|/2 fails. Since Lemma 7.1 is the first step in the proof of Lemma 7.2, which establishes the lower bound in Theorem 1.5, the proof of Theorem 1.5 is incomplete as written. Consequently Theorems 1.6, 2.2, and 2.4, which rely on Theorem 1.5 or 1.6, are also unsupported until this lemma is repaired. The lemma itself may be true, but the current argument does not prove it.
  2. [7, Lemma 7.4 and Theorem 1.6] Theorem 1.6 depends on Lemma 7.4, which is cited to an unpublished manuscript 'in preparation' by Hunter, Milojevic, Sudakov, and Tomon. The lemma is used as a black box and is load-bearing: without it, the proof of Theorem 1.6 does not go through. Since one of the authors of the current paper is also an author of the cited unpublished work, the manuscript should either include a proof of Lemma 7.4, cite a public version with a verifiable statement, or explicitly mark Theorem 1.6 (and Theorem 2.4, which uses it) as conditional on an external result. This is not a concern for Theorem 1.1 or Theorem 1.7, whose proofs do not use Lemma 7.4.
minor comments (5)
  1. [5, Proof of Theorem 5.2] In the induction step, the displayed inequality 'gamma_2(M_{i+1}) < gamma_2(M_{i+1}) - c/gamma_2(M_{i+1})' is self-referential; it should read 'gamma_2(M_{i+1}) < gamma_2(M_i) - c/gamma_2(M_i)'. The subsequent 'gamma(M_i)' should also be 'gamma_2(M_i)'.
  2. [5, Proof of Corollary 1.2] In the proof of Corollary 1.2, the phrase 'for some t/m, u/m >= 2^{-O(gamma^3)}' should read 't/m, u/n >= 2^{-O(gamma^3)}'.
  3. [9, Lemma 9.4] In the computation of the expected cut size, sum over edges of <x_a,x_b> equals <A,M'>/2, not <A,M'>, because each edge contributes once but the Frobenius inner product sums over ordered pairs. The displayed expression is therefore missing a factor of 1/2. This changes the constant from E(G)/(2pi) to E(G)/(4pi) in the lower bound sp(G) >= E(G)/(2pi) - O(n), but the conclusion sp(G) = Omega(E(G)) is unaffected because Lemma 9.3 supplies the additional term sp(G) = Omega(n).
  4. [5, Lemma 5.3, Case (c)] In the final part of Case (c), the sentence 'then V_J has at least n_J/(4 gamma^2) columns' should refer to the submatrix V' of V_I, not to V_J. The notation is confusing as written.
  5. [9, Proof of Theorem 9.1] When Lemma 4.4 is applied to J - B, the resulting submatrix B' should be explicitly described as the corresponding submatrix of B, not of J - B, to avoid ambiguity in the sentence 'we can find such a submatrix B''.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular reduction: the main theorems are derived self-containedly, with one in-preparation self-cited lemma used only in secondary results.

full rationale

The central derivation chain is not circular. Theorem 1.1 is proved by iterating Lemma 5.3, whose proof builds only on the discrepancy estimates of Lemma 4.4, basic gamma_2 properties, and elementary linear algebra; Corollary 1.2 follows from SVD truncation (Lemma 5.1) plus Theorem 1.1, never the reverse. The MaxCut inverse theorem (Theorem 9.1 and Theorem 1.7) is an independent chain: Lemma 9.2 is a probabilistic subadditivity argument, Lemma 9.3 is the external Erdős-Gyárfás-Kohayakawa bound, and Lemma 9.4 is a self-contained SDP/hyperplane-rounding proof that sp(G) = Omega(E(G)); the proof then uses Lemma 5.1, Lemma 4.4, Theorem 5.2, and Turán's theorem. No parameter is fitted to the target conclusion and no theorem is defined in terms of the object it predicts. The only notable self-citation is Lemma 7.4, quoted from [HMST] and listed as 'in preparation'; it is load-bearing for Theorem 1.6 and hence Theorem 2.4, but it is a general bipartite graph lemma independent of the target results, and the headline theorems (Theorem 1.1 and Theorem 1.7) do not use it. This is a proof-completeness and reliability concern for secondary results, not a circular reduction. Separately, the proof of Lemma 7.1 contains an unjustified edge-count step (e(G1) >= d0|A1|/2 fails on a star-like bipartite graph), and Lemma 9.4's Taylor summation omits a factor 1/2 when passing from edge sums to the Frobenius inner product, weakening the constant but not the Omega(E(G)) conclusion; both are correctness risks, not circularity.

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

The central theorems (1.1, 1.2, 1.7) are derived from standard linear algebra and a few external lemmas; Theorem 1.6 additionally depends on an unpublished lemma from a same-author group. No fitted or data-dependent parameters appear anywhere; all constants are absolute or depend only on the input parameters γ and α.

assumptions (5)
  • domain assumption Lemma 7.4 (Hunter, Milojević, Sudakov, Tomon, in preparation): every bipartite graph of average degree d with no four-cycle-free induced subgraph of average degree at least k contains a subgraph on at most d vertices with at least c d^2 edges.
    Invoked as a black box in the proof of Theorem 1.6. The result is cited as 'in preparation' and is not proven in this manuscript. At least one author (Tomon) overlaps with the present paper, so a public proof is required before the dependency is fully verified.
  • domain assumption Lemma 4.2, stated as a consequence of Claim 2.2 of Sudakov and Tomon [ST24], which asserts a binary matrix contains a half-sized submatrix whose density drops by an amount proportional to the discrepancy.
    Used to prove the sparsification Lemma 4.3, which is essential for Theorem 1.1. It is an external preprint result with overlapping authorship; the statement is used without proof in this paper.
  • domain assumption Lemma 9.3 (Erdős, Gyárfás, Kohayakawa): a graph on n vertices with no isolated vertices has sp(G) ≥ n/6.
    Used in Lemma 9.4 and Theorem 9.1 to convert the energy lower bound into a surplus lower bound. The result is cited from the literature rather than proved here.
  • standard math Grothendieck's inequality, in the form that the cut-norm and the dual γ2* norm are equivalent up to absolute constant factors.
    Used in Lemma 4.1 to lower-bound the discrepancy by a γ2* expression, a standard tool in the factorization norm literature.
  • standard math Cauchy interlacing theorem for eigenvalues of principal submatrices of a real symmetric matrix.
    Used in Lemma 7.2 and Theorem 2.4 to transfer eigenvalue bounds from a submatrix to the original matrix.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Factorization norms and an inverse theorem for MaxCut." pith.science (2026). https://pith.science/paper/7NZQRWAX

@misc{pith2026250623989,
  author       = {Pith},
  title        = {Pith review of: Factorization norms and an inverse theorem for MaxCut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7NZQRWAX}},
  note         = {Machine review of arXiv:2506.23989}
}
abstract

We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_2$-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph $G$ with $m$ edges has a cut of size at least $\frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}$, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of $G$ is at most $\frac{m}{2}+O(\sqrt{m})$, then $G$ must contain a clique of size $\Omega(\sqrt{m})$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

    math.CO 2025-07 conditional novelty 8.0 of 10

    A new spectral argument shows that very dense graphs far from unions of cliques have least eigenvalue at most -n^{1/4-epsilon}, and this yields max-cut surpluses of order n^{1.01} and m^{0.5001} for H-free graphs.

  2. A note on matchings and co-matchings in bipartite graphs

    math.CO 2026-07 reject novelty 7.0 of 10

    For bipartite graphs with no induced matching of size k and no induced co-matching of size ℓ, a pure pair exists with both sides at least 4/(13·binom(k+ℓ−4,k−2)) of the graph, and diagonal constructions show exponenti...

  3. Beyond the MaxCut problem in $H$-free graphs

    math.CO 2025-07 conditional novelty 7.0 of 10

    Graphs with m edges and no clique of size near sqrt(m) must have a cut exceeding m/2 by a power of m.

  4. Block structure in boolean matrices of bounded factorization norm

    math.CA 2025-07 conditional novelty 6.0 of 10

    A boolean matrix with gamma-2 norm at most lambda contains a blocky submatrix that covers at least a 1/2^{2^{O(lambda)}} fraction of its 1-entries.

Reference graph

Works this paper leans on

52 extracted references · 49 canonical work pages · cited by 4 Pith papers

  1. [1]

    N. Alon, M. Krivelevich, and B. Sudakov. Maxcut in H -free graphs. Comb. Prob. Comp. , 14:629--647, 2005

    work page 2005

  2. [2]

    N. Alon. Bipartite subgraphs. Combinatorica , 16:301--311, 1996

    work page 1996

  3. [3]

    N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Inventiones Mathematicae , 163(3):499--522, 2006

    work page 2006

  4. [4]

    I. Balla. Equiangular lines via matrix projection. 2021. preprint, arXiv:2110.15842

    arXiv 2021

  5. [5]

    Beck and W

    J. Beck and W. W. L. Chen. Irregularities of Distribution . Cambridge University Press, Cambridge, 1987

    work page 1987

  6. [6]

    Balla, F

    I. Balla, F. Dr\"axler, P. Keevash, and B. Sudakov. Equiangular lines and spherical codes in E uclidean space. Inventiones mathematicae , 211(1):179--212, 2018

    work page 2018

  7. [7]

    Balla, O

    I. Balla, O. Janzer, and B. Sudakov. On M ax C ut and the L ov\'asz theta function. Proceedings of AMS , 152:1871--1879, 2024

    work page 2024

  8. [8]

    P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult. Line graphs, root systems, and elliptic geometry. Journal of Algebra , 43(1):305--327, 1976

    work page 1976

Show all 52 references
  1. [9]

    Chazelle

    B. Chazelle. The Discrepancy Method . Cambridge University Press, Cambridge, 2000

    2000

  2. [10]

    Cheung, H

    T.-M. Cheung, H. Hatami, K. Hosseini, A. Nikolov, T. Pitassi, and M. Shirley. A lower bound on the trace norm of boolean matrices and its applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages 37--1. Schloss Dagstuhl-Leibniz-Zentrum f\...

    2025

  3. [11]

    Cheung, H

    T.-M. Cheung, H. Hatami, K. Hosseini, and M. Shirley. Separation of the factorization norm and randomized communication complexity. In 38th Computational Complexity Conference (CCC 2023) . Schloss Dagstuhl-Leibniz-Zentrum f\"ur Informatik, 2023

    2023

  4. [12]

    Chazelle and A

    B. Chazelle and A. Lvov. A trace bound for the hereditary discrepancy. Disc. Comput. Geom. , 26:221--231, 2001

    2001

  5. [13]

    Chattopadhyay, S

    A. Chattopadhyay, S. Lovett, and M. Vinyals. Equality alone does not simulate randomness. In 34th Computational Complexity Conference (CCC 2019) . Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, 2019

    2019

  6. [14]

    C. S. Edwards. Some extremal properties of bipartite subgraphs. Canadian Journal of Mathematics , 3:475--485, 1973

    1973

  7. [15]

    C. S. Edwards. An improved lower bound for the number of edges in a largest bipartite subgraph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) , pages 167--181, 1975

    1974

  8. [16]

    Erd o s, A

    P. Erd o s, A. Gy\'arf\'as, and Y. Kohayakawa. The size of the largest bipartite subgraphs. Disc. Math. , 177:267--271, 1997

    1997

  9. [17]

    Edmonds, A

    A. Edmonds, A. Nikolov, and J. Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 425--438, 2020

    2020

  10. [18]

    P. Erd o s. Problems and results in graph theory and combinatorial analysis. Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, 1977), Academic Press , pages 153--163, 1979

    1977

  11. [19]

    Fichtenberger, M

    H. Fichtenberger, M. Henzinger, and J. Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning , pages 10072--10092. PMLR, 2023

    2023

  12. [20]

    J. Fox, J. Pach, and A. Suk. Erd o s-- H ajnal conjecture for graphs with bounded VC -dimension. Discrete & Computational Geometry , 61:809--829, 2019

    2019

  13. [21]

    Goh and H

    M. Goh and H. Hatami. Block complexity and idempotent schur multipliers. 2025. in preparation

    2025

  14. [22]

    Goh and H

    M. Goh and H. Hatami. Block structure and B oolean matrices of bounded factorization norm. 2025. in preparation

    2025

  15. [23]

    Glock, O

    S. Glock, O. Janzer, and B. Sudakov. New results for M ax C ut in H -free graphs. Journal of London Math. Soc. , 108:441--481, 2023

    2023

  16. [24]

    Grothendieck

    A. Grothendieck. R \'e sum \'e de la th \'e orie m \'e trique des produits tensoriels topologiques , volume 2. Soc. de Matem \'a tica de S \ a o Paulo, 1956

    1956

  17. [25]

    Boolean functions with small spectral norm

    Ben Green and Tom Sanders. Boolean functions with small spectral norm. Geometric and Functional Analysis , 18(1):144--162, 2008

    2008

  18. [26]

    A quantitative version of the idempotent theorem in harmonic analysis

    Ben Green and Tom Sanders. A quantitative version of the idempotent theorem in harmonic analysis. Annals of mathematics , pages 1025--1054, 2008

    2008

  19. [27]

    M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the Association for Computing Machinery , 42:1115--1145, 1995

    1995

  20. [28]

    Hambardzumyan, H

    L. Hambardzumyan, H. Hatami, and P. Hatami. Dimension-free bounds and structural results in communication complexity. Israel Journal of Mathematics , 253(2):555--616, 2023

    2023

  21. [29]

    Hunter, A

    Z. Hunter, A. Milojevi\'c, B. Sudakov, and I. Tomon. C _4 -free subgraphs of high degree with geometric applications. in preparation

  22. [30]

    Hunter, A

    Z. Hunter, A. Milojevi \'c , B. Sudakov, and I. Tomon. Disjoint pairs in set systems and combinatorics of low rank matrices, 2024. preprint, arxiv:2411.13510

    2024 arXiv

  23. [31]

    Janzer and B

    O. Janzer and B. Sudakov. Resolution of the E rd o s- S auer problem on regular subgraphs. Forum of Mathematics, Pi , 11:e19, 2023

    2023

  24. [32]

    Jiang, J

    Z. Jiang, J. Tidor, Y. Yao, S. Zhang, and Y. Zhao. Equiangular lines with a fixed angle. Annals of Mathematics , 194(3):729--743, 2021

    2021

  25. [33]

    J. H. Koolen, M. Y. Cao, and Q. Yang. Recent progress on graphs with fixed smallest adjacency eigenvalue: A survey. Graphs and Combinatorics , 37(4):1139--1178, 2021

    2021

  26. [34]

    H. K. Kim, J. H. Koolen, and J. J. Yang. A structure theory for graphs with fixed smallest eigenvalue. Lin. Alg. Appl. , 504:1--13, 2016

    2016

  27. [35]

    Kwapie \'n

    S. Kwapie \'n . On operators factorizable through l\_p space. M \'e moires de la Soci \'e t \'e Math \'e matique de France , 31:215--225, 1972

    1972

  28. [36]

    J. H. Koolen, J. Y. Yang, and Q. Yang. On graphs with smallest eigenvalue at least -3 and their lattices. Advances in Mathematics , 338:847--864, 2018

    2018

  29. [37]

    S. Lovett. Communication is bounded by root of rank. J. ACM , 63(1):Art. 1, 9, 2016

    2016

  30. [38]

    P. W. H. Lemmens and J. J. Seidel. Equiangular lines. J. Algebra , 24:494--512, 1973

    1973

  31. [39]

    Lov\'asz and M

    L. Lov\'asz and M. Saks. Lattices, M \"obius functions and communication complexity. Annual Symposium on Foundations of Computer Science , pages 81--90, 1988

    1988

  32. [40]

    Linial and A

    N. Linial and A. Shraibman. Learning complexity vs communication complexity. Comb. Prob. Comp. , 18(1-2):227--245, 2009

    2009

  33. [41]

    Linial and A

    N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures & Algorithms , 34(3):368--394, 2009

    2009

  34. [42]

    T. Lee, A. Shraibman, and R. S palek. A direct product theorem for discrepancy. In 2008 23rd Annual IEEE Conference on Computational Complexity , pages 71--80, 2008

    2008

  35. [43]

    B. Maurey. Th \'e or \`e mes de factorisation pour les op \'e rateurs lin \'e aires \`a valeurs dans un espace L^ p ( , ), 0< p + . S \'e minaire Maurey-Schwartz , pages 1--8, 1974

    1974

  36. [44]

    Muthukrishnan and A

    S. Muthukrishnan and A. Nikolov. Optimal private halfspace counting via discrepancy. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 1285--1292, 2012

    2012

  37. [45]

    Matou s ek, A

    J. Matou s ek, A. Nikolov, and K. Talwar. Factorization norms and hereditary discrepancy. Int. Math. Res. Not. , 2020(3):751--780, 2020

    2020

  38. [46]

    Nisan and A

    N. Nisan and A. Wigderson. On rank vs. communication complexity. Combinatorica , 15(4):557--565, 1995

    1995

  39. [47]

    R\"aty, B

    E. R\"aty, B. Sudakov, and I. Tomon. Positive discrepancy, M ax C ut, and eigenvalues of graphs. 2023. preprint, arxiv:2311.02070

    2023 arXiv

  40. [48]

    R\"aty and I

    E. R\"aty and I. Tomon. Large cuts in hypergraphs via energy. Math. Proc. Camb. Soc. , 179(1):45--61, 2025

    2025

  41. [49]

    ankten bilinearformen mit unendlich vielen ver\

    I. Schur. Bemerkungen zur theorie der beschr\"ankten bilinearformen mit unendlich vielen ver\"anderlichen. J. Reine. Angew. Math. , 140:1--28, 1911

    1911

  42. [50]

    Sudakov and I

    B. Sudakov and I. Tomon. Matrix discrepancy and the log-rank conjecture. Mathematical Programming , 2024

    2024

  43. [51]

    J. A. Tropp. Column subset selection, matrix factorization, and eigenvalue optimization. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms , pages 978--986. SIAM, 2009

    2009

  44. [52]

    P. Tur\'an. On an extremal problem in graph theory. Matematikai \'es Fizikai Lapok (in Hungarian) , 48:436--452, 1941

    1941

Pith tools

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