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

On the power of BFS to determine a graph's diameter

Corneil, D. G., Dragan, F. F., & Köhler, E. (2003) · Networks · doi:10.1002/net.10098 · Cited by 34

Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree

Xiao, J., Liu, L., Xia, L., & Jiang, T. (2007) · doi:10.5555/1283383.1283454 · Cited by 34

Generalized matrix inversion is not harder than matrix multiplication

Petković, M. D., & Stanimirović, P. S. (2008) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2008.11.012 · Cited by 35

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

Andrzej Lingas, B. (2010) · Algorithmica · doi:10.1007/s00453-010-9441-x · Cited by 34

A Fully Dynamic Algorithm for Maintaining the Transitive Closure

King, V., & Sagert, G. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2002.1883 · Cited by 41

Tree-adjoining grammar parsing and boolean matrix multiplication

Satta, G. (1994) · Cited by 34

Fast polynomial factorization and modular composition in small characteristic

Umans, C. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374445 · Cited by 33

Social Influence Based Clustering and Optimization over Heterogeneous Information Networks

Zhou, Y., & Liu, L. (2015) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2717314 · Cited by 33

Learning Transferable Subspace for Human Motion Segmentation

Wang, L., Ding, Z., & Fu, Y. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11824 · Cited by 33

Fast Sparse Matrix Multiplication

Yuster, R., & Zwick, U. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30140-0_54 · Cited by 33

Fast matrix multiplication using coherent configurations

Cohn, H., & Umans, C. (2013) · Cited by 33

Finding a maximum weight triangle in n 3-Δ time, with applications

Williams, V. V., & Williams, R. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132550 · Cited by 33

On reducing computational overhead in multi-objective genetic Takagi–Sugeno fuzzy systems

Cococcioni, M., Lazzerini, B., & Marcelloni, F. (2009) · Applied Soft Computing · doi:10.1016/j.asoc.2009.12.028 · Cited by 33

Efficient transitive closure of sparse matrices over closed semirings

Penn, G. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.11.008 · Cited by 34

Probabilistic local reconstruction for k-NN regression and its application to virtual metrology in semiconductor manufacturing

Lee, S.-K., Kang, P., & Cho, S. (2013) · Neurocomputing · doi:10.1016/j.neucom.2013.10.001 · Cited by 33

Randomized low‐rank approximation methods for projection‐based model order reduction of large nonlinear dynamical problems

Bach, C., Ceglia, D., Song, L., & Duddeck, F. M. E. (2018) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.6009 · Cited by 38

Computing Popov and Hermite forms of polynomial matrices

Villard, G. (1996) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/236869.237082 · Cited by 33

Algebraic Structures and Algorithms for Matching and Matroid Problems

Harvey, N. J. A. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.8 · Cited by 33

A Hidden Markov Technique for Haplotype Reconstruction

Rastas, P. M. A., Koivisto, M., Mannila, H., & Ukkonen, E. (2005) · Lecture notes in computer science · doi:10.1007/11557067_12 · Cited by 33

A Complete Implementation for Computing General Dimensional Convex Hulls

Emiris, I. Z. (1998) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195998000126 · Cited by 33

Fast computation of the Smith normal form of an integer matrix

Giesbrecht, M. W. (1995) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/220346.220361 · Cited by 33

Average-case complexity of detecting cliques

Sudan, M., & Rossman, B. (2010) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 33

Reachability and Termination Analysis of Concurrent Quantum Programs

Yu, N., & Ying, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32940-1_7 · Cited by 32

Giga-scale exhaustive points-to analysis for Java in under a minute

Dietrich, J. B., Hollingum, N., & Scholz, B. (2015) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2814270.2814307 · Cited by 33

Scalable Inference of Ordinary Differential Equation Models of Biochemical Processes

Fröhlich, F., Loos, C., & Hasenauer, J. (2018) · Methods in molecular biology · doi:10.1007/978-1-4939-8882-2_16 · Cited by 32

Coded Computing for Resilient, Secure, and Privacy-Preserving Distributed Matrix Multiplication

Yu, Q., & Avestimehr, A. S. (2020) · IEEE Transactions on Communications · doi:10.1109/tcomm.2020.3032196 · Cited by 33

Faster Algorithms on Branch and Clique Decompositions

Bodlaender, H. L., van Leeuwen, E. J., van Rooij, J. M. M., & Vatshelle, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15155-2_17 · Cited by 36

Successive matrix squaring algorithm for computing the Drazin inverse

Wei, Y. (2000) · Applied Mathematics and Computation · doi:10.1016/s0096-3003(98)10118-2 · Cited by 32

Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations

Chowdhury, M. F. I., Jeannerod, C.-P., Neiger, V., Schost, É., & Villard, G. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2416068 · Cited by 32

A 5/2n/sup 2/-lower bound for the rank of n×n-matrix multiplication over arbitrary fields

Bläser, M. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814576 · Cited by 32

How to use the minimal separators of a graph for its chordal triangulation

Parra, A., & Scheffler, P. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60084-1_68 · Cited by 32

On Exact Algebraic [Non-]Immunity of S-Boxes Based on Power Functions

Courtois, N. T., Debraize, B., & Garrido, E. (2006) · Lecture notes in computer science · doi:10.1007/11780656_7 · Cited by 32

Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory

Cheriyan, J. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539793256223 · Cited by 32

Exponentiation in finite fields: Theory and practice

Gathen, J. V. Z., & Nöcker, M. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63163-1_8 · Cited by 32

Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition

Cohen, E. (1996) · Journal of Algorithms · doi:10.1006/jagm.1996.0048 · Cited by 32

Efficient approximate solution of sparse linear systems

Reif, J. H. (1998) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(98)00191-6 · Cited by 32

The algorithmic aspects of the regularity lemma

Alon, N. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267804 · Cited by 32

The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics

Eppstein, D., & Spiro, E. S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03367-4_25 · Cited by 31

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Baswana, S., & Kavitha, T. (2010) · SIAM Journal on Computing · doi:10.1137/080737174 · Cited by 31

$$P\mathop{ =}\limits^{?}NP$$

Aaronson, S. (2016) · Springer eBooks · doi:10.1007/978-3-319-32162-2_1 · Cited by 40

Matrix Multiplication on High-Density Multi-GPU Architectures: Theoretical and Experimental Investigations

Zhang, P., & Gao, Y. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-20119-1_2 · Cited by 32

Estimating Clustering Indexes in Data Streams

Buriol, L. S., Frahling, G., Leonardi, S., & Sohler, C. (2007) · Springer eBooks · doi:10.1007/978-3-540-75520-3_55 · Cited by 31

On the arithmetic complexity of Strassen-like matrix multiplications

Cenk, M., & Hasan, M. A. (2016) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2016.07.004 · Cited by 34

Polynomials and the exponent of matrix multiplication

Chiantini, L., Hauenstein, J. D., Ikenmeyer, C., Landsberg, J. M., & Ottaviani, G. (2018) · Bulletin of the London Mathematical Society · doi:10.1112/blms.12147 · Cited by 31

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Alman, J., & Williams, V. V. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00061 · Cited by 37

Computing Frobenius maps and factoring polynomials

Gathen, J. V. Z., & Shoup, V. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129722 · Cited by 31

Lower Bounds for Matrix Product

Shpilka, A. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702405954 · Cited by 35

Approximate distance oracles for unweighted graphs in Õ (n2) time

Baswana, S., & Sen, S. (2004) · Symposium on Discrete Algorithms · doi:10.5555/982792.982830 · Cited by 31

Scheduling with communication for multiprocessor computation

Verriet, J. H. (1998) · Utrecht University Repository (Utrecht University) · Cited by 31

Computing minimal interpolation bases

Jeannerod, C.-P., Neiger, V., Schost, É., & Villard, G. (2016) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2016.11.015 · Cited by 30

SETH-based Lower Bounds for Subset Sum and Bicriteria Path

Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2022) · ACM Transactions on Algorithms · doi:10.1145/3450524 · Cited by 30

General Principles of Algebraic Attacks and New Design Criteria for Cipher Components

Courtois, N. T. (2005) · Lecture notes in computer science · doi:10.1007/11506447_7 · Cited by 30

Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality

Bostan, A., Salvy, B., & Schost, �. (2003) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-003-0133-5 · Cited by 30

Maximum-Likelihood Detection in Few-Mode Fiber Transmission With Mode-Dependent Loss

Lobato, A., Ferreira, F. M., Inan, B., Adhikari, S., Kuschnerov, M., Napoli, A., Spinnler, B., & Lankl, B. (2013) · IEEE Photonics Technology Letters · doi:10.1109/lpt.2013.2257724 · Cited by 30

Using polynomial regression for data representation in wireless sensor networks

Banerjee, T., Chowdhury, K. R., & Agrawal, D. P. (2006) · International Journal of Communication Systems · doi:10.1002/dac.847 · Cited by 30

Dynamic Subgraph Connectivity with Geometric Applications

Chan, T. M. (2006) · SIAM Journal on Computing · doi:10.1137/s009753970343912x · Cited by 30

Dynamic Connectivity: Connecting to Networks and Geometry

Chan, T. M., Ptraşcu, M., & Roditty, L. (2011) · SIAM Journal on Computing · doi:10.1137/090751670 · Cited by 30

Structural Properties of Sparse Graphs

Nešetřil, J., & de Mendez, P. O. (2008) · Bolyai Society mathematical studies · doi:10.1007/978-3-540-85221-6_13 · Cited by 30

A Gibbs Sampler for Learning DAGs.

Goudie, R. J. B., & Mukherjee, S. (2016) · PubMed · doi:10.17863/cam.24421 · Cited by 30

Subquadratic-time factoring of polynomials over finite fields

Kaltofen, E., & Shoup, V. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225166 · Cited by 30

Information-Based complexity: New questions for mathematicians

Traub, J. F., & Woźniakowski, H. (1991) · The Mathematical Intelligencer · doi:10.1007/bf03024085 · Cited by 30

Determinant algorithms for random planar structures

Wilson, D. B. (1997) · doi:10.5555/314161.314264 · Cited by 30

Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis

Washington, L. C., & Bard, G. V. (2007) · University Libraries (University of Maryland) · Cited by 30

Optimal Key Consensus in Presence of NoisePreprint

Jin, Z., & Zhao, Y. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.06150 · Cited by 33

Further Limitations of the Known Approaches for Matrix MultiplicationPreprint

Alman, J., & Williams, V. V. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2018.25 · Cited by 38

Speeding up subgroup cryptosystems

Stam, M. (2003) · doi:10.6100/ir564670 · Cited by 29

Notes on Communication and Computation in Secure Distributed Matrix Multiplication

D’Oliveira, R. G. L., Rouayheb, S. E., Heinlein, D., & Karpuk, D. (2020) · IEEE Conference on Communications and Network Security · doi:10.1109/cns48642.2020.9162296 · Cited by 29

Efficient Sparse Representation for Learning With High-Dimensional Data

Chen, J., Yang, S., Wang, Z., & Mao, H. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3119278 · Cited by 29

Efficient algorithms on sets of permutations, dominance, and real-weighted APSP

Yuster, R. (2009) · doi:10.5555/1496770.1496873 · Cited by 29

Group-theoretic algorithms for matrix multiplication

Umans, C. (2006) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1145768.1145772 · Cited by 30

On the complexity of computing with zero-dimensional triangular sets

Poteaux, A., & Schost, É. (2012) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2012.05.008 · Cited by 29

A landmark‐bounded method for large‐scale underground mine mapping

Lavigne, N. J., & Marshall, J. A. (2012) · Journal of Field Robotics · doi:10.1002/rob.21415 · Cited by 30

On Computing the Resultant of Generic Bivariate Polynomials

Villard, G. (2018) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/3208976.3209020 · Cited by 29

Barriers for Fast Matrix Multiplication from Irreversibility

Christandl, M., Vrana, P., & Zuiddam, J. (2021) · Theory of Computing · doi:10.4086/toc.2021.v017a002 · Cited by 46

Algebraic Attacks over GF(2 k ), Application to HFE Challenge 2 and Sflash-v2

Courtois, N. T. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24632-9_15 · Cited by 29

Shortest Paths in Matrix Multiplication Time

Sankowski, P. (2005) · Lecture notes in computer science · doi:10.1007/11561071_68 · Cited by 29

Directeds-t numberings, Rubber bands, and testing digraphk-vertex connectivity

Cheriyan, J., & Reif, J. H. (1994) · COMBINATORICA · doi:10.1007/bf01302965 · Cited by 29

Secure Linear Algebra Using Linearly Recurrent Sequences

Kiltz, E., Mohassel, P., Weinreb, E., & Franklin, M. (2007) · Springer eBooks · doi:10.1007/978-3-540-70936-7_16 · Cited by 29

Centroids, Representations, and Submodular Flows

Gabow, H. N. (1995) · Journal of Algorithms · doi:10.1006/jagm.1995.1022 · Cited by 29

Change of order for bivariate triangular sets

Pascal, C., & Schost, É. (2006) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1145768.1145814 · Cited by 29

Revealed preference theory: An algorithmic outlook

Smeulders, B., Crama, Y., & Spieksma, F. C. R. (2018) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.04.026 · Cited by 28

An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay

Bock, N., & Challacombe, M. (2013) · SIAM Journal on Scientific Computing · doi:10.1137/120870761 · Cited by 28

A Case for Compute Reuse in Future Edge Systems: An Empirical Study

Lee, J., Mtibaa, A., & Mastorakis, S. (2019) · IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/gcwkshps45667.2019.9024587 · Cited by 28

Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-free Languages

Akutsu, T. (1999) · Journal of Combinatorial Optimization · doi:10.1023/a:1009898029639 · Cited by 28

A polynomial approximation algorithm for the minimum fill-in problem

Natanzon, A., Ron Shamir, A., & Sharan, R. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276710 · Cited by 28

Descriptive complexity and the W hierarchy.

Downey, R. G., Fellows, M. R., & Regan, K. W. (1996) · Cited by 28

Novel Sampling Scheme on the Sphere for Head-Related Transfer Function Measurements

Bates, A. P., Khalid, Z., & Kennedy, R. A. (2015) · IEEE/ACM Transactions on Audio Speech and Language Processing · doi:10.1109/taslp.2015.2419971 · Cited by 27

Fast approximate truncated SVD

Shishkin, S. L., Shalaginov, A., & Bopardikar, S. D. (2019) · Numerical Linear Algebra with Applications · doi:10.1002/nla.2246 · Cited by 27

Geodetic Sets in Graphs

Brešar, B., Kovše, M., & Tepeh, A. (2010) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4789-6_8 · Cited by 27

Replacement Paths via Fast Matrix Multiplication

Weimann, O., & Yuster, R. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.68 · Cited by 27

Faster Approximation of Distances in Graphs

Berman, P., & Kasiviswanathan, S. P. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73951-7_47 · Cited by 30

Deterministic computation of the Frobenius form

Storjohann, A. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959911 · Cited by 27

Faster subtree isomorphism

Ron Shamir, A., & Tsur, D. (2002) · Israel Symposium on Theory and Computing Systems (ISTCS) · doi:10.1109/istcs.1997.595164 · Cited by 27

All-pairs bottleneck paths in vertex weighted graphs

Shapira, A., Yuster, R., & Zwick, U. (2007) · doi:10.5555/1283383.1283488 · Cited by 27

Finding least common ancestors in directed acyclic graphs

Bender, M. A., Pemmasani, G., Skiena, S., & Sumazin, P. (2001) · doi:10.5555/365411.365795 · Cited by 27

Faster Algorithms for Markov Decision Processes with Low Treewidth

Chatterjee, K., & Łącki, J. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39799-8_36 · Cited by 27

Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts

Jeannerod, C.-P., Neiger, V., Schost, É., & Villard, G. (2016) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2930889.2930928 · Cited by 27

Radiance Uncertainty Characterisation to Facilitate Climate Data Record Creation

Merchant, C. J., Holl, G., Mittaz, J. P. D., & Woolliams, E. R. (2019) · Remote Sensing · doi:10.3390/rs11050474 · Cited by 27

LU-Cholesky QR algorithms for thin QR decomposition

Terao, T., Ozaki, K., & Ogita, T. (2019) · Parallel Computing · doi:10.1016/j.parco.2019.102571 · Cited by 29

How to Write Fast Numerical Code: A Small Introduction

Chellappa, S., Franchetti, F., & Püschel, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88643-3_5 · Cited by 28

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