Cover Image

Better Boosting of Communication Oracles, or Not

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Harms, Nathaniel, Riazanov, Artur
Format:	Preprint
Published:	2024
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

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Randomized Communication and Implicit Graph Representations
by: Harms, Nathaniel, et al.
Published: (2021)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

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

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

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

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

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
by: Ruszil, Jakub, et al.
Published: (2026)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
by: Stoian, Mihail
Published: (2024)

Cluster Editing on Cographs and Related Classes
by: Lafond, Manuel, et al.
Published: (2024)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

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

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

On approximability of the Permanent of PSD matrices
by: Ebrahimnejad, Farzam, et al.
Published: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

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

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
by: Kuschner, Jordan, et al.
Published: (2024)

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

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)