Buchumschlag

Optimality of Frequency Moment Estimation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Braverman, Mark, Zamir, Or
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity Information Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
von: Braverman, Mark, et al.
Veröffentlicht: (2025)

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
von: Wang, Qisheng
Veröffentlicht: (2024)

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
von: Wang, Qisheng, et al.
Veröffentlicht: (2024)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
von: Al-okaily, Anas
Veröffentlicht: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
von: Gu, Yuzhou, et al.
Veröffentlicht: (2025)

Improved Decoding of Tanner Codes
von: Zhou, Zhaienhe, et al.
Veröffentlicht: (2025)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
von: Ko, Young Kun
Veröffentlicht: (2026)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
von: Saha, Barna, et al.
Veröffentlicht: (2024)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
von: Chen, Sitan, et al.
Veröffentlicht: (2026)

Quantum Multi-Level Estimation of Functionals of Discrete Distributions
von: Chen, Kean, et al.
Veröffentlicht: (2026)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
von: Goldenberg, Elazar, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Optimal certification of constant-local Hamiltonians
von: Lee, Junseo, et al.
Veröffentlicht: (2025)

Stable Algorithms Lower Bounds for Estimation
von: Yu, Xifan, et al.
Veröffentlicht: (2026)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

Testing Sumsets is Hard
von: Chen, Xi, et al.
Veröffentlicht: (2024)

On Optimal Testing of Linearity
von: Arora, Vipul, et al.
Veröffentlicht: (2024)

Linear Hashing Is Optimal
von: Jaber, Michael, et al.
Veröffentlicht: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
von: Bhattacharya, Sudatta, et al.
Veröffentlicht: (2025)

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes
von: Green-Maimon, Naomi, et al.
Veröffentlicht: (2025)

Near-Optimal Averaging Samplers and Matrix Samplers
von: Xun, Zhiyang, et al.
Veröffentlicht: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
von: Sohn, Youngtak, et al.
Veröffentlicht: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
von: Wallisch, Christian, et al.
Veröffentlicht: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Unbounded Error Correcting Codes
von: Efremenko, Klim, et al.
Veröffentlicht: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
von: Rai, Shanthanu S
Veröffentlicht: (2024)

Model-agnostic super-resolution in high dimensions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
von: Umans, Chris, et al.
Veröffentlicht: (2025)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
von: Levet, Michael, et al.
Veröffentlicht: (2025)