Lowered crossover points of Anthropic's subexponential 3-SAT algorithm
cs.CC, cs.DS
Submitted: 2026-10-30
Updated: 2026-10-30
Code: https://github.com/Majdoddin/anthropic-3sat-crossover
Terminology
Sources
- Universal points in the asymptotic spectrum of tensors
- Asymptotic tensor rank of graph tensors: beyond matrix multiplication
- Tensor network complexity of multilinear maps
- Inequalities for the Ranks of Quantum States
- A complete picture of the four-party linear inequalities in terms of the 0-entropy
- Multiplying matrices via polynomials: exposition and barriers
- Asymptotic Rank Speedup Theorems, Revisited
- New Algorithms for #2-SAT and #3-SAT
- Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
- A Better Analysis For PPSZ For 3-SAT
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
- Uniform CSP Parameterized by Solution Size is in W[1]
- Tensor network ranks
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?