 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources4
 Resource Type

04000000000
 More
 Availability

04
 Author / Contributor
 Filter by Author / Creator


Vassilevska_Williams, Virginia (4)

Xu, Yinzhan (2)

CensorHillel, Keren (1)

Dalirrooyfard, Mina (1)

Dory, Michal (1)

Even, Tomer (1)

Forster, Sebastian (1)

Kirkpatrick, Yael (1)

Mathialagan, Surya (1)

Nazari, Yasamin (1)

Xu, Zixuan (1)

Zhou, Renfei (1)

de_Vos, Tijn (1)

#Tyler Phillips, Kenneth E. (0)

#Willis, Ciara (0)

& AbreuRamos, E. D. (0)

& Abramson, C. I. (0)

& AbreuRamos, E. D. (0)

& Adams, S.G. (0)

& Ahmed, K. (0)

 Filter by Editor


Bringmann, Karl (1)

Grohe, Martin (1)

Puppis, Gabriele (1)

Svensson, Ola (1)

& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Brennan K. (0)

& Brennan, K. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Ferretti, F. (0)

& Higgins, A. (0)

& J. Peters (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available June 10, 2025

Vassilevska_Williams, Virginia ; Xu, Yinzhan ; Xu, Zixuan ; Zhou, Renfei ( , Proceedings of the 2024 Annual ACMSIAM Symposium on Discrete Algorithms (SODA))The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018]. In particular, the new bound on ω is ω ≤ 2.371552 (improved from ω ≤ 2.371866). For the dual matrix multiplication exponent α defined as the largest α for which ω(1, α, 1) = 2, we obtain the improvement α ≥ 0.321334 (improved from α ≥ 0.31389). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.more » « lessFree, publiclyaccessible full text available June 1, 2025

Dory, Michal ; Forster, Sebastian ; Kirkpatrick, Yael ; Nazari, Yasamin ; Vassilevska_Williams, Virginia ; de_Vos, Tijn ( , Proceedings of the 2024 Annual ACMSIAM Symposium on Discrete Algorithms (SODA))Free, publiclyaccessible full text available June 1, 2025

CensorHillel, Keren ; Even, Tomer ; Vassilevska_Williams, Virginia ( , Schloss Dagstuhl – LeibnizZentrum für Informatik)Bringmann, Karl ; Grohe, Martin ; Puppis, Gabriele ; Svensson, Ola (Ed.)We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)approximation in Õ(n^ω/t^{ω2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)approximation algorithms for the number of hcycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h2)},n)), the time to multiply n × n/(t^{1/(h2)}) by n/(t^{1/(h2)) × n matrices. Finally, we show that under popular finegrained hypotheses, this running time is optimal.more » « lessFree, publiclyaccessible full text available January 1, 2025