Cover Image

Instance-optimal estimation of L2-norm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Adar, Tomer
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight simulation of a distribution using conditional samples
by: Adar, Tomer
Published: (2025)

Optimal mass estimation in the conditional sampling model
by: Adar, Tomer, et al.
Published: (2025)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Refining the Adaptivity Notion in the Huge Object Model
by: Adar, Tomer, et al.
Published: (2023)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

Support Testing in the Huge Object Model
by: Adar, Tomer, et al.
Published: (2023)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Convex optimization with $p$-norm oracles
by: Adil, Deeksha, et al.
Published: (2024)

Load Balancing with Duration Predictions
by: Azar, Yossi, et al.
Published: (2025)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

An Improved Algorithm for Sparse Instances of SAT
by: Jain, Sanjay, et al.
Published: (2024)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

Unifying Laplace Mechanism with Instance Optimality in Differential Privacy
by: Durfee, David
Published: (2025)

Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy
by: Dong, Wei, et al.
Published: (2024)

Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization
by: Yılmaz, Baturay, et al.
Published: (2025)

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

From Donkeys to Kings in Tournaments
by: Abboud, Amir, et al.
Published: (2024)

Fun Maximizing Search, (Non) Instance Optimality, and Video Games for Parrots
by: Barbay, Jérémy
Published: (2024)

Witness-Sensitive Detection of Induced Diamonds
by: Censor-Hillel, Keren, et al.
Published: (2026)

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
by: Bampis, Evripidis, et al.
Published: (2024)

On the instance optimality of detecting collisions and subgraphs
by: Ben-Eliezer, Omri, et al.
Published: (2023)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
by: Ezra, Tomer, et al.
Published: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Query-optimal estimation of unitary channels in diamond distance
by: Haah, Jeongwan, et al.
Published: (2023)

Semirandom Planted Clique via 1-norm Isometry Property
by: Guruswami, Venkatesan, et al.
Published: (2025)

Faster optimal univariate microgaggregation
by: Stamm, Felix I., et al.
Published: (2024)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

Approximating optimization problems in graphs with locational uncertainty
by: Bougeret, Marin, et al.
Published: (2022)

Near-optimal Algorithms for Stochastic Online Bin Packing
by: Ayyadevara, Nikhil, et al.
Published: (2022)

Optimal quantile estimation: beyond the comparison model
by: Gupta, Meghal, et al.
Published: (2024)

A fast and slightly robust covariance estimator
by: Duchi, John, et al.
Published: (2025)

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

GridOT -- a discrete optimal transport solver on grids
by: Rauch, Johannes, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

A note on the depth of optimal fanout-bounded prefix circuits
by: Sergeev, Igor S.
Published: (2025)

A General Reduction for High-Probability Analysis with General Light-Tailed Distributions
by: Attia, Amit, et al.
Published: (2024)