Cover Image

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jin, Ce, Xu, Yinzhan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

New Separations and Reductions for Directed Preservers and Hopsets
by: Hoppenworth, Gary, et al.
Published: (2024)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

Determinantal Sieving
by: Eiben, Eduard, et al.
Published: (2023)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting
by: Ertl, Otmar
Published: (2023)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

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

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Faster Convolutions: Yates and Strassen Revisited
by: Brand, Cornelius, et al.
Published: (2025)

DynamicLogLog: Faster, Smaller, and More Accurate Cardinality Estimation
by: Bushnell, Brian
Published: (2026)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Less is More: Faster Maximum Clique Search by Work-Avoidance
by: Vandierendonck, Hans
Published: (2025)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)