:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Beame, Paul, Whitmeyer, Michael
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2411.07400
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

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

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

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

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

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

Optimal Communication Complexity of Chained Index
by: Sundaresan, Janani
Published: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Collision-resistant hash-shuffles on the reals
by: Barmpalias, George, et al.
Published: (2025)

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

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