:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Xu, Jeff
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2411.14314
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
by: Kocurek, Nicholas, et al.
Published: (2026)

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

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
by: Eagling-Vose, Tala, et al.
Published: (2024)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Finding d-Cuts in Claw-free Graphs
by: Ahn, Jungho, et al.
Published: (2025)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
by: Bharadwaj, G V Sumukha, et al.
Published: (2024)

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
by: Bozga, Marius, et al.
Published: (2026)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Distributed $(Δ+1)$-Coloring in Graphs of Bounded Neighborhood Independence
by: Fuchs, Marc, et al.
Published: (2025)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
by: Chukhin, Nikolai, et al.
Published: (2024)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Outer-(ap)RAC Graphs
by: Förster, et al.
Published: (2024)

Realizing Graphs with Cut Constraints
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

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

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

The Parameterized Complexity of Coloring Mixed Graphs
by: Lauerbach, Antonio, et al.
Published: (2026)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

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

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Recognizing and Realizing Temporal Reachability Graphs
by: Erlebach, Thomas, et al.
Published: (2025)