Copertina

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Pettie, Seth, Wang, Dingyu
Natura:	Preprint
Pubblicazione:	2020
Soggetti:	Data Structures and Algorithms Information Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Universal Perfect Samplers for Incremental Streams
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
di: Long, Yaowei, et al.
Pubblicazione: (2024)

Space Complexity of Vertex Connectivity Oracles
di: Pettie, Seth, et al.
Pubblicazione: (2022)

Key Compression Limits for $k$-Minimum Value Sketches
di: Dickens, Charlie, et al.
Pubblicazione: (2024)

Testing (Conditional) Mutual Information
di: Seyfried, Jan, et al.
Pubblicazione: (2025)

Optimal Protocols for 2-Party Contention Resolution
di: Wang, Dingyu
Pubblicazione: (2024)

Multi-dimensional Approximate Counting
di: Wang, Dingyu
Pubblicazione: (2024)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
di: Huang, Shang-En, et al.
Pubblicazione: (2016)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
di: Wang, Ziao, et al.
Pubblicazione: (2023)

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
di: Wang, Ziao, et al.
Pubblicazione: (2022)

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
di: Gadekar, Ameet, et al.
Pubblicazione: (2025)

Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach
di: Jiang, Bo, et al.
Pubblicazione: (2024)

Capacity-Achieving Gray Codes
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
di: Gupta, Shivam, et al.
Pubblicazione: (2023)

A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
di: Wang, Xinzhao, et al.
Pubblicazione: (2022)

Optimality of Frequency Moment Estimation
di: Braverman, Mark, et al.
Pubblicazione: (2024)

Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication
di: Ly, Hoang, et al.
Pubblicazione: (2025)

Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
di: Löffler, Maarten, et al.
Pubblicazione: (2026)

A probabilistic analysis on general probabilistic scheduling problems
di: Suruga, Daiki
Pubblicazione: (2024)

Robust Gray Codes Approaching the Optimal Rate
di: Con, Roni, et al.
Pubblicazione: (2024)

Investigations on Algorithm Selection for Interval-Based Coding Methods
di: Strutz, Tilo, et al.
Pubblicazione: (2024)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2025)

Pcodec: Better Compression for Numerical Sequences
di: Loncaric, Martin, et al.
Pubblicazione: (2025)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
di: Peikert, Chris, et al.
Pubblicazione: (2025)

Old and New Results on Alphabetic Codes
di: Bruno, Roberto, et al.
Pubblicazione: (2025)

Lower Bounds on Adaptive Sensing for Matrix Recovery
di: Kacham, Praneeth, et al.
Pubblicazione: (2023)

Efficient $\varepsilon$-approximate minimum-entropy couplings
di: Compton, Spencer
Pubblicazione: (2025)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
di: Ashvinkumar, Vikrant, et al.
Pubblicazione: (2025)

Graph Reconstruction from Noisy Random Subgraphs
di: McGregor, Andrew, et al.
Pubblicazione: (2024)

A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data
di: Smart, Bridget, et al.
Pubblicazione: (2025)

More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
di: Ghentiyala, Surendra, et al.
Pubblicazione: (2024)

Continuous Optimization for Decoding Errors
di: Srivastava, Shashank
Pubblicazione: (2024)

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

Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
di: Bruno, Roberto, et al.
Pubblicazione: (2025)

Efficiency of ANS Entropy Encoders
di: Kosolobov, Dmitry
Pubblicazione: (2022)

Worst-case optimal adaptive alphabetic prefix-free coding
di: Gagie, Travis
Pubblicazione: (2021)

Analyzing Collection Strategies: A Computational Perspective on the Coupon Collector Problem
di: Abraham, Hadas, et al.
Pubblicazione: (2026)

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
di: Rao, Shravas
Pubblicazione: (2023)