Beating Trivial Time for Tricky Triangle Tasks

Neha Pant; Ryan Williams

arxiv: 2606.27727 · v1 · pith:EHWIEU3Ynew · submitted 2026-06-26 · 💻 cs.DS · cs.CC

Beating Trivial Time for Tricky Triangle Tasks

Neha Pant , Ryan Williams This is my paper

Pith reviewed 2026-06-29 02:39 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords triangle detectionword RAMsparse graphsexact triangle4-cycle detectionAC0 circuitsfine-grained complexity

0 comments

The pith

New algorithms improve on the trivial running times for sparse triangle and exact triangle problems in the Word RAM model.

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

The paper shows that All-Edges Sparse Triangle, Sparse Monochromatic Triangle, and Exact Triangle all admit algorithms faster than their previously optimal-seeming trivial bounds. These problems arise in graph analysis where nodes have limited degree or edges carry weights, and the trivial approach simply enumerates possible triples. The speedups rely on importing ideas from randomized algorithms, circuit complexity, and communication complexity, all realized with only basic AC0 word operations. This challenges the idea that fine-grained conjectures like 3SUM force the naive time bound to be tight in the standard RAM model. The same methods also yield an o(n²) algorithm for 4-cycle detection under a mild word-size assumption and an AC0-based sorting routine.

Core claim

We present the first improvements over the trivial algorithms for each of these problems in the Word RAM model. Moreover, our algorithms can be implemented with only polysize AC0 operations on words. Extending our techniques, we also show how to solve the notorious 4-cycle detection problem on n-node graphs in o(n²) time, in a Word-RAM model with word size w > ω(log² n). Along the way, we show how to sort n items over a universe of size 2^u using only AC0 word operations in O(n u log n)/w time.

What carries the argument

Transfer of randomized-algorithm, circuit-complexity, and communication-complexity techniques to produce sub-trivial time bounds for the listed triangle enumeration tasks.

If this is right

All-Edges Sparse Triangle on n^δ-degree graphs runs in time strictly better than the previous trivial bound.
Sparse Monochromatic Triangle and Exact Triangle likewise receive improved Word-RAM algorithms.
4-cycle detection on n-node graphs runs in o(n²) time whenever the word size exceeds ω(log² n).
n numbers drawn from a 2^u universe can be sorted using only AC0 word operations in O(n u log n / w) time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the technique transfer succeeds here, similar transfers may improve other problems whose hardness was previously tied only to 3SUM in weaker models.
The restriction to polysize AC0 operations indicates that the speedups do not require heavy arithmetic or branching, which could simplify implementation.
The 4-cycle result suggests the same toolkit may apply to other small-subgraph detection tasks once word size is taken into account.
These Word-RAM improvements highlight a possible gap between combinatorial algorithms assumed in some fine-grained conjectures and what elementary circuit operations actually permit.

Load-bearing premise

That techniques from randomized algorithms, circuit complexity, and communication complexity can be adapted directly to produce faster Word-RAM algorithms for these triangle problems.

What would settle it

An explicit construction of a degree-n^δ graph family on which the new algorithm for All-Edges Sparse Triangle fails to beat the trivial O(m^{3/2}) bound, or a formal proof that the AC0 word operations cannot achieve the claimed improvement.

read the original abstract

For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-grained conjectures. For example, All-Edges Sparse Triangle and Sparse Monochromatic Triangle where each node has degree $n^{\delta}$ for some $\delta < 1$, and the Exact Triangle where edges have arbitrary weights, all have this property under the 3SUM Conjecture. However, as there are slightly nontrivial algorithms for 3SUM, it is natural to wonder if the trivial algorithm for these tricky triangle tasks might also be improved. Applying a variety of techniques from randomized algorithms, circuit complexity, and communication complexity, we present the first improvements over the trivial algorithms for each of these problems in the Word RAM model. Moreover, our algorithms can be implemented with only polysize $AC0$ operations on words. Extending our techniques, we also show how to solve the notorious 4-cycle detection problem on $n$-node graphs in $o(n^2)$ time, in a Word-RAM model with word size $w > \omega(\log^2 n)$. Along the way, we show how to sort $n$ items over a universe of size $2^u$ using only $AC0$ word operations in $O(n u \log n)/w$ time.

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.

Desk Editor's Note private letter to a colleague

The paper gives the first sub-trivial algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, Exact Triangle, and 4-cycle detection using transfers from randomized algorithms, circuit complexity, and communication complexity, all in Word RAM with polysize AC0 operations.

read the letter

The core contribution is concrete: they improve the trivial bounds on those three triangle problems that looked stuck under 3SUM-style conjectures, and they get 4-cycle detection in o(n^2) time once the word size exceeds omega(log^2 n). They also include an AC0 sorting routine for n items over a 2^u universe that runs in O(n u log n / w) time. These are the first claimed improvements, and the AC0 restriction is a clean extra property.

The work is strongest on the technique transfer itself. Taking ideas from other areas and making them work for these specific graph problems in the Word RAM model is the real step. The sorting subroutine looks reusable on its own.

The main limitation is the word-size assumption for the 4-cycle result; it is not the standard log n word model, so the result sits in a slightly stronger setting. The triangle improvements appear to hold in the usual model. No obvious circularity or model mismatch shows up in the claims.

This is for people who follow fine-grained graph algorithms and conditional lower bounds. Anyone working on subquadratic or sub-cubic graph problems will want to see the details. It is worth sending to peer review because the statements are precise, the authors have a record on this style of result, and the improvements would matter if the proofs hold.

Referee Report

0 major / 1 minor

Summary. The manuscript claims the first improvements over trivial enumeration algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, and Exact Triangle (each with node degrees n^δ for δ<1 or arbitrary edge weights) in the Word RAM model, obtained by transferring techniques from randomized algorithms, circuit complexity, and communication complexity. The algorithms are further restricted to polysize AC0 word operations. The work extends the approach to obtain an o(n²)-time algorithm for 4-cycle detection when the word size w satisfies w > ω(log² n). As a byproduct, it gives an AC0 sorting algorithm for n items from a universe of size 2^u running in O(n u log n / w) time.

Significance. If the central claims are correct, the results are significant for fine-grained complexity: they show that the optimality of trivial algorithms for these triangle problems (previously supported by 3SUM-based lower bounds) can be circumvented, and they supply new Word-RAM algorithms whose only non-trivial operations lie in AC0. The 4-cycle improvement addresses a well-known open question, and the sorting subroutine may be of independent interest for circuit-based algorithm design.

minor comments (1)

[Abstract] The abstract states that the algorithms 'can be implemented with only polysize AC0 operations on words' but does not define 'polysize' or the precise word-RAM variant used; a short clarifying sentence would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for noting its potential significance for fine-grained complexity and Word-RAM algorithms with AC0 operations. The recommendation is listed as uncertain, but the report contains no specific major comments to address. We stand by the correctness of the central claims and are happy to supply any additional clarifications, full proofs, or implementation details upon request.

Circularity Check

0 steps flagged

No significant circularity; derivation applies external techniques

full rationale

The paper's central claim is that techniques from randomized algorithms, circuit complexity, and communication complexity (external to the present work) yield the first improvements over trivial algorithms for the listed triangle problems in the Word RAM model. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided abstract or description. The derivation chain is presented as a transfer of independent prior results rather than a reduction to the paper's own inputs. This is the expected non-finding for an applications paper whose improvements rest on cross-area transfer.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract relies on standard models and conjectures from prior literature without introducing new free parameters or entities.

axioms (2)

domain assumption Standard Word RAM model
The algorithms are presented in the Word RAM model as stated in the abstract.
domain assumption Existence of slightly nontrivial 3SUM algorithms
Mentioned as motivation for wondering if triangle tasks can be improved.

pith-pipeline@v0.9.1-grok · 5768 in / 1125 out tokens · 58226 ms · 2026-06-29T02:39:12.516980+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

[1]

Hendrych, M

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. FSTTCS.2023.25, doi:10.4230/LIPIcs.FSTTCS.2023.25. 3 Miklós Ajtai, János Komlós, and Endre Szemerédi. Sorting in c log n parallel steps.Comb., 3(1):1–19, 1983.doi:10.1007/BF02579338. 4 Susanne Albers and Torben Hagerup. Improved parallel int...

work page doi:10.4230/lipics 2023
[2]

5 Noga Alon, Raphael Yuster, and Uri Zwick

URL:https://doi.org/10.1006/inco.1997.2632, doi:10.1006/INCO.1997.2632. 5 Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.J. ACM, 42(4):844–856,

work page doi:10.1006/inco.1997.2632 1997
[3]

6 Noga Alon, Raphael Yuster, and Uri Zwick

doi:10.1145/210332.210337. 6 Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189. 7 Arne Andersson, Peter Bro Miltersen, and Mikkel Thorup. Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. , 215(1-2):337–344, 1999.doi:10.1016/ S0304-3975...

work page doi:10.1145/210332.210337 1997
[4]

9 Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen

URL:https://doi.org/10.1007/s00453-007-9036-3, doi:10.1007/S00453-007-9036-3. 9 Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen. Expected linear time sorting for word sizeω(log2n log logn). In Scandinavian Workshop on Algorithm Theory , pages 26–37. Springer,

work page doi:10.1007/s00453-007-9036-3
[5]

Fast evaluation of union-intersection expressions

10 Philip Bille, Anna Pagh, and Rasmus Pagh. Fast evaluation of union-intersection expressions. In Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, volume 4835 ofLecture Notes in Computer Science , pages 739–750. Springer, 2007.doi:10.1007/978-3-540-77120-3\_64. 11 J.A Bondy and M Simo...

work page doi:10.1007/978-3-540-77120-3 2007
[6]

12 William G Brown

URL: https://www.sciencedirect.com/science/ article/pii/0095895674900525, doi:10.1016/0095-8956(74)90052-5. 12 William G Brown. On graphs that do not contain a Thomsen graph.Canadian Mathematical Bulletin, 9(3):281–285,

work page doi:10.1016/0095-8956(74)90052-5
[7]

13 Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs.SIAM J. Comput., 39(5):2075–2089, 2010.doi:10.1137/08071990X. 14 Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real apsp, real 3sum, and OV. In STOC ’22: 54th Annual ACM...

work page doi:10.1137/08071990x 2075
[8]

URL:https://doi.org/10.1016/j.tcs.2010.06.002, doi: 10.1016/J.TCS.2010.06.002. N. Pant and R. Williams 8:23 18 Anirban Dasgupta, Ravi Kumar, and D Sivakumar. Sparse and lopsided set disjointness via information theory. InInternational Workshop on Approximation Algorithms for Combinatorial Optimization, pages 517–528. Springer,

work page doi:10.1016/j.tcs.2010.06.002 2010
[9]

20 DavidEppstein, MichaelT.Goodrich, MichaelMitzenmacher, andManuelR.Torres

URL:http://www.vldb.org/pvldb/vol4/p255-ding.pdf, doi: 10.14778/1938545.1938550. 20 DavidEppstein, MichaelT.Goodrich, MichaelMitzenmacher, andManuelR.Torres. 2-3cuckoo filters for faster triangle listing and set intersection. InProceedings of the 36th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14...

work page doi:10.14778/1938545.1938550 2017
[10]

23 Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi

doi:10.1007/BF02579292. 23 Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi. Lower bounds for external memory integer sorting via network coding. SIAM J. Com- put., 52(on):STOC19–87–STOC19–111,

work page doi:10.1007/bf02579292
[11]

24 Michael L

URL:https://doi.org/10.1137/20m1321887, doi:10.1137/20M1321887. 24 Michael L. Fredman. New bounds on the complexity of the shortest path problem.SIAM J. Comput., 5(1):83–89, 1976.doi:10.1137/0205006. 25 Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. , 47(3):424–436, December

work page doi:10.1137/20m1321887 1976
[12]

26 Allan Grønlund and Seth Pettie

doi:10.1016/ 0022-0000(93)90040-4. 26 Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM, 65(4):22:1–22:25, 2018.doi:10.1145/3185378. 27 Torben Hagerup. Simpler and faster dictionaries on the AC0 RAM. InAutomata, Languages and Programming, 25th International Colloquium, ICALP’98, Aalborg, Denmark, July 13-17, 1998, Proceed...

work page doi:10.1145/3185378 2018
[13]

28 Ce Jin and Yinzhan Xu

URL: https://doi.org/10.1007/BFb0055042, doi:10.1007/BFB0055042. 28 Ce Jin and Yinzhan Xu. Removing additive structure in 3sum-based reductions. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 405–418. ACM, 2023.doi:10.1145/3564246.3585157. 29 Tsvi Kopelowitz, Seth Pettie, and El...

work page doi:10.1007/bfb0055042 2023
[14]

30 Zongpeng Li and Baochun Li

doi:10.1007/978-3-319-21840-3\_39. 30 Zongpeng Li and Baochun Li. Network coding: The case of multiple unicast sessions.Proceed- ings of the 42nd Allerton Annual Conference on Communication, Control, and Computing , 10

work page doi:10.1007/978-3-319-21840-3
[15]

Monochromatic triangles, intermediate matrix products, and convolutions

31 Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA , volume 151 of LIPIcs, pages 53:1–53:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2020
[16]

32 Mihai Pătraşcu

URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.53, doi:10.4230/LIPICS.ITCS.2020.53. 32 Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. InProceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 603–610. ACM, 2010.doi:10.1145/1806689.1806772. 33 Dana Richards and Arth...

work page doi:10.4230/lipics.itcs.2020.53 2020
[17]

Schmidt, Alan Siegel, and Aravind Srinivasan

34 Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence.SIAM J. Discret. Math. , 8(2):223–250, 1995.doi: 10.1137/S089548019223872X. MFCS 2026 8:24 Beating Trivial Time for Tricky Triangle Tasks 35 Larry J. Stockmeyer and Uzi Vishkin. Simulation of parallel random access machines by ...

work page doi:10.1137/s089548019223872x 1995
[18]

37 Virginia Vassilevska Williams and R

doi:10.1145/1798596.1798597. 37 Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5):27:1–27:38, 2018.doi:10.1145/3186893. 38 Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. , 42(3):831–854, 2013.doi:10.1137...

work page doi:10.1145/1798596.1798597 2018

[1] [1]

Hendrych, M

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. FSTTCS.2023.25, doi:10.4230/LIPIcs.FSTTCS.2023.25. 3 Miklós Ajtai, János Komlós, and Endre Szemerédi. Sorting in c log n parallel steps.Comb., 3(1):1–19, 1983.doi:10.1007/BF02579338. 4 Susanne Albers and Torben Hagerup. Improved parallel int...

work page doi:10.4230/lipics 2023

[2] [2]

5 Noga Alon, Raphael Yuster, and Uri Zwick

URL:https://doi.org/10.1006/inco.1997.2632, doi:10.1006/INCO.1997.2632. 5 Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.J. ACM, 42(4):844–856,

work page doi:10.1006/inco.1997.2632 1997

[3] [3]

6 Noga Alon, Raphael Yuster, and Uri Zwick

doi:10.1145/210332.210337. 6 Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997.doi:10.1007/BF02523189. 7 Arne Andersson, Peter Bro Miltersen, and Mikkel Thorup. Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. , 215(1-2):337–344, 1999.doi:10.1016/ S0304-3975...

work page doi:10.1145/210332.210337 1997

[4] [4]

9 Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen

URL:https://doi.org/10.1007/s00453-007-9036-3, doi:10.1007/S00453-007-9036-3. 9 Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen. Expected linear time sorting for word sizeω(log2n log logn). In Scandinavian Workshop on Algorithm Theory , pages 26–37. Springer,

work page doi:10.1007/s00453-007-9036-3

[5] [5]

Fast evaluation of union-intersection expressions

10 Philip Bille, Anna Pagh, and Rasmus Pagh. Fast evaluation of union-intersection expressions. In Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, volume 4835 ofLecture Notes in Computer Science , pages 739–750. Springer, 2007.doi:10.1007/978-3-540-77120-3\_64. 11 J.A Bondy and M Simo...

work page doi:10.1007/978-3-540-77120-3 2007

[6] [6]

12 William G Brown

URL: https://www.sciencedirect.com/science/ article/pii/0095895674900525, doi:10.1016/0095-8956(74)90052-5. 12 William G Brown. On graphs that do not contain a Thomsen graph.Canadian Mathematical Bulletin, 9(3):281–285,

work page doi:10.1016/0095-8956(74)90052-5

[7] [7]

13 Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs.SIAM J. Comput., 39(5):2075–2089, 2010.doi:10.1137/08071990X. 14 Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real apsp, real 3sum, and OV. In STOC ’22: 54th Annual ACM...

work page doi:10.1137/08071990x 2075

[8] [8]

URL:https://doi.org/10.1016/j.tcs.2010.06.002, doi: 10.1016/J.TCS.2010.06.002. N. Pant and R. Williams 8:23 18 Anirban Dasgupta, Ravi Kumar, and D Sivakumar. Sparse and lopsided set disjointness via information theory. InInternational Workshop on Approximation Algorithms for Combinatorial Optimization, pages 517–528. Springer,

work page doi:10.1016/j.tcs.2010.06.002 2010

[9] [9]

20 DavidEppstein, MichaelT.Goodrich, MichaelMitzenmacher, andManuelR.Torres

URL:http://www.vldb.org/pvldb/vol4/p255-ding.pdf, doi: 10.14778/1938545.1938550. 20 DavidEppstein, MichaelT.Goodrich, MichaelMitzenmacher, andManuelR.Torres. 2-3cuckoo filters for faster triangle listing and set intersection. InProceedings of the 36th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14...

work page doi:10.14778/1938545.1938550 2017

[10] [10]

23 Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi

doi:10.1007/BF02579292. 23 Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi. Lower bounds for external memory integer sorting via network coding. SIAM J. Com- put., 52(on):STOC19–87–STOC19–111,

work page doi:10.1007/bf02579292

[11] [11]

24 Michael L

URL:https://doi.org/10.1137/20m1321887, doi:10.1137/20M1321887. 24 Michael L. Fredman. New bounds on the complexity of the shortest path problem.SIAM J. Comput., 5(1):83–89, 1976.doi:10.1137/0205006. 25 Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. , 47(3):424–436, December

work page doi:10.1137/20m1321887 1976

[12] [12]

26 Allan Grønlund and Seth Pettie

doi:10.1016/ 0022-0000(93)90040-4. 26 Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM, 65(4):22:1–22:25, 2018.doi:10.1145/3185378. 27 Torben Hagerup. Simpler and faster dictionaries on the AC0 RAM. InAutomata, Languages and Programming, 25th International Colloquium, ICALP’98, Aalborg, Denmark, July 13-17, 1998, Proceed...

work page doi:10.1145/3185378 2018

[13] [13]

28 Ce Jin and Yinzhan Xu

URL: https://doi.org/10.1007/BFb0055042, doi:10.1007/BFB0055042. 28 Ce Jin and Yinzhan Xu. Removing additive structure in 3sum-based reductions. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 405–418. ACM, 2023.doi:10.1145/3564246.3585157. 29 Tsvi Kopelowitz, Seth Pettie, and El...

work page doi:10.1007/bfb0055042 2023

[14] [14]

30 Zongpeng Li and Baochun Li

doi:10.1007/978-3-319-21840-3\_39. 30 Zongpeng Li and Baochun Li. Network coding: The case of multiple unicast sessions.Proceed- ings of the 42nd Allerton Annual Conference on Communication, Control, and Computing , 10

work page doi:10.1007/978-3-319-21840-3

[15] [15]

Monochromatic triangles, intermediate matrix products, and convolutions

31 Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA , volume 151 of LIPIcs, pages 53:1–53:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2020

[16] [16]

32 Mihai Pătraşcu

URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.53, doi:10.4230/LIPICS.ITCS.2020.53. 32 Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. InProceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 603–610. ACM, 2010.doi:10.1145/1806689.1806772. 33 Dana Richards and Arth...

work page doi:10.4230/lipics.itcs.2020.53 2020

[17] [17]

Schmidt, Alan Siegel, and Aravind Srinivasan

34 Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence.SIAM J. Discret. Math. , 8(2):223–250, 1995.doi: 10.1137/S089548019223872X. MFCS 2026 8:24 Beating Trivial Time for Tricky Triangle Tasks 35 Larry J. Stockmeyer and Uzi Vishkin. Simulation of parallel random access machines by ...

work page doi:10.1137/s089548019223872x 1995

[18] [18]

37 Virginia Vassilevska Williams and R

doi:10.1145/1798596.1798597. 37 Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5):27:1–27:38, 2018.doi:10.1145/3186893. 38 Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. , 42(3):831–854, 2013.doi:10.1137...

work page doi:10.1145/1798596.1798597 2018