Matrix multiplication via arithmetic progressions

On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

Behrend, F. A. (1946) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.32.12.331 · Cited by 414

Partial and Total Matrix Multiplication

Schönhage, A. (1981) · SIAM Journal on Computing · doi:10.1137/0210032 · Cited by 279

On the Asymptotic Complexity of Matrix Multiplication

Coppersmith, D., & Winograd, S. (1982) · SIAM Journal on Computing · doi:10.1137/0211038 · Cited by 221

How to Multiply Matrices Faster

(1984) · Lecture notes in computer science · doi:10.1007/3-540-13866-8 · Cited by 147

On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

Salem, R., & Spencer, D. C. (1942) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.28.12.561 · Cited by 134

Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations

Pan, V. Y. (1978) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1978.34 · Cited by 121

The asymptotic spectrum of tensors and the exponent of matrix multiplication

Strassen, V. (1986) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1986.52 · Cited by 120

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

Dell, H., & van Melkebeek, D. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806725 · Cited by 170

The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems

Silvi, P., Tschirsich, F., Gerster, M., Jünemann, J., Jaschke, D., Rizzi, M., & Montangero, S. (2019) · SciPost Physics Lecture Notes · doi:10.21468/scipostphyslectnotes.8 · Cited by 202

Triangulations

Yokohama, S. (2013) · Discrete mathematics and its applications · doi:10.1201/b16132-52 · Cited by 169

Computing Frobenius maps and factoring polynomials

Gathen, J. V. Z., & Shoup, V. (1992) · Computational Complexity · doi:10.1007/bf01272074 · Cited by 169

Algorithms for Identifying Boolean Networks and Related Biological Networks Based on Matrix Multiplication and Fingerprint Function

Akutsu, T., Miyano, S., & Kuhara, S. (2000) · Journal of Computational Biology · doi:10.1089/106652700750050817 · Cited by 169

Tight lower bounds for certain parameterized NP-hard problems

Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D. W., Kanj, I. A., & Xia, G. (2005) · Information and Computation · doi:10.1016/j.ic.2005.05.001 · Cited by 168

Algorithms in Number Theory

Lenstra, A. K., & Lenstra, H. W. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50017-5 · Cited by 168

On the complexity of matrix multiplication

Stothers, A. J. (2010) · ERA · Cited by 167

On the possibility of faster SAT algorithms

Pǎtraşcu, M., & Williams, R. (2010) · Cited by 164

Mode-seeking by Medoidshifts

Sheikh, Y. A., Khan, E. A., & Takeo Kanade, A. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408978 · Cited by 164

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

Dell, H., & van Melkebeek, D. (2014) · Journal of the ACM · doi:10.1145/2629620 · Cited by 193

Solving mazes with memristors: A massively parallel approach

Pershin, Y. V., & Ventra, M. D. (2011) · Physical Review E · doi:10.1103/physreve.84.046703 · Cited by 163

Solving linear programs in the current matrix multiplication time

Cohen, M. B., Lee, Y. T., & Song, Z. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316303 · Cited by 188

Outsourcing Large Matrix Inversion Computation to A Public Cloud

Lei, X., Liao, X., Huang, T., Li, H., & Hu, C. (2013) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2013.7 · Cited by 161

Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery

Strobl, E. V., Zhang, K., & Visweswaran, S. (2018) · Journal of Causal Inference · doi:10.1515/jci-2018-0017 · Cited by 159

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

Hoàng, C. T., Kamiński, M., Lozin, V., Sawada, J., & Shu, X. (2008) · Algorithmica · doi:10.1007/s00453-008-9197-8 · Cited by 158

Accelerating Resolution-of-the-Identity Second-Order Møller−Plesset Quantum Chemistry Calculations with Graphical Processing Units

Vogt-Maranto, L., Olivares‐Amaya, R., Kermes, S., Shao, Y., Amador‐Bedolla, C., & Aspuru‐Guzik, A. (2008) · The Journal of Physical Chemistry A · doi:10.1021/jp0776762 · Cited by 156

Faster Algorithms for Rectangular Matrix Multiplication

Gall, F. L. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.80 · Cited by 154

Improved bound for complexity of matrix multiplication

Davie, A. M., & Stothers, A. J. (2013) · Proceedings of the Royal Society of Edinburgh: Section A Mathematics · doi:10.1017/s0308210511001648 · Cited by 152

Measuring Crowd Collectiveness

Zhou, B., Tang, X., Zhang, H., & Wang, X. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2300484 · Cited by 151

Weak bisimulation for fully probabilistic processes

Christel Baier, A., & Hermanns, H. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63166-6_14 · Cited by 151

Optimal distributed all pairs shortest paths and applications

Holzer, S., & Wattenhofer, R. P. (2012) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/2332432.2332504 · Cited by 150

A cutting plane algorithm for convex programming that uses analytic centers

Atkinson, D. S., & Vaidya, P. M. (1995) · Mathematical Programming · doi:10.1007/bf01585551 · Cited by 150

Fast linear algebra is stable

Demmel, J., Dumitriu, I., & Holtz, O. (2007) · Numerische Mathematik · doi:10.1007/s00211-007-0114-x · Cited by 167

With a Little Help from My Friends (and Substitutes): Social Referents and Influence in Psychological Contract Fulfillment

Ho, V. T., & Levesque, L. L. (2005) · Organization Science · doi:10.1287/orsc.1050.0121 · Cited by 148

The Security of Hidden Field Equations (HFE)

Courtois, N. T. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45353-9_20 · Cited by 146

On the complexity of computing determinants

Kaltofen, E., & Villard, G. (2005) · Computational Complexity · doi:10.1007/s00037-004-0185-3 · Cited by 146

Fast linear algebra is stable

Demmel, J. W., Dumitriu, I., & Holtz, O. (2006) · Cited by 143

Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing

Beimel, A., Ishai, Y., & Malkin, T. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44598-6_4 · Cited by 142

Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions

Alon, N., & Naor, M. (1996) · Algorithmica · doi:10.1007/bf01940874 · Cited by 142

Rectangular Matrix Multiplication Revisited

Coppersmith, D. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0438 · Cited by 147

A direct comparison of high-speed methods for the numerical Abel transform

Hickstein, D. D., Gibson, S. T., Yurchak, R., Das, D. D., & Ryazanov, M. (2019) · Review of Scientific Instruments · doi:10.1063/1.5092635 · Cited by 141

Mind the gaps

Pan, R., & Scholz, M. (2009) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1557019.1557094 · Cited by 139

Fast Construction of Irreducible Polynomials over Finite Fields

Shoup, V. (1994) · Journal of Symbolic Computation · doi:10.1006/jsco.1994.1025 · Cited by 138

Subquadratic-time factoring of polynomials over finite fields

Kaltofen, E., & Shoup, V. (1998) · Mathematics of Computation · doi:10.1090/s0025-5718-98-00944-2 · Cited by 137

Selected topics on assignment problems

Burkard, R. E. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00343-2 · Cited by 137

Transmit Selection Diversity for Unitary Precoded Multiuser Spatial Multiplexing Systems With Linear Receivers

Chen, R., Heath, R. W., & Andrews, J. G. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.887147 · Cited by 137

Algorithms and Complexity

Grechuk, B. (2021) · Springer eBooks · doi:10.1007/978-3-030-80627-9_7 · Cited by 137

Zigzag persistent homology in matrix multiplication time

Milosavljević, N., Morozov, D., & Škraba, P. (2011) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1998196.1998229 · Cited by 153

Determinant Sums for Undirected Hamiltonicity

Björklund, A. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.24 · Cited by 135

DSP complexity of mode-division multiplexed receivers

Inan, B., Spinnler, B., Ferreira, F. M., den Borne, D. V., Lobato, A., Adhikari, S., Sleiffer, V. A. J. M., Kuschnerov, M., Hanik, N., & Jansen, S. L. (2012) · Optics Express · doi:10.1364/oe.20.010859 · Cited by 133

Subcubic Equivalences Between Path, Matrix, and Triangle Problems

Williams, V. V., & Williams, R. (2018) · Journal of the ACM · doi:10.1145/3186893 · Cited by 201

All pairs shortest paths in undirected graphs with integer weights

Shoshan, A., & Zwick, U. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814635 · Cited by 132

On the complexity of fixed parameter clique and dominating set

Eisenbrand, F., & Grandoni, F. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.009 · Cited by 131

Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor

Gall, F. L., & Urrutia, F. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975031.67 · Cited by 156

Data science applications to string theory

Ruehle, F. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.09.005 · Cited by 140

Near optimal algorithms for computing Smith normal forms of integer matrices

Storjohann, A. (1996) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/236869.237084 · Cited by 127

Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

Karger, D. R., Koller, D., & Phillips, S. J. (1993) · SIAM Journal on Computing · doi:10.1137/0222071 · Cited by 127

Reachability is harder for directed than for undirected finite graphs

Ajtai, M., & Fagin, R. (1990) · Journal of Symbolic Logic · doi:10.2307/2274958 · Cited by 127

On Dynamic Shortest Paths Problems

Roditty, L., & Zwick, U. (2010) · Algorithmica · doi:10.1007/s00453-010-9401-5 · Cited by 126

Matrix Representation of Solution Concepts in Multiple-Decision-Maker Graph Models

Xu, H., Hipel, K. W., & Kilgour, D. M. (2008) · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · doi:10.1109/tsmca.2009.2007994 · Cited by 125

Fast context-free grammar parsing requires fast boolean matrix multiplication

Lee, L. (2002) · Journal of the ACM · doi:10.1145/505241.505242 · Cited by 139

Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Iliopoulos, C. S. (1989) · SIAM Journal on Computing · doi:10.1137/0218045 · Cited by 121

C−+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai

Patarin, J., Goubin, L., & Courtois, N. T. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49649-1_4 · Cited by 117

Algorithmic Aspects of Triangle-Based Network Analysis

Schank, T. (2007) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000007159 · Cited by 118

Networks Cannot Compute Their Diameter in Sublinear Time

Frischknecht, S., Holzer, S., & Wattenhofer, R. P. (2012) · Cited by 115

On the complexity of the F 5 Gröbner basis algorithm

Bardet, M., Faugère, J., & Salvy, B. (2014) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2014.09.025 · Cited by 113

Faster Subtree Isomorphism

Ron Shamir, A., & Tsur, D. (1999) · Journal of Algorithms · doi:10.1006/jagm.1999.1044 · Cited by 113

Structural Intervention Distance for Evaluating Causal Graphs

Peters, J., & Bühlmann, P. (2015) · Neural Computation · doi:10.1162/neco_a_00708 · Cited by 112

Determinant Sums for Undirected Hamiltonicity

Björklund, A. (2014) · SIAM Journal on Computing · doi:10.1137/110839229 · Cited by 111

Computing Maximum Flow with Augmenting Electrical Flows

Mądry, A. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.70 · Cited by 109

Linear FPT reductions and computational lower bounds

Chen, J., Huang, X., Kanj, I. A., & Xia, G. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007391 · Cited by 109

Computing dominances in En

Matoušek, J. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90071-o · Cited by 109

Boolean grammars

Okhotin, A. (2004) · Information and Computation · doi:10.1016/j.ic.2004.03.006 · Cited by 109

Asymptotically Fast Triangularization of Matrices over Rings

Hafner, J. L., & McCurley, K. S. (1991) · SIAM Journal on Computing · doi:10.1137/0220067 · Cited by 107

Accidental Algorthims

Valiant, L. G. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.7 · Cited by 117

Highly predictive blacklisting

Zhang, J., Porras, P. A., & Ullrich, J. (2008) · Cited by 106

Solving path problems on the GPU

Buluç, A., Gilbert, J. R., & Budak, C. (2009) · Parallel Computing · doi:10.1016/j.parco.2009.12.002 · Cited by 110

Grad and classes with bounded expansion II. Algorithmic aspects

Nešetřil, J., & de Mendez, P. O. (2007) · European Journal of Combinatorics · doi:10.1016/j.ejc.2006.07.014 · Cited by 106

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

Serra‐Capizzano, S. (1994) · BIT Numerical Mathematics · doi:10.1007/bf01934269 · Cited by 106

Compressed matrix multiplication

Pagh, R. (2013) · ACM Transactions on Computation Theory · doi:10.1145/2493252.2493254 · Cited by 105

2006, Quantum verification of matrix products

Buhrman, H., & Špalek, R. (2004) · UvA-DARE (University of Amsterdam) · Cited by 105

A Group-theoretic Approach to Fast Matrix MultiplicationPreprint

Cohn, H., & Umans, C. (2003) · Cited by 105

A generative model of whole-brain effective connectivity

Frässle, S., Lomakina, E. I., Kasper, L., Manjaly, Z. M., Leff, A. P., Pruessmann, K. P., Buhmann, J. M., & Stephan, K. E. (2018) · NeuroImage · doi:10.1016/j.neuroimage.2018.05.058 · Cited by 104

On Dynamic Shortest Paths Problems

Roditty, L., & Zwick, U. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30140-0_52 · Cited by 103

On the Bayes-optimality of F-measure maximizers

Waegeman, W., Dembczyńki, K., Jachnik, A., Cheng, W., & Hüllermeier, E. (2013) · Open access LMU (Ludwid Maxmilian's Universitat Munchen) · doi:10.48550/arxiv.1310.4849 · Cited by 102

A hybrid model using fuzzy logic and an extreme learning machine with vector particle swarm optimization for wireless sensor network localization

Phoemphon, S., So–In, C., & Niyato, D. T. (2018) · Applied Soft Computing · doi:10.1016/j.asoc.2018.01.004 · Cited by 102

A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph

Duke, R. A., Lefmann, H., & Rödl, V. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793247634 · Cited by 102

A subdivision-based algorithm for the sparse resultant

Canny, J., & Emiris, I. Z. (2000) · Journal of the ACM · doi:10.1145/337244.337247 · Cited by 101

On the all-pairs-shortest-path problem

Seidel, R. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129784 · Cited by 101

Fusion of Multispectral and Panchromatic Images Using a Restoration-Based Method

Li, Z., & Leung, H. (2008) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2008.2005639 · Cited by 100

Finding, minimizing, and counting weighted subgraphs

Williams, V. V., & Williams, R. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536477 · Cited by 99

Geometry and Complexity Theory

Landsberg, J. M. (2017) · Cambridge University Press eBooks · doi:10.1017/9781108183192 · Cited by 120

Algebraic Attacks on Combiners with Memory and Several Outputs

Courtois, N. T. (2005) · Lecture notes in computer science · doi:10.1007/11496618_3 · Cited by 99

Nearly Optimal Algorithms for Canonical Matrix Forms

Giesbrecht, M. W. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793252687 · Cited by 99

Factoring Polynomials Over Finite Fields: A Survey

Gathen, J. V. Z., & Panario, D. (2001) · Journal of Symbolic Computation · doi:10.1006/jsco.1999.1002 · Cited by 98

Chip-firing games, potential theory on graphs, and spanning trees

Baker, M. H., & Shokrieh, F. (2012) · Journal of Combinatorial Theory Series A · doi:10.1016/j.jcta.2012.07.011 · Cited by 97

Tensor Rank and Stochastic Entanglement Catalysis for Multipartite Pure States

Chen, L., Chitambar, E., Duan, R., Ji, Z., & Winter, A. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.200501 · Cited by 98

Cover times, blanket times, and majorizing measures

Ding, J., Lee, J., & Peres, Y. (2012) · Annals of Mathematics · doi:10.4007/annals.2012.175.3.8 · Cited by 96

Fully dynamic all pairs shortest paths with real edge weights

Demetrescu, C., & Italiano, G. F. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.005 · Cited by 96

Parameterized Complexity of Cardinality Constrained Optimization Problems

Cai, L. (2007) · The Computer Journal · doi:10.1093/comjnl/bxm086 · Cited by 95

Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers

Lecerf, G. (2003) · Journal of Complexity · doi:10.1016/s0885-064x(03)00031-1 · Cited by 95

Improved algorithms for isomorphisms of polynomials

Patarin, J., Goubin, L., & Courtois, N. T. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054126 · Cited by 94

On the complexity of solving quadratic Boolean systems

Bardet, M., Faugère, J., Salvy, B., & Spaenlehauer, P.-J. (2012) · Journal of Complexity · doi:10.1016/j.jco.2012.07.001 · Cited by 94

Fast and processor efficient parallel matrix multiplication algorithms on a linear array with a reconfigurable pipelined bus system

Li, K., Pan, Y. F., & Zheng, S. (1998) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.706044 · Cited by 94

An Exact Algorithm for F-Measure Maximization

Dembczyński, K., Waegeman, W., Cheng, W., & Hüllermeier, E. (2011) · Ghent University Academic Bibliography (Ghent University) · Cited by 93

The bilinear complexity and practical algorithms for matrix multiplication

Smirnov, A. V. (2013) · Computational Mathematics and Mathematical Physics · doi:10.1134/s0965542513120129 · Cited by 104

An efficient MapReduce algorithm for counting triangles in a very large graph

Park, H.-M., & Chung, C. (2013) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2505515.2505563 · Cited by 96

Evolutionary Approaches To Minimizing Network Coding Resources

Kim, M., Médard, M., Aggarwal, V., O’Reilly, U.-M., Kim, W. B., Ahn, C. W., & Effros, M. (2007) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2007.231 · Cited by 92

A Novel Fast and Flexible Holomorphic Embedding Power Flow Method

Chiang, H., Wang, T., & Sheng, H. (2017) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2017.2750711 · Cited by 91

Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplications

Pan, V. Y. (1979) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1979.17 · Cited by 43

Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication

Pan, V. Y. (1982) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(82)90037-2 · Cited by 33

The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations

Pan, V. Y. (1984) · Theoretical Computer Science · doi:10.1016/0304-3975(84)90107-5 · Cited by 4

Fast matrix multiplication without APA-algorithms

Pan, V. Y. (1982) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(82)90029-3 · Cited by 6

Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations

Pan, V. Y. (1978) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1978.34 · Cited by 121