85 papers
This paper presents a fully-dynamic data structure that maintains spectral sparsifiers for geometric graphs with update time under point location changes, offering robustness against adaptive adversaries and enabling efficient randomized sketches for Laplacian matrix operations.
The paper introduces DRESS, a deterministic and parameter-free framework that generates isomorphism-invariant graph fingerprints via a convergent non-linear dynamical system, offering expressiveness comparable to the 2-WL test at significantly lower computational cost while generalizing to enhanced variants like -DRESS that surpass higher-order Weisfeiler-Leman tests.
This paper presents the first deterministic iterative algorithm for constructing an -coreset that guarantees subspace embedding for any , achieving an optimal size of by removing previously necessary logarithmic factors and enabling deterministic solutions for regression.
This paper presents improved algorithms for various kernel matrix linear algebra tasks, such as matrix-vector products and spectral norm computation, by leveraging kernel density estimation to achieve faster runtimes with reduced dependencies on the number of data points and error tolerance compared to existing methods.
This paper establishes that low-degree polynomial tests can distinguish between correlated sparse stochastic block models and independent Erdős-Rényi graphs if and only if the subsampling probability exceeds the minimum of Otter's constant and the Kesten-Stigum threshold, thereby identifying a sharp computational transition for detection and partial recovery.