Cover Image

Sampling permutations satisfying constraints within the lopsided local lemma regime

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	He, Kun, Qiu, Guoliang, Sun, Xiaoming
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

FPTAS for Holant Problems with Log-Concave Signatures
by: He, Kun, et al.
Published: (2024)

Learning CNF formulas from uniform random solutions in the local lemma regime
by: Feng, Weiming, et al.
Published: (2025)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
by: Liu, Jingcheng, et al.
Published: (2026)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Compact representations of pattern-avoiding permutations
by: Kozma, László, et al.
Published: (2025)

Counting random $k$-SAT near the satisfiability threshold
by: Chen, Zongchen, et al.
Published: (2024)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
by: Wan, Zongqi, et al.
Published: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)

A refined graph container lemma and applications to the hard-core model on bipartite expanders
by: Jenssen, Matthew, et al.
Published: (2024)

Parameterised algorithms for temporally satisfying reconfiguration problems
by: Davot, Tom, et al.
Published: (2025)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
by: Jin, Mingming, et al.
Published: (2023)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

The PRODSAT phase of random quantum satisfiability
by: Lee, Joon, et al.
Published: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
by: Harris, David G., et al.
Published: (2017)

Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
by: Ma, Xinran, et al.
Published: (2025)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Indexing Tries within Entropy-Bounded Space
by: Carfagna, Lorenzo, et al.
Published: (2025)

Phase transition of the Sinkhorn-Knopp algorithm
by: He, Kun
Published: (2025)

On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
by: He, Kun
Published: (2026)

Testability of relations between permutations
by: Becker, Oren, et al.
Published: (2020)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

A polynomial kernel for vertex deletion into bipartite permutation graphs
by: Derbisz, Jan
Published: (2021)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Fast Sampling Based Sketches for Tensors
by: Swartworth, William, et al.
Published: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

Sorting with constraints
by: Manas, A.
Published: (2025)

Efficient Computation of Periods and Covers Using Sampling
by: Lecroq, Thierry, et al.
Published: (2024)

Optimal Phylogenetic Reconstruction from Sampled Quartets
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Online Sampling and Decision Making with Low Entropy
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2021)

Weighted Reservoir Sampling With Replacement from Data Streams
by: Meligrana, Adriano, et al.
Published: (2024)

Efficient Leverage Score Sampling for Tensor Train Decomposition
by: Bharadwaj, Vivek, et al.
Published: (2024)

Stochastic Minimum Spanning Trees with a Single Sample
by: Hoeksma, Ruben, et al.
Published: (2024)

Revisit the Partial Coloring Method: Prefix Spencer and Sampling
by: Cai, Dongrun, et al.
Published: (2024)

Perfect Sampling in Turnstile Streams Beyond Small Moments
by: Woodruff, David P., et al.
Published: (2025)