Imagen de Portada

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Mackenzie, Simon, Saffidine, Abdallah
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
por: Nkosi, Thami
Publicado: (2025)

An XOR Lemma for Deterministic Communication Complexity
por: Iyer, Siddharth, et al.
Publicado: (2024)

A Strong Direct Sum Theorem for Distributional Query Complexity
por: Blanc, Guy, et al.
Publicado: (2024)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
por: Saffidine, Abdallah, et al.
Publicado: (2025)

Strongly Refuting Random CSP without Literals
por: Chan, Siu On, et al.
Publicado: (2026)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

New Direct Sum Tests
por: Westover, Alek, et al.
Publicado: (2024)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
por: Pednekar, Samruddhi, et al.
Publicado: (2026)

Refuting Perfect Matchings in Spectral Expanders is Hard
por: Biswas, Ari, et al.
Publicado: (2025)

A Piecewise Approach for the Analysis of Exact Algorithms
por: Clinch, Katie, et al.
Publicado: (2024)

One-Way Communication Complexity of Partial XOR Functions
por: Podolskii, Vladimir V., et al.
Publicado: (2023)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
por: Yang, Guangxu, et al.
Publicado: (2025)

On the Parameterized Complexity of Min-Sum-Radii
por: Kumar, Pankaj, et al.
Publicado: (2026)

Pseudodeterministic Communication Complexity
por: Göös, Mika, et al.
Publicado: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
por: Baril, Ambroise, et al.
Publicado: (2024)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
por: Guan, Ziyi, et al.
Publicado: (2023)

Structure in Communication Complexity and Constant-Cost Complexity Classes
por: Hatami, Hamed, et al.
Publicado: (2024)

Direct Product Theorems for Randomized Query Complexity
por: Ben-David, Shalev, et al.
Publicado: (2025)

Communication Complexity is NP-hard
por: Hirahara, Shuichi, et al.
Publicado: (2025)

Recovery Reductions, Conjectures, and Barriers
por: Nareddy, Tejas, et al.
Publicado: (2025)

Multiparty Communication Complexity of Collision Finding
por: Beame, Paul, et al.
Publicado: (2024)

Optimal Communication Complexity of Chained Index
por: Sundaresan, Janani
Publicado: (2024)

A Hierarchy for Constant Communication Complexity
por: Ambainis, Andris, et al.
Publicado: (2025)

A Note on the Complexity of Directed Clique
por: Gutowski, Grzegorz, et al.
Publicado: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
por: Klocker, Linus, et al.
Publicado: (2026)

The Algebraic Cost of a Boolean Sum
por: Orzel, Ian, et al.
Publicado: (2025)

Deterministic Weighted Automata under Partial Observability
por: Michaliszyn, Jakub, et al.
Publicado: (2024)

Trinomials and Deterministic Complexity Limits for Real Solving
por: Boniface, Emma, et al.
Publicado: (2022)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
por: Bhattacharya, Sreejata Kishor
Publicado: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
por: Chatterjee, Prerona, et al.
Publicado: (2025)

Geometry Of The Subset Sum Problem -- Part I
por: Bollepalli, Srinivas Balaji
Publicado: (2025)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
por: Samar, Sahil, et al.
Publicado: (2026)

On the Keevash-Knox-Mycroft Conjecture
por: Gan, Luyining, et al.
Publicado: (2022)

Second-Order Parameterizations for the Complexity Theory of Integrable Functions
por: Bacho, Aras, et al.
Publicado: (2025)

On the Complexity of Target Set Selection in Simple Geometric Networks
por: Dvořák, Michal, et al.
Publicado: (2023)

Direct Sums for Parity Decision Trees
por: Besselman, Tyler, et al.
Publicado: (2024)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
por: Anagnostides, Ioannis, et al.
Publicado: (2025)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
por: Bortolotti, Alex, et al.
Publicado: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
por: Part, Fedor
Publicado: (2022)