Cover Image

Discrepancy Minimization in Input-Sparsity Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Deng, Yichuan, Li, Xiaoyu, Song, Zhao, Weinstein, Omri
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Training Overparametrized Neural Networks in Sublinear Time
by: Deng, Yichuan, et al.
Published: (2022)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

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

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

A Dynamic Low-Rank Fast Gaussian Transform
by: Huang, Baihe, et al.
Published: (2022)

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

Discrepancy Minimization via Regularization
by: Pesenti, Lucas, et al.
Published: (2022)

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
by: Nikolov, Aleksandar, et al.
Published: (2026)

Quantum Speedups for Approximating the John Ellipsoid
by: Li, Xiaoyu, et al.
Published: (2024)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Constructive l2-Discrepancy Minimization with Additive Deviations
by: Dutta, Kunal
Published: (2025)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
by: Ailon, Nir, et al.
Published: (2025)

Sparsity-Parameterised Dynamic Edge Colouring
by: Christiansen, Aleksander B. G., et al.
Published: (2023)

Faster Algorithm for Structured John Ellipsoid Computation
by: Cao, Yang, et al.
Published: (2022)

Online Flow Time Minimization with Gradually Revealed Jobs
by: Lindermayr, Alexander, et al.
Published: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Minimizing $\ell_2$ Norm of Flow Time by Starvation Mitigation
by: Kuo, Tung-Wei
Published: (2021)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

Minimizing Reachability Times on Temporal Graphs via Shifting Labels
by: Deligkas, Argyrios, et al.
Published: (2021)

Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations
by: Halpern, Daniel, et al.
Published: (2025)

Spectral Sparsification by Deterministic Discrepancy Walk
by: Lau, Lap Chi, et al.
Published: (2024)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
by: Chen, Qingyun, et al.
Published: (2024)

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
by: Heeger, Klaus, et al.
Published: (2024)

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
by: Erlebach, Thomas, et al.
Published: (2026)

Minimizing the Minimizers via Alphabet Reordering
by: Verbeek, Hilde, et al.
Published: (2024)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

Minimizers in Semi-Dynamic Strings
by: Zuba, Wiktor, et al.
Published: (2025)

On Minimizing Wiggle in Stacked Area Charts
by: Dobler, Alexander, et al.
Published: (2025)

One-Sided Local Crossing Minimization
by: Giannopoulos, Panos, et al.
Published: (2025)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
by: Chenakkod, Shabarish, et al.
Published: (2024)

Masked Matrix Multiplication for Emergent Sparsity
by: Wheatman, Brian, et al.
Published: (2024)