On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,742 papers · 148 categories

Trend · papers per month

count % of corpus

6 results for “k-SAT”

One-Shot Learning for k-SATcs.DS

Learning β for k-SAT with one sample is hard, especially for low degrees.

problem Learning the parameter β for k-SAT with a single sample.

method Single-sample learning of k-SAT formulas with a given satisfying assignment.

result One-shot learning for k-SAT is infeasible well below the satisfiability threshold, even for low degrees.

k-SAT one-shot learning satisfiability threshold Markov random fields

2025-02-10abs ↗pdf ↗

The Algorithmic Phase Transition of Random

k

-SAT for Low Degree Polynomialscs.CC

New study shows low-degree polynomial algorithms struggle at clause densities close to Fix's.

problem Finding satisfying assignments in random k-SAT formulas at high clause densities.

method Analysis of low-degree polynomial algorithms and a new many-way overlap gap property.

result No efficient algorithms can find satisfying assignments at clause densities close to Fix's.

k-SAT random formulas low-degree polynomials clause density satisfying assignment

2021-06-03abs ↗pdf ↗

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Samplecs.LG

Estimates inverse temperature of Ising models with a single sample.

problem Estimating inverse temperature in truncated Ising models with hard constraints.

method Maximizing pseudolikelihood to estimate the inverse temperature.

result An estimator that is nearly

O(n)

time and

O(Δ^3/\sqrt{n})

-consistent.

Ising model Inverse temperature Truncated probability Pseudolikelihood Consistency

2025-09-25abs ↗pdf ↗

Learning Hard-Constrained Models with One Samplecs.LG

Single sample estimation for hard-constrained models like SAT and coloring problems.

problem Estimating parameters of Markov Random Fields with hard constraints using a single sample.

method Pseudo-likelihood estimator with coupling techniques.

result Single-sample estimation is not always possible for hard constraints, and existence of an estimator is related to satisfiability.

Markov Random Field Hard Constraints Single Sample Estimation Pseudo-Likelihood Coupling Techniques

2023-11-06abs ↗pdf ↗

Streamlining Variational Inference for Constraint Satisfaction Problemscs.AI

Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and …

2018-11-24abs ↗pdf ↗

On the Fine-Grained Hardness of Inverting Generative Modelsstat.ML

This paper explores the computational hardness of generating latent vectors for generative models.

problem Computational hardness of generating latent vectors for generative models.

method Established lower bounds for exact and approximate model inversion under strong exponential time hypothesis (SETH) and exponential time hypothesis (ETH).

result Lower bounds for computational complexity of exact and approximate model inversion.

Generative models Latent vectors Computational hardness NP-hard Exact inversion

2023-09-11abs ↗pdf ↗