:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Aamand, Anders, Liu, Allen, Narayanan, Shyam
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2411.18765
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Structure of Replicable Hypothesis Testers
by: Aamand, Anders, et al.
Published: (2025)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Skirting Additive Error Barriers for Private Turnstile Streams
by: Aamand, Anders, et al.
Published: (2026)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)

How fast can you find a good hypothesis?
by: Aamand, Anders, et al.
Published: (2025)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Differentially Private Quantiles with Smaller Error
by: Imola, Jacob, et al.
Published: (2025)

Improved algorithms for learning quantum Hamiltonians, via flat polynomials
by: Narayanan, Shyam
Published: (2024)

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)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Learning-Augmented Frequent Directions
by: Aamand, Anders, et al.
Published: (2025)

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
by: Rivkin, Joey, et al.
Published: (2024)

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Differentially Private Gomory-Hu Trees
by: Aamand, Anders, et al.
Published: (2024)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2025)

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

When is String Reconstruction using de Bruijn Graphs Hard?
by: Bals, Ben, et al.
Published: (2025)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

New Bounds for Circular Trace Reconstruction
by: Burudgunte, Arnav, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Sample-Efficient Private Learning of Mixtures of Gaussians
by: Ashtiani, Hassan, et al.
Published: (2024)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

Optimal Rounding for Two-Stage Bipartite Matching
by: Pollner, Tristan, et al.
Published: (2025)

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

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

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

Transposition is Nearly Optimal for IID List Update
by: Coester, Christian
Published: (2026)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Near-Optimal Heaps and Dijkstra on Pointer Machines
by: van der Hoog, Ivor, et al.
Published: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
by: Duyster, Anouk, et al.
Published: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)