Cover Image

Random local access for sampling k-SAT solutions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dong, Dingding, Mani, Nitya
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Strong spatial mixing for colorings on trees and its algorithmic applications
by: Chen, Zongchen, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
by: Xiao, Chenglong, et al.
Published: (2024)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
by: Zhan, Yongjian
Published: (2026)

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Proceedings of the 13th edition of the conference on Random Generation of Combinatorial Structures. Polyominoes and Tilings
by: Brlek, Srečko, et al.
Published: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Thin Trees via $k$-Respecting Cut Identities
by: Daga, Mohit
Published: (2025)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
by: Ingels, Florian, et al.
Published: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

A Uniformly Random Solution to Algorithmic Redistricting
by: Cai, Jin-Yi, et al.
Published: (2024)

Enumerating minimal solution sets for metric graph problems
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
by: Carlson, Charlie, et al.
Published: (2024)

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

Sink-free orientations: a local sampler with applications
by: Anand, Konrad, et al.
Published: (2025)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

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

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
by: Tan, Jingjing
Published: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Generation of weighted trees, block trees and block graphs
by: Ekim, Tınaz, et al.
Published: (2024)

Circular-arc graphs and the Helly property
by: Derbisz, Jan, et al.
Published: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
by: Harada, Tsubasa, et al.
Published: (2024)

Deterministic counting from coupling independence
by: Chen, Xiaoyu, et al.
Published: (2024)