Copertina

On Solving Linear Systems in Sublinear Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Andoni, Alexandr, Krauthgamer, Robert, Pogrow, Yosef
Natura:	Preprint
Pubblicazione:	2018
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
di: Kwok, Tsz Chiu, et al.
Pubblicazione: (2025)

On Sketching Quadratic Forms
di: Andoni, Alexandr, et al.
Pubblicazione: (2015)

Solving the Correlation Cluster LP in Sublinear Time
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Sketching Cuts in Graphs and Hypergraphs
di: Kogan, Dmitry, et al.
Pubblicazione: (2014)

Stable coresets: Unleashing the power of uniform sampling
di: Carmel, Amir, et al.
Pubblicazione: (2025)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
di: Kenneth, Yotam, et al.
Pubblicazione: (2023)

A Framework for Building Data Structures from Communication Protocols
di: Andoni, Alexandr, et al.
Pubblicazione: (2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
di: Alman, Josh, et al.
Pubblicazione: (2024)

Simple Algorithms for Fully Dynamic Edge Connectivity
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Cut-Query Algorithms with Few Rounds
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
di: Andoni, Alexandr, et al.
Pubblicazione: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
di: Yoshida, Yuichi
Pubblicazione: (2026)

Computing String Covers in Sublinear Time
di: Radoszewski, Jakub, et al.
Pubblicazione: (2024)

Nearly Optimal Attention Coresets
di: Liberty, Edo, et al.
Pubblicazione: (2026)

Counting Distinct Square Substrings in Sublinear Time
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Moderate Dimension Reduction for $k$-Center Clustering
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2023)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
di: Dai, Jiangqi, et al.
Pubblicazione: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
di: Kempa, Dominik, et al.
Pubblicazione: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
di: Eden, Talya, et al.
Pubblicazione: (2025)

Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
di: Au, Andrew
Pubblicazione: (2026)

Approximate Butterfly Counting in Sublinear Time
di: Luo, Chi, et al.
Pubblicazione: (2026)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
di: Fu, Bin, et al.
Pubblicazione: (2026)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
di: Bille, Philip, et al.
Pubblicazione: (2022)

Coresets for Kernel Clustering
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2021)

Near-Optimal Dimension Reduction for Facility Location
di: Huang, Lingxiao, et al.
Pubblicazione: (2024)

Streaming Algorithms for Geometric Steiner Forest
di: Czumaj, Artur, et al.
Pubblicazione: (2020)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
di: Kapralov, Michael, et al.
Pubblicazione: (2022)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2026)

Almost-Optimal Sublinear Additive Spanners
di: Tan, Zihan, et al.
Pubblicazione: (2023)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
di: Shah, Vihan
Pubblicazione: (2026)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2025)

Simple and Optimal Sublinear Algorithms for Mean Estimation
di: Bertolotti, Beatrice, et al.
Pubblicazione: (2024)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
di: He, Jialin, et al.
Pubblicazione: (2025)