5 papers
Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection and Pace to Unanimity
Ioana Dumitriu, Muchen Ju, Hai-Xiao Wang
We study the two-opinion majority dynamics process: at each time step, every vertex adopts the majority opinion among its neighbors, retaining its current opinion if there is a tie…
Majority Dynamics on Assortative Sparse Stochastic Block Models
Ioana Dumitriu, Muchen Ju, Hai-Xiao Wang
Majority dynamics is a two-opinion process in which each vertex repeatedly updates to the majority opinion among its neighbors. We study this process on a resampled sparse binary s…
Attention Mechanisms Through the Lens of Numerical Methods: Approximation Methods and Alternative Formulations
Michel Fabrice Serret, Alice Cortinovis, Yijun Dong +10
The attention mechanism is the computational core of modern Transformer architectures, but its quadratic complexity in the input sequence length is the bottleneck for large-scale i…
Singular values of sparse random rectangular matrices: Emergence of outliers at criticality
Ioana Dumitriu, Hai-Xiao Wang, Zhichao Wang +1
Consider the random bipartite ErdÅs-Rényi graph , where each edge with one vertex in and the other vertex in is connected with proba…
Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks
Hai-Xiao Wang, Zhichao Wang
We delve into the challenge of semi-supervised node classification on the Contextual Stochastic Block Model (CSBM) dataset. Here, nodes from the two-cluster Stochastic Block Model…