Imagen de Portada

Low-Sensitivity Matching via Sampling from Gibbs Distributions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Yoshida, Yuichi, Zhang, Zihan
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Detecting Low-Degree Truncation
por: De, Anindya, et al.
Publicado: (2024)

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

Testing Properties of Edge Distributions
por: Fei, Yumou
Publicado: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Improved Algorithm for Permutation Testing
por: Zhang, Xiaojin
Publicado: (2020)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
por: Zhang, Bingwei, et al.
Publicado: (2026)

Bipartite Exact Matching in P
por: Du, Yuefeng
Publicado: (2026)

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