STOC

\documentclass[sigconf,screen,nonacm]{acmart}
\settopmatter{printacmref=false,printccs=false}
\usepackage{amsmath,amssymb,amsthm,mathtools}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\acmConference[STOC '26]{ACM Symposium on Theory of Computing}{June 2026}{City, Country}

\begin{document}

\title{Near-Linear Time Approximation for Graph Sparsification\\via Structural Oracles}

\author{First Last}
\affiliation{\institution{University of Example}\country{Country}}
\email{[email protected]}
\author{Jane Doe}
\affiliation{\institution{Example Research Labs}\country{Country}}
\email{[email protected]}

\begin{abstract}
We give a near-linear time $(1\pm\varepsilon)$-approximation algorithm
for graph sparsification that produces a sparsifier with
$O(n \log n / \varepsilon^2)$ edges, improving the prior best
$O(m^{4/3})$ bound. Our approach combines a new structural oracle for
effective resistances with a careful sampling scheme.
\end{abstract}

\maketitle

\section{Introduction}
Graph sparsification is a fundamental algorithmic primitive. Spielman
and Srivastava showed that effective-resistance sampling achieves
spectral sparsification with $O(n \log n / \varepsilon^2)$ edges in
$\tilde O(m^{4/3})$ time.

\begin{theorem}\label{thm:main}
There is an algorithm that given a weighted graph $G$ on $n$ vertices and
$m$ edges and $\varepsilon \in (0,1)$, runs in time $O((n+m) \cdot
\mathrm{poly}(\log n, \varepsilon^{-1}))$ and outputs a
$(1\pm\varepsilon)$-spectral sparsifier of $G$ with
$O(n \log n / \varepsilon^2)$ edges.
\end{theorem}

\section{Preliminaries}
\begin{definition}
A graph $H$ is a $(1\pm\varepsilon)$-spectral sparsifier of $G$ if
$(1-\varepsilon) x^\top L_H x \le x^\top L_G x \le (1+\varepsilon) x^\top L_H x$
for all $x$.
\end{definition}

\section{Structural Oracle}
\begin{lemma}\label{lem:oracle}
There is a data structure answering $(1 \pm \varepsilon)$-approximate
effective-resistance queries in $\mathrm{polylog}(n)$ time per query,
with $O((n+m) \cdot \mathrm{polylog}(n))$ preprocessing.
\end{lemma}

\begin{proof}
We build a short-cycle-free spanner and perform truncated random walks
on a Schur-complement contraction.
\end{proof}

\section{Sampling Scheme}
Given the oracle, we sample each edge independently with probability
proportional to its approximate effective resistance.

\section{Proof of Theorem~\ref{thm:main}}
The proof combines Lemma~\ref{lem:oracle} with a matrix Bernstein
concentration argument.

\section{Conclusion}
Near-linear time suffices for near-optimal spectral sparsification.

\bibliographystyle{ACM-Reference-Format}
\bibliography{refs}
\end{document}