Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 2 of 2 for “"Random CSP"”.
-
Resolution Complexity of Random Constraint Satisfaction Problems
The resolution complexity of random constraint satisfaction problems is a widely studied topic. This line of research started with a seminal paper by Chvátal and Szemeréd. They showed that for any 𝑘 ≥ 3, w.h.p. an unsatisfiable random 𝑘-SAT instance has exponentially high resolution complexity when …
-
Two Studies of Constraints in High Dimensions: Entropy Inequalities and the Randomized Symmetric Binary Perceptron
… and a toy shallow neural network which stores random patterns; we also study a randomized variant of the symmetric binary perceptron. We first consider the (k + 1)-th derivative of xᵏ⁻ʳH(xʳ), where H(x) := −x log x − (1 − x) log (1 − x),0 ≤ x ≤ 1 is the binary entropy and k ≥ r ≥ 1 are …