Copertina

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gu, Yuzhou, Li, Xin, Xu, Yinzhan
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Computational Complexity Information Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

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

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
di: Srivastava, Shashank, et al.
Pubblicazione: (2025)

Improved Decoding of Tanner Codes
di: Zhou, Zhaienhe, et al.
Pubblicazione: (2025)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
di: Al-okaily, Anas
Pubblicazione: (2024)

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
di: Focke, Jacob, et al.
Pubblicazione: (2022)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
di: Döring, Simon, et al.
Pubblicazione: (2024)

Quantum Multi-Level Estimation of Functionals of Discrete Distributions
di: Chen, Kean, et al.
Pubblicazione: (2026)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
di: Chen, Sitan, et al.
Pubblicazione: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
di: Li, Qian, et al.
Pubblicazione: (2025)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
di: Goldenberg, Elazar, et al.
Pubblicazione: (2024)

The Structure of In-Place Space-Bounded Computation
di: Cook, James, et al.
Pubblicazione: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
di: Black, Hadley, et al.
Pubblicazione: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
di: Greilhuber, Jakob, et al.
Pubblicazione: (2026)

Stable Algorithms Lower Bounds for Estimation
di: Yu, Xifan, et al.
Pubblicazione: (2026)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
di: Fujie, Yuto, et al.
Pubblicazione: (2025)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
di: Braverman, Mark, et al.
Pubblicazione: (2025)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
di: Saha, Barna, et al.
Pubblicazione: (2024)

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
di: Wang, Qisheng
Pubblicazione: (2024)

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

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
di: Chakraborty, Dipayan, et al.
Pubblicazione: (2024)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
di: Kothari, Pravesh K., et al.
Pubblicazione: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
di: Mao, Songtao
Pubblicazione: (2026)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
di: Luo, Yuetian, et al.
Pubblicazione: (2023)

The Theory and Practice of Computing the Bus-Factor
di: Piccolo, Sebastiano A., et al.
Pubblicazione: (2026)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
di: Kocurek, Nicholas, et al.
Pubblicazione: (2026)

Kernelization Bounds for Constrained Coloring
di: Haviv, Ishay
Pubblicazione: (2026)

Clustering with Locally Bounded Ignorance
di: Garvardt, Jaroslav, et al.
Pubblicazione: (2026)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Residue Domination in Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2024)

Improved Space Bounds for Subset Sum
di: Belova, Tatiana, et al.
Pubblicazione: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
di: Fleming, Noah, et al.
Pubblicazione: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

A Space-space Trade-off for Directed st-Connectivity
di: Edenhofer, Roman
Pubblicazione: (2026)