Copertina

Multiparty Communication Complexity of Collision Finding

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Beame, Paul, Whitmeyer, Michael
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Quantum Time-Space Tradeoffs for Matrix Problems
di: Beame, Paul, et al.
Pubblicazione: (2024)

Extending CDCL to disjunctions of parity equations
di: Beame, Paul, et al.
Pubblicazione: (2026)

The NISQ Complexity of Collision Finding
di: Hamoudi, Yassine, et al.
Pubblicazione: (2022)

The Complexity of Order-Finding for ROABPs
di: Bhargava, Vishwas, et al.
Pubblicazione: (2024)

Multiparty equality in the local broadcast model
di: Esperet, Louis, et al.
Pubblicazione: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
di: Egidy, Fabian, et al.
Pubblicazione: (2024)

A Parameterized-Complexity Framework for Finding Local Optima
di: Ganian, Robert, et al.
Pubblicazione: (2026)

The Complexity of Finding Missing Answer Repairs
di: Comer, Jesse, et al.
Pubblicazione: (2026)

Pseudodeterministic Communication Complexity
di: Göös, Mika, et al.
Pubblicazione: (2025)

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

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

The Complexity of Finding and Counting Subtournaments
di: Döring, Simon, et al.
Pubblicazione: (2025)

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

Optimal Communication Complexity of Chained Index
di: Sundaresan, Janani
Pubblicazione: (2024)

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

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

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
di: Mackenzie, Simon, et al.
Pubblicazione: (2024)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
di: Dvořák, Pavel, et al.
Pubblicazione: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

On the Rational Degree of Boolean Functions and Applications
di: Iyer, Vishnu, et al.
Pubblicazione: (2023)

Communication Complexity of Disjointness under Product Distributions
di: Hunter, Zach, et al.
Pubblicazione: (2026)

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

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
di: Shih, Yu-Sheng, et al.
Pubblicazione: (2026)

The Complexity of Finding Local Optima in Contrastive Learning
di: Yan, Jingming, et al.
Pubblicazione: (2025)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
di: Chen, Lijie, et al.
Pubblicazione: (2025)

Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
di: Fioravantes, Foivos, et al.
Pubblicazione: (2024)

The Communication Complexity of Approximating Matrix Rank
di: Sherstov, Alexander A., et al.
Pubblicazione: (2024)

Complexity of Finding and Enumerating Interconnection Trees
di: Demange, Noé, et al.
Pubblicazione: (2026)

The Adaptive Complexity of Finding a Stationary Point
di: Zhou, Huanjian, et al.
Pubblicazione: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
di: Ramya, C., et al.
Pubblicazione: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
di: Brânzei, Simina, et al.
Pubblicazione: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
di: Atserias, Albert, et al.
Pubblicazione: (2024)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
di: Hollender, Alexandros, et al.
Pubblicazione: (2023)

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

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
di: Dey, Palash, et al.
Pubblicazione: (2026)

Assembly Theory and its Relationship with Computational Complexity
di: Kempes, Christopher P., et al.
Pubblicazione: (2024)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
di: Hasegawa, Atsuya, et al.
Pubblicazione: (2025)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
di: Wu, Xudong, et al.
Pubblicazione: (2025)