More Like this

1. Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity

   https://doi.org/10.5555/3398761.3398865  

   Murhekar, Aniket and (January 2020, AAMAS Conference proceedings)

   null (Ed.)

   A two-player finite game is represented by two payoff matrices (A, B), one for each player. Imitation games are a subclass of two-player games in which B is the identity matrix, implying that the second player gets a positive payoff only if she "imitates" the first. Given that the problem of computing a Nash equilibrium (NE) is known to be provably hard, even to approximate, we ask if it is any easier for imitation games. We show that much like the general case, for any c > 0, computing a 1 over n^c -approximate NE of imitation games remains PPAD-hard, where n is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find ε-approximate NE for any given constant ε > 0 (PTAS). The former result also rules out the smooth complexity being in P, unless PPAD ⊂ RP. 

   more » « less
2. Generalizations of Matrix Multiplication can solve the Light Bulb Problem

   https://doi.org/10.1109/FOCS57990.2023.00090  

   Alman, Josh; Zhang, Hengjie (November 2023, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS))

   In the light bulb problem, one is given uniformly random vectors x1,…,xn,y1,…,yn∈{−1,1}d. They are all chosen independently except a planted pair (xi∗,yj∗) is chosen with correlation ρ>0. The goal is to find the planted pair. This problem was introduced over 30 years ago by L.~Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in Ω(n2) time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as ρ→0. In 2012, G.~Valiant gave a breakthrough algorithm using fast matrix multiplication that runs in time O(n(5−ω)/(4−ω))0 is. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to O(n2ω/3)0. We also introduce a new tensor T2112, which has the same size of 2×2 matrix multiplication tensor, but runs faster than the Strassen's algorithm for light bulb problem. 

   more » « less
3. Communication Lower Bounds for Matricized Tensor Times Khatri-Rao Product

   https://doi.org/10.1109/IPDPS.2018.00065  

   Ballard, Grey; Knight, Nicholas; Rouse, Kathryn (May 2018, 2018 IEEE International Parallel and Distributed Processing Symposium)

   The matricized-tensor times Khatri-Rao product (MTTKRP) computation is the typical bottleneck in algorithms for computing a CP decomposition of a tensor. In order to develop high performance sequential and parallel algorithms, we establish communication lower bounds that identify how much data movement is required for this computation in the case of dense tensors. We also present sequential and parallel algorithms that attain the lower bounds and are therefore communication optimal. In particular, we show that the structure of the computation allows for less communication than the straightforward approach of casting the computation as a matrix multiplication operation. 

   more » « less
4. Communication Lower Bounds and Optimal Algorithms for Symmetric Matrix Computations

   https://doi.org/10.1145/3727344  

   Al_Daas, Hussam; Ballard, Grey; Grigori, Laura; Kumar, Suraj; Rouse, Kathryn; Verite, Mathieu (April 2025, ACM Transactions on Parallel Computing)

   In this article, we focus on the communication costs of three symmetric matrix computations: i) multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK) ii) adding the result of the multiplication of a matrix with the transpose of another matrix and the transpose of that result, known as a symmetric rank-2k update (SYR2K) iii) performing matrix multiplication with a symmetric input matrix (SYMM). All three computations appear in the Level 3 Basic Linear Algebra Subroutines (BLAS) and have wide use in applications involving symmetric matrices. We establish communication lower bounds for these kernels using sequential and distributed-memory parallel computational models, and we show that our bounds are tight by presenting communication-optimal algorithms for each setting. Our lower bound proofs rely on applying a geometric inequality for symmetric computations and analytically solving constrained nonlinear optimization problems. The symmetric matrix and its corresponding computations are accessed and performed according to a triangular block partitioning scheme in the optimal algorithms. 

   more » « less
5. Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds

   https://doi.org/10.1145/3490148.3538552  

   Al Daas, Hussam; Ballard, Grey; Grigori, Laura; Kumar, Suraj; Rouse, Kathryn (July 2022, Proceedings of the 34th Annual ACM Symposium on Parallelism in Algorithms and Architectures)

   Communication lower bounds have long been established for matrix multiplication algorithms. However, most methods of asymptotic analysis have either ignored the constant factors or not obtained the tightest possible values. Recent work has demonstrated that more careful analysis improves the best known constants for some classical matrix multiplication lower bounds and helps to identify more efficient algorithms that match the leading-order terms in the lower bounds exactly and improve practical performance. The main result of this work is the establishment of memory-independent communication lower bounds with tight constants for parallel matrix multiplication. Our constants improve on previous work in each of three cases that depend on the relative sizes of the aspect ratios of the matrices. 

   more » « less