No article text was recorded for this version.
computational phase transition
Version 2 of 2482 papers867 conceptsfrozen 2026-10-04
Papers in this version
- Blog: On the Scaling Window of Model RB
- Blog: Experimental Results on the Crossover Point in Satisfiability Problems
- Blog: Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem
- Blog: Exact Phase Transitions in Random Constraint Satisfaction Problems
- Blog: A variational description of the ground state structure in random satisfiability problems
- Blog: Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms
- Blog: On the average similarity degree between solutions of random k-SAT and random CSPs
- Blog: Hard and Easy Distributions of SAT Problems
- Blog: Phase Transition Behavior of Cardinality and XOR Constraints
- Blog: Combining the
- Blog: Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm
- Blog: On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs
- Blog: Using Deep Structure to Locate Hard Problems
- Blog: Theoretical Analysis of Davis-Putnam Procedure and Propositional Satisfiability
- Blog: On the hardness of sampling independent sets beyond the tree threshold
- Blog: Phase Transitions in Knowledge Compilation: an Experimental Study
- Blog: Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances
- Blog: Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
- Blog: Generating Satisfiable Problem Instances
- Blog: Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
- Blog: Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems
- Blog: Towards Interesting Patterns of Hard CSPs with Functional Constraints
- Blog: Phase Transitions in Knowledge Compilation: An Experimental Study
- Blog: The airplane refueling problem is NP-complete and is solvable in polynomial time
- Blog: Can Large Language Models Reason? A Characterization via 3-SAT
- Blog: Combining the k-CNF and XOR Phase-Transitions
- Blog: Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3
- Blog: Statistical mechanics of an NP-complete problem: subset sum
- Blog: Hiding quiet solutions in random constraint satisfaction problems
- Blog: Threshold values of random <i>K</i>‐SAT from the cavity method
- Blog: Statistical Physics of Hard Optimization Problems
- Blog: Combining the k-CNF and XOR Phase-Transitions
- Blog: Exact Phase Transitions and Approximate Algorithm of #CSP
- Blog: Theoretical Analysis of Davis-Putnam Procedure and Propositional
- Blog: Exact Phase Transitions of Model RB with Slower-Growing Domains
- Blog: Where the Really Hard Problems Are
- Blog: Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
- Blog: A Simple Model to Generate Hard Satisfiable Instances
- Blog: Relational Learning as Search in a Critical Region
- Blog: Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs
- Blog: Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
- Blog: Phase Transitions of the Asymmetric Traveling Salesman
- Blog: Finite-Size Scaling in Random $K$-Satisfiability Problems
- Blog: Cost-Based Heuristics and Node Re-Expansions across the Phase Transition
- Blog: Exploiting Problem Structure in Genetic Algorithms
- Blog: Branching Process approach for 2-SAT thresholds
- Blog: Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
- Blog: Backtracking Algorithms for Disjunctions of Temporal Constraints
- Blog: Quiet Planting in the Locked Constraint Satisfaction Problems
- Blog: An Average Analysis of Backtracking on Random Constraint Satisfaction Problems
- Blog: Max 2-SAT with up to 108 qubits
- Blog: The Statistical Mechanics of k-Satisfaction
- Blog: Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
- Blog: Approximate Counting via Correlation Decay in Spin Systems
- Blog: Exact phase transition of backtrack-free search with implications on the power of greedy algorithms
- Blog: Have Large Language Models Learned to Reason? A Characterization via 3-SAT
- Blog: On Computational Complexity of Pickup-and-Delivery Problems with Precedence Constraints or Time Windows
- Blog: Generating Weighted MAX-2-SAT Instances of Tunable Difficulty with Frustrated Loops
- Blog: Parametrized Families of Hard Planning Problems from Phase Transitions
- Blog: Hiding Quiet Solutions in Random Constraint Satisfaction Problems
Showing 60 of 482 papers.
History & citation
Current · Permanent link
- The Freezing Transition and Algorithmic Hardness in CSPs merged into this direction (70% overlap)
- Survey Propagation for Shattered Constraint Satisfaction Landscapes merged into this direction (68% overlap)
- higher-order SAT generalization split from this direction (63% overlap)
- power-law variable distribution split from this direction (60% overlap)
- solution space shattering split from this direction (53% overlap)
- satisfiability threshold gap split from this direction (78% overlap)
- algorithm-dependent problem hardness split from this direction (64% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_computational_phase_transition_32fa8730,
title = {computational phase transition},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-phase-transition/rdr_32fa8730d64b480dbb499c7f2da7efac},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}This exact version (version 2, frozen text):
@misc{lacuna_computational_phase_transition_32fa8730_v2,
title = {computational phase transition},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-phase-transition/rdr_32fa8730d64b480dbb499c7f2da7efac/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}