Copertina

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kocurek, Nicholas, Gharan, Shayan Oveis, Tjowasi, Dante
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
di: Leake, Jonathan, et al.
Pubblicazione: (2025)

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

On approximability of the Permanent of PSD matrices
di: Ebrahimnejad, Farzam, et al.
Pubblicazione: (2024)

On Thin Perfect Matchings up to Polylogarithmic Factors
di: Haqi, Alireza, et al.
Pubblicazione: (2026)

Most Juntas Saturate the Hardcore Lemma
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
di: Gharan, Shayan Oveis, et al.
Pubblicazione: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
di: Blanc, Guy, et al.
Pubblicazione: (2024)

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

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

Exact Algorithms for Distance to Unique Vertex Cover
di: Fioravantes, Foivos, et al.
Pubblicazione: (2025)

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

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
di: Chen, Yu-Zhen Janice, et al.
Pubblicazione: (2025)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Bipartite Exact Matching in P
di: Du, Yuefeng
Pubblicazione: (2026)

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

Coloring Graphs with Few Colors in the Streaming Model
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
di: Yoshida, Yuichi, et al.
Pubblicazione: (2025)

Randomized query composition and product distributions
di: Sanyal, Swagato
Pubblicazione: (2024)

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

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

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
di: Rao, Satish
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
di: Clinch, Katie, et al.
Pubblicazione: (2025)

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

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

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

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

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
di: Dey, Palash, et al.
Pubblicazione: (2025)

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

The Parameterized Landscape of Labeled Graph Contractions
di: Lafond, Manuel, et al.
Pubblicazione: (2025)

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

Streaming Complexity Separations for Dense and Sparse Graphs
di: Liu, Yang P., et al.
Pubblicazione: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
di: Chudigiewitsch, Florian, et al.
Pubblicazione: (2026)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
di: Esmer, Barış Can, et al.
Pubblicazione: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2024)

Colouring $(P_r+P_s)$-Free Graphs
di: Klimošová, Tereza, et al.
Pubblicazione: (2018)

The Query Complexity of Local Search in Rounds on General Graphs
di: Brânzei, Simina, et al.
Pubblicazione: (2026)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
di: Dvořák, Pavel, et al.
Pubblicazione: (2022)