:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Yoshida, Yuichi, Zhang, Zihan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	https://arxiv.org/abs/2511.16918
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

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

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
by: Hwang, Yeongwoo, et al.
Published: (2024)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Analyzing and Leveraging the $k$-Sensitivity of LZ77
by: Bathie, Gabriel, et al.
Published: (2026)

Parameter estimation for Gibbs distributions
by: Harris, David G., et al.
Published: (2020)

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

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

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

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

Detecting Low-Degree Truncation
by: De, Anindya, 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)

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

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

Bipartite Exact Matching in P
by: Du, Yuefeng
Published: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Subset Balancing and Generalized Subset Sum via Lattices
by: Gao, Yiming, et al.
Published: (2026)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
by: Firbas, Alexander, et al.
Published: (2024)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

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

Work-Efficient Parallel Counting via Sampling
by: Liu, Hongyang, et al.
Published: (2024)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

A general framework for finding diverse solutions via network flow and its applications
by: Iwamasa, Yuni, et al.
Published: (2025)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)