Papers for

graph processing engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improved bounds for rectangular matrix multiplication reduce graph algorithm times

Rectangular matrix multiplication from shared-leg entropy

Abstract: In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $ω(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $ω(1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $ω(1,\frac{1}{2},1)=2$ and the dual exponent satisfies $α\ge \frac{1}{2}$. We use the shared-leg entropy inequality and polynomial-multiplication degenerations from that work, retaining two-leg symmetry and the orientation of each sector. Logarithmic averaging produces homogeneous auxiliary profiles. Their powered versions have a common asymptotic slope, and bounding their intercepts gives the spectral constraint $b\le 4a(1-a)$. This yields the rectangular curve by tensor-spectrum duality. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.

Wed 7 OctData Structures and Algorithms
The gist
Multiplying matrices quickly is a key step in many computer algorithms, like finding shortest paths in networks. The authors expanded on recent math to better understand how quickly rectangular matrices (matrices with different row and column sizes) can be multiplied. Their results show new limits on the speed of these multiplications. This leads to faster algorithms for certain network problems, shaving time off known techniques.
Open → 2610.10494v1

Random order enables new quantum memory uses in streaming tasks

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

Abstract: How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.

Mon 5 OctData Structures and Algorithms
The gist
This paper looks at how the order of data affects the power of quantum memory when processing data streams. The authors show that in random order, quantum memory can be reused or "replenished" by later data, making quantum algorithms more space efficient. They prove limits on how little space is possible for some problems, showing that even quantum methods need substantial memory in other situations. They also improve algorithms for counting triangles in graphs when edges come in random repeated order. Overall, the work shows that random input order can both help and limit quantum streaming.
Open → 2610.06727v1