pith. machine review for the scientific record. sign in

arxiv: 2605.09006 · v1 · submitted 2026-05-09 · 💻 cs.DS

Recognition: no theorem link

Witness-Sensitive Detection of Induced Diamonds

Keren Censor-Hillel , Tomer Even , Virginia Vasillevska Williams , Nathan Wallheimer

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:12 UTC · model grok-4.3

classification 💻 cs.DS
keywords induced diamondwitness-sensitive detectiongraph algorithmssubgraph detectionmatrix multiplicationsampling framework4-SUMfine-grained complexity
0
0 comments X

The pith

The algorithm detects induced diamonds in Õ(min(n^{2.425}/t^{0.25} + n², n^ω)) time with high probability when t such diamonds exist.

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

This paper develops a witness-sensitive algorithm for finding induced diamonds, which are K4 minus one edge, in an n-vertex graph known to contain t of them. The running time improves on the previous best matrix-multiplication algorithm whenever t is at least n to the power of roughly (3 minus omega) over 3. The method splits into cases: it handles r-heavy diamonds, where one triangle lies inside a clique of size r or larger, via a direct algorithm, and handles the absence of such heavy diamonds via adaptive sampling. A new refinement framework for sampling vectors supports the adaptive case and yields the claimed matrix-multiplication bound. Sympathetic readers care because the speed now scales with the number of solutions rather than always paying the full worst-case cost.

Core claim

We provide a fast witness-sensitive algorithm for detecting an induced diamond in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^{2.425}/t^{0.25}+n², n^ω)) with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time O(n^ω log n) whenever t ≥ n^{(3-ω)/3}. The key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role; a diamond is r-heavy if this size is at least r. We give a fast detection algorithm for r-heavy diamonds in Õ(r · (n/r)^ω + (n/r)^3 + nr) time. When there are no r-heavy diamonds, we give a different fast detection algorithm in Õ(MM(n

What carries the argument

The refinement framework for sampling vectors that permits adaptive sampling of vertices in graphs containing no r-heavy diamonds.

Load-bearing premise

The refinement framework for sampling vectors correctly enables adaptive sampling in graphs with no r-heavy diamonds, supporting the claimed MM(n, n, n√(r/t)) time bound.

What would settle it

Construct a family of graphs with t induced diamonds and no r-heavy ones in which the adaptive sampling step requires more than Õ(n^{2.425}/t^{0.25}) time or misses all diamonds with constant probability.

Figures

Figures reproduced from arXiv: 2605.09006 by Keren Censor-Hillel, Nathan Wallheimer, Tomer Even, Virginia Vasillevska Williams.

Figure 1
Figure 1. Figure 1: Running time of induced diamond detection as a function of [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two extreme configurations illustrating the “hard case” where diamonds cluster around a single [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Refinement sequence from P (1) to P (4). We set λ = 48 log n. The first vector is P (1) = (1/t), which samples each element in G (1) with probability 1/t. The first refinement is straightforward: view G (2) as a bipartite graph with vertex sets A = (V1×V2) and B = (V3×V4) and t edges. For 0 ≤ i ≤ log t, let Ai be the set of vertices in A with degree in [2i , 2 i+1). This lets us control degrees on the A-si… view at source ↗
Figure 4
Figure 4. Figure 4: {u1, u2, u3, v2} is an induced diamond; the dashed red edge (u3, v2) is missing. This observation also follows from [CMBM+21, Lemma 7]: a graph is diamond-free if and only if every edge lies in a unique maximal clique. Roadmap. The next paragraphs contain the notation and definitions used in the algorithm. The first part of the algorithm includes finding a set of edges L, computed using fast matrix multipl… view at source ↗
Figure 5
Figure 5. Figure 5: A 6-cycle in the graph Fi : u1 → W(e1) → u2 → W(e2) → u3 → W(e3) → u1. • If u3 ∈ W(e1), then (u1, u3) is a violating edge; both in W(e1) and W(e3). Thus, e1 is an r-revealing edge. • If u3 ∈/ W(e1), then it is not a neighbor of say v1, but it has two neighbors u1, u2 ∈ W(e1), thus (u1, u2) is an r-violating edge, and e1 is an r-revealing edge. We prove Lemma 3.8. We need one more theorem from extremal comb… view at source ↗
Figure 6
Figure 6. Figure 6: Refinement sequence from P (1) to P (4). We set λ = 48 log n. We explain how each refinement step is done. Each step follows the same “recipe”, with slight deviations to get better control over wheavy(P). From P (1) to P (2): Consider the bipartite graph G (2) with vertex set A ⊔ B and t edges. Let Ai denote the set of vertices in A with degree in [2i , 2 i+1), for every 0 ≤ i ≤ log t. One of these sets mu… view at source ↗
read the original abstract

We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a $K_4$ minus an edge) in an $n$-vertex graph containing $t$ induced diamonds. Our algorithm runs in time $\tilde{O}(\min(n^{2.425}/t^{0.25}+n^2, n^\omega))$ with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time $O(n^\omega\log{n})$ [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever $t \geq n^{(3-\omega)/3}$, where $\omega < 2.372$ is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is $r$-heavy if this size is at least $r$, and we provide a fast detection algorithm for $r$-heavy diamonds in $\tilde{O}(r \cdot (n/r)^\omega + (n/r)^3+ nr)$ time. When there are no $r$-heavy diamonds, we provide a different fast detection algorithm in $\tilde{O}(\mathsf{MM}(n,n,n\sqrt{r/t}))$ time, where $\mathsf{MM}(a,b,c)$ denotes the time to multiply an $a \times b$ matrix by a $b \times c$ matrix, which is conditionally optimal for $r=\tilde{O}(1)$. Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no $r$-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for $4$-SUM and for a special case of $4$-cycles.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents a witness-sensitive algorithm for detecting an induced diamond (K4 minus an edge) in an n-vertex graph containing t such diamonds. It achieves Õ(min(n^{2.425}/t^{0.25} + n², n^ω)) time with high probability by distinguishing r-heavy diamonds (where a triangle is contained in a clique of size at least r) from r-light ones, providing an Õ(r · (n/r)^ω + (n/r)^3 + nr) algorithm for the former and an Õ(MM(n, n, n√(r/t))) algorithm for the latter via a new refinement framework for adaptive vector sampling. The result improves on the prior O(n^ω log n) witness-oblivious bound for t ≥ n^{(3-ω)/3} and extends the framework to 4-SUM and a special case of 4-cycles.

Significance. If the refinement framework is correct, the result meaningfully advances witness-sensitive subgraph detection in fine-grained complexity by exploiting the number t of witnesses and the structural distinction between heavy and light diamonds. The adaptive sampling technique, which is claimed to be conditionally optimal for constant r, represents a technical contribution with potential applicability beyond induced diamonds, as demonstrated by the extensions to 4-SUM and 4-cycles.

major comments (1)
  1. [refinement framework section] The refinement framework for sampling vectors (detailed in the section on the main technical contribution): the analysis must explicitly verify that adaptive samples in graphs with no r-heavy diamonds preserve the required distribution while achieving the rectangular matrix-multiplication cost MM(n, n, n√(r/t)). The high-level description leaves open whether the probability bounds fully account for adaptivity without bias or violation of the r-light property, which is load-bearing for the overall min expression when t is large.
minor comments (2)
  1. [Introduction] Clarify the exact definition of 'witness-sensitive' versus 'witness-oblivious' early in the introduction, as the distinction is central to the claimed improvement.
  2. [Preliminaries] The notation MM(a,b,c) is introduced but its precise relation to the current best rectangular matrix multiplication exponents should be stated explicitly for reproducibility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on the manuscript. We address the single major comment below regarding the refinement framework. We agree that additional explicit verification is warranted and will revise the paper accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: The refinement framework for sampling vectors (detailed in the section on the main technical contribution): the analysis must explicitly verify that adaptive samples in graphs with no r-heavy diamonds preserve the required distribution while achieving the rectangular matrix-multiplication cost MM(n, n, n√(r/t)). The high-level description leaves open whether the probability bounds fully account for adaptivity without bias or violation of the r-light property, which is load-bearing for the overall min expression when t is large.

    Authors: We appreciate the referee's observation that the current high-level description of the adaptive sampling in the refinement framework does not provide fully explicit probability bounds. Upon re-examination, we agree that a more detailed verification is needed to confirm that the adaptive procedure preserves the uniform distribution over candidate vertices, introduces no bias, and respects the r-light property (i.e., does not create or rely on r-heavy diamonds). In the revised manuscript we will expand the relevant section with a new lemma (and supporting calculations) that rigorously bounds the failure probability of the adaptive samples, shows that the expected number of matrix-multiplication operations remains O(MM(n, n, n√(r/t))), and verifies that the r-light assumption is maintained throughout the sampling process. These additions will be placed immediately after the high-level overview and will include the precise concentration bounds used to obtain the overall Õ(min(...)) running time with high probability. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior diamond detection work; new refinement framework provides independent content

full rationale

The derivation introduces a novel refinement framework for adaptive vector sampling in graphs without r-heavy diamonds as the main technical contribution. This framework directly yields the Õ(MM(n,n,n√(r/t))) bound for the no r-heavy case, combined with the r-heavy detection algorithm that relies only on standard matrix multiplication. The sole self-citation is to the 2014 witness-oblivious algorithm by overlapping authors, which is cited only for comparison and is not used to justify the new framework, the adaptive sampling probabilities, or the overall min runtime expression. No self-definitional reductions, fitted inputs presented as predictions, uniqueness theorems, or ansatzes smuggled via citation are present; the central claims rest on the newly designed technique and the matrix-multiplication exponent ω.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard assumption of fast matrix multiplication and introduces a new algorithmic technique (refinement framework) rather than new entities or fitted constants.

free parameters (1)
  • r
    Threshold defining r-heavy diamonds; chosen to balance the two algorithmic cases and optimize the overall time bound.
axioms (1)
  • standard math Matrix multiplication of n×n matrices can be performed in O(n^ω) time with ω < 2.372
    Invoked directly in the time bound for r-heavy diamonds and in the overall min expression.

pith-pipeline@v0.9.0 · 5676 in / 1323 out tokens · 56758 ms · 2026-05-12T02:12:37.256728+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

  1. [1]

    Karypis , booktitle =

    Michihiro Kuramochi and G. Karypis , booktitle =. Frequent subgraph discovery , year =. Proceedings 2001 IEEE International Conference on Data Mining , pages =

    work page 2001

  2. [2]

    Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , title =

    Xin Liu and Haojie Pan and Mutian He and Yangqiu Song and Xin Jiang , booktitle =. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , title =

    work page

  3. [3]

    Proceedings of the 24th international conference on world wide web , pages =

    The k-clique densest subgraph problem , author =. Proceedings of the 24th international conference on world wide web , pages =

    work page

  4. [4]

    Alon and Phuong Dao and I

    N. Alon and Phuong Dao and I. Hajirasouliha and F. Hormozdiari and S. C. Sahinalp , booktitle =. Biomolecular network motif counting and discovery by color coding , volume =. Bioinformatics , pages =

    work page

  5. [5]

    Optimally discriminative subnetwork markers predict response to chemotherapy , volume =

    Dao, Phuong and Wang, Kendric and Collins, Colin and Ester, Martin and Lapuk, Anna and Sahinalp, S Cenk , journal =. Optimally discriminative subnetwork markers predict response to chemotherapy , volume =

    work page

  6. [6]

    Small molecule subgraph detector (SMSD) toolkit , volume =

    Rahman, Syed Asad and Bashton, Matthew and Holliday, Gemma L and Schrader, Rainer and Thornton, Janet M , journal =. Small molecule subgraph detector (SMSD) toolkit , volume =

    work page

  7. [7]

    Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism , year =

    Sun, Qingyun and Li, Jianxin and Peng, Hao and Wu, Jia and Ning, Yuanxing and Yu, Philip S and He, Lifang , booktitle =. Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism , year =

    work page

  8. [8]

    Zafeiriou and M

    Giorgos Bouritsas and Fabrizio Frasca and S. Zafeiriou and M. Bronstein , booktitle =. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting , volume =. IEEE Transactions on Pattern Analysis and Machine Intelligence , pages =

    work page

  9. [9]

    Question Answering with Subgraph Embeddings , year =

    Antoine Bordes and Sumit Chopra and Jason Weston , booktitle =. Question Answering with Subgraph Embeddings , year =. doi:10.3115/V1/D14-1067 , timestamp =

    work page doi:10.3115/v1/d14-1067

  10. [10]

    Property testing and its connection to learning and approximation , volume =

    Goldreich, Oded and Goldwasser, Shari and Ron, Dana , journal =. Property testing and its connection to learning and approximation , volume =

    work page

  11. [11]

    Efficient testing of large graphs , volume =

    Alon, Noga and Fischer, Eldar and Krivelevich, Michael and Szegedy, Mario , journal =. Efficient testing of large graphs , volume =

    work page

  12. [12]

    Algorithmica , month = feb, number =

    Property testing in bounded degree graphs , volume =. Algorithmica , month = feb, number =. 2002 , language =

    work page 2002

  13. [13]

    Alon and J

    N. Alon and J. Fox , booktitle =. Easily Testable Graph Properties , volume =. Combinatorics, Probability and Computing , pages =

    work page

  14. [14]

    Shapira , booktitle =

    Lior Gishboliner and A. Shapira , booktitle =. Deterministic vs non-deterministic graph property testing , volume =. Israel Journal of Mathematics , pages =

    work page

  15. [15]

    Testing the diameter of graphs , volume =

    Parnas, Michal and Ron, Dana , journal =. Testing the diameter of graphs , volume =

    work page

  16. [16]

    Tight bounds for testing bipartiteness in general graphs , volume =

    Kaufman, Tali and Krivelevich, Michael and Ron, Dana , journal =. Tight bounds for testing bipartiteness in general graphs , volume =

    work page

  17. [17]

    Sublinear-time algorithms for counting star subgraphs via edge sampling , volume =

    Aliakbarpour, Maryam and Biswas, Amartya Shankha and Gouleakis, Themis and Peebles, John and Rubinfeld, Ronitt and Yodpinyanee, Anak , journal =. Sublinear-time algorithms for counting star subgraphs via edge sampling , volume =

    work page

  18. [18]

    Approximately counting triangles in sublinear time , volume =

    Eden, Talya and Levi, Amit and Ron, Dana and Seshadhri, C , journal =. Approximately counting triangles in sublinear time , volume =

    work page

  19. [19]

    A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling , year =

    Assadi, Sepehr and Kapralov, Michael and Khanna, Sanjeev , journal =. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling , year =

    work page

  20. [20]

    ArXiv , title =

    Hendrik Fichtenberger and Mingze Gao and Pan Peng , booktitle =. ArXiv , title =

    work page

  21. [21]

    Eden and R

    Amartya Shankha Biswas and T. Eden and R. Rubinfeld , booktitle =. ArXiv , title =

    work page

  22. [22]

    A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling , volume =

    Sepehr Assadi and Michael Kapralov and Sanjeev Khanna , booktitle =. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling , volume =. 2019 , biburl =. doi:10.4230/LIPICS.ITCS.2019.6 , timestamp =

    work page doi:10.4230/lipics.itcs.2019.6 2019

  23. [23]

    Graph sketches: sparsification, spanners, and subgraphs , year =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , booktitle =. Graph sketches: sparsification, spanners, and subgraphs , year =

    work page

  24. [24]

    Better algorithms for counting triangles in data streams , year =

    McGregor, Andrew and Vorotnikova, Sofya and Vu, Hoa T , booktitle =. Better algorithms for counting triangles in data streams , year =

    work page

  25. [25]

    Towards tighter space bounds for counting triangles and other substructures in graph streams , year =

    Bera, Suman K and Chakrabarti, Amit , booktitle =. Towards tighter space bounds for counting triangles and other substructures in graph streams , year =

    work page

  26. [26]

    The complexity of counting cycles in the adjacency list streaming model , year =

    Kallaugher, John and McGregor, Andrew and Price, Eric and Vorotnikova, Sofya , booktitle =. The complexity of counting cycles in the adjacency list streaming model , year =

    work page

  27. [27]

    Approximate Triangle Counting via Sampling and Fast Matrix Multiplication , year =

    T. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication , year =. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , organization =

    work page 2022

  28. [28]

    More Asymmetry Yields Faster Matrix Multiplication , year =

    Josh Alman and Ran Duan and Virginia. More Asymmetry Yields Faster Matrix Multiplication , year =. Proceedings of the 2025

    work page 2025

  29. [29]

    Fast Approximate Counting of Cycles , volume =

    Keren Censor. Fast Approximate Counting of Cycles , volume =. 51st International Colloquium on Automata, Languages, and Programming,. 2024 , biburl =. doi:10.4230/LIPICS.ICALP.2024.37 , timestamp =

    work page doi:10.4230/lipics.icalp.2024.37 2024

  30. [30]

    CoRR , title =

    Keren Censor. CoRR , title =. 2025 , biburl =. doi:10.48550/ARXIV.2503.21655 , timestamp =

    work page doi:10.48550/arxiv.2503.21655 2025

  31. [31]

    Finding and counting small induced subgraphs efficiently , volume =

    Kloks, Ton and Kratsch, Dieter and M. Finding and counting small induced subgraphs efficiently , volume =. Information Processing Letters , number =

    work page

  32. [32]

    On the complexity of fixed parameter clique and dominating set , volume =

    Eisenbrand, Friedrich and Grandoni, Fabrizio , journal =. On the complexity of fixed parameter clique and dominating set , volume =

    work page

  33. [33]

    Finding four-node subgraphs in triangle time , year =

    Williams, Virginia Vassilevska and Wang, Joshua R and Williams, Ryan and Yu, Huacheng , booktitle =. Finding four-node subgraphs in triangle time , year =

    work page

  34. [34]

    Finding a minimum circuit in a graph , year =

    Itai, Alon and Rodeh, Michael , booktitle =. Finding a minimum circuit in a graph , year =

    work page

  35. [35]

    On the complexity of the subgraph problem , volume =

    Ne. On the complexity of the subgraph problem , volume =. Comment. Math. Univ. Carol. , number =

    work page

  36. [36]

    Subcubic Equivalences Between Path, Matrix, and Triangle Problems , volume =

    Virginia. Subcubic Equivalences Between Path, Matrix, and Triangle Problems , volume =. J

    work page

  37. [37]

    Strong cliques in diamond-free graphs , volume =

    Chiarelli, Nina and Mart. Strong cliques in diamond-free graphs , volume =. Theoretical Computer Science , pages =

    work page

  38. [38]

    A note on bipartite graphs without 2k-cycles , volume =

    Naor, Assaf and Verstra. A note on bipartite graphs without 2k-cycles , volume =. Combinatorics, Probability and Computing , number =

    work page

  39. [39]

    The size of bipartite graphs with girth eight , year =

    Neuwirth, Stefan , howpublished =. The size of bipartite graphs with girth eight , year =

    work page

  40. [40]

    Can you beat treewidth? , year =

    D. Can you beat treewidth? , year =. 51th Annual

    work page

  41. [41]

    Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle , volume =

    Holger Dell and John Lapinskas and Kitty Meeks , journal =. Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle , volume =

    work page

  42. [42]

    Arboricity and Subgraph Listing Algorithms , volume =

    Norishige Chiba and Takao Nishizeki , journal =. Arboricity and Subgraph Listing Algorithms , volume =

    work page

  43. [43]

    Color-coding , volume =

    Alon, Noga and Yuster, Raphael and Zwick, Uri , journal =. Color-coding , volume =

    work page

  44. [44]

    Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles , year =

    Dalirrooyfard, Mina and Vuong, Thuy Duong and Williams, Virginia Vassilevska , booktitle =. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles , year =

    work page

  45. [45]

    Mina Dalirrooyfard and V. V. Williams , booktitle =. Induced Cycles and Paths Are Harder Than You Think , year =. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    work page 2022

  46. [46]

    A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection , year =

    Abboud, Amir and Akmal, Shyan and Fischer, Nick , booktitle =. A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection , year =

    work page

  47. [47]

    Approximately counting and sampling Hamiltonian motifs in sublinear time , year =

    Eden, Talya and Levi, Reut and Ron, Dana and Rubinfeld, Ronitt , booktitle =. Approximately counting and sampling Hamiltonian motifs in sublinear time , year =

    work page

  48. [48]

    Distributed subgraph finding: progress and challenges , year =

    Censor-Hillel, Keren , journal =. Distributed subgraph finding: progress and challenges , year =

    work page

  49. [49]

    Lower Bounds for Induced Cycle Detection in Distributed Computing , year =

    Le Gall, Fran. Lower Bounds for Induced Cycle Detection in Distributed Computing , year =. 32nd International Symposium on Algorithms and Computation (ISAAC 2021) , organization =

    work page 2021

  50. [50]

    Distributed Complexity of P

    Masayuki Miyamoto , booktitle =. Distributed Complexity of P. 2025 , doi =

    work page 2025

  51. [51]

    Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters , volume =

    Nikabadi, Amir and Korhonen, Janne , booktitle =. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters , volume =

    work page

  52. [52]

    The time complexity of fully sparse matrix multiplication , year =

    Abboud, Amir and Bringmann, Karl and Fischer, Nick and K. The time complexity of fully sparse matrix multiplication , year =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , organization =

    work page 2024

  53. [53]

    Fast rectangular matrix multiplication and applications , volume =

    Huang, Xiaohan and Pan, Victor Y , journal =. Fast rectangular matrix multiplication and applications , volume =

    work page

  54. [54]

    All pairs shortest paths using bridging sets and rectangular matrix multiplication , volume =

    Zwick, Uri , journal =. All pairs shortest paths using bridging sets and rectangular matrix multiplication , volume =

    work page

  55. [55]

    Concentration of measure for the analysis of randomized algorithms , year =

    Dubhashi, Devdatt P and Panconesi, Alessandro , publisher =. Concentration of measure for the analysis of randomized algorithms , year =

    work page

  56. [56]

    2019 , publisher =

    Theory of Evolutionary Computation: Recent Developments in Discrete Optimization , author =. 2019 , publisher =

    work page 2019

  57. [57]

    Subcubic equivalences between path, matrix and triangle problems , year =

    Williams, Virginia Vassilevska and Williams, Ryan , booktitle =. Subcubic equivalences between path, matrix and triangle problems , year =

    work page

  58. [58]

    A fast deterministic detection of small pattern graphs in graphs without large cliques , volume =

    Kowaluk, Miros. A fast deterministic detection of small pattern graphs in graphs without large cliques , volume =. Theoretical Computer Science , pages =

    work page

  59. [59]

    Small-bias probability spaces: Efficient constructions and applications , year =

    Naor, Joseph and Naor, Moni , booktitle =. Small-bias probability spaces: Efficient constructions and applications , year =

    work page

  60. [60]

    Simple constructions of almost k-wise independent random variables , volume =

    Alon, Noga and Goldreich, Oded and H. Simple constructions of almost k-wise independent random variables , volume =. Random Structures & Algorithms , number =

    work page

  61. [61]

    Schulman and Aravind Srinivasan , booktitle =

    Moni Naor and Leonard J. Schulman and Aravind Srinivasan , booktitle =. Splitters and Near-optimal Derandomization , year =. doi:10.1109/SFCS.1995.492475 , url =

    work page doi:10.1109/sfcs.1995.492475 1995

  62. [62]

    Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs , volume =

    Alon, Noga and Bruck, Jehoshua and Naor, Joseph and Naor, Moni and Roth, Ron M , journal =. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs , volume =

    work page