English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This thesis is divided in two parts. The first presents an overview of knownresults in statistical mechanics of disordered systems and its approach torandom combinatorial optimization problems. The second part is a discussion oftwo original results.  The first result concerns DPLL heuristics for random k-XORSAT, which isequivalent to the diluted Ising p-spin model. It is well known that DPLL isunable to find the ground states in the clustered phase of the problem, i.e.that it leads to contradictions with probability 1. However, no solid argumentsupports this is general. A class of heuristics, which includes the well knownUC and GUC, is introduced and studied. It is shown that any heuristic in thisclass must fail if the clause to variable ratio is larger than some constant,which depends on the heuristic but is always smaller than the clusteringthreshold.  The second result concerns the properties of random k-SAT at large clause tovariable ratios. In this regime, it is well known that the uniform distributionof random instances is dominated by unsatisfiable instances. A generaltechnique (based on the Replica method) to restrict the distribution tosatisfiable instances with uniform weight is introduced, and is used tocharacterize their solutions. It is found that in the limit of large clause tovariable ratios, the uniform distribution of satisfiable random k-SAT formulasis asymptotically equal to the much studied Planted distribution.  Both results are already published and available as arXiv:0709.0367 andarXiv:cs/0609101 . A more detailed and self-contained derivation is presentedhere.

Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT