Cover Image

The communication complexity of distributed estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gopalan, Parikshit, Meka, Raghu, Raghavendra, Prasad, Singhal, Mihir, Wigderson, Avi
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
by: Bürgisser, Peter, et al.
Published: (2024)

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

Parameterized complexity of reconfiguration of atoms
by: Cooper, Alexandre, et al.
Published: (2021)

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

On girth and the parameterized complexity of token sliding and token jumping
by: Bartier, Valentin, et al.
Published: (2020)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Randomized query composition and product distributions
by: Sanyal, Swagato
Published: (2024)

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

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Parameter estimation for Gibbs distributions
by: Harris, David G., et al.
Published: (2020)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

Universal Solvability for Robot Motion Planning on Graphs
by: Dhar, Anubhav, et al.
Published: (2025)

On the complexity of symmetric vs. functional PCSPs
by: Nakajima, Tamio-Vesa, et al.
Published: (2022)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
by: Dumont, Joanne, et al.
Published: (2026)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

On estimating the quantum $\ell_α$ distance
by: Liu, Yupan, et al.
Published: (2025)

Amplitude amplification and estimation require inverses
by: Tang, Ewin, et al.
Published: (2025)

On estimating the trace of quantum state powers
by: Liu, Yupan, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

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

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)