Cover Image

Counting random $k$-SAT near the satisfiability threshold

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Zongchen, Lonkar, Aditya, Wang, Chunyang, Yang, Kuan, Yin, Yitong
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

Phase Transitions via Complex Extensions of Markov Chains
by: Liu, Jingcheng, et al.
Published: (2024)

Random local access for sampling k-SAT solutions
by: Dong, Dingding, et al.
Published: (2024)

Spectral Independence via Stability and Applications to Holant-Type Problems
by: Chen, Zongchen, et al.
Published: (2021)

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

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

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

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

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

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

Faster Mixing of the Jerrum-Sinclair Chain
by: Chen, Xiaoyu, et al.
Published: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

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

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

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

Using random spanning trees in survivable networks design
by: Wrobel, Blazej, et al.
Published: (2025)

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

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, 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)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

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

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)

Counting Locally Optimal Tours in the TSP
by: Manthey, Bodo, et al.
Published: (2024)

Depth-13 Sorting Networks for 28 Channels
by: Wang, Chengu
Published: (2025)

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
by: Wang, Adam
Published: (2025)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
by: Wang, Chenhao
Published: (2025)

Explicit Min-wise Hash Families with Optimal Size
by: Chen, Xue, et al.
Published: (2025)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)

Correcting matrix products over the ring of integers
by: Wu, Yu-Lun, et al.
Published: (2023)

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

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

A near-optimal zero-free disk for the Ising model
by: Patel, Viresh, et al.
Published: (2023)

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)