2003/12/05 by Giorgio Parisi, Parisi, Giorgio
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Physical sciences #G.2.1 #G.2.1 G.3 #G.3 #cond-mat.dis-nn #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0312011
22 pages, 1 figure Lectures given at the Varenna summer school
arxiv created 2003/12/05 · openalex publication_date 2003/12/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In these lectures I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics techniques. After presenting the general results, in order to simplify the presentation I will describe in details only the problems related to the coloring of a random graph.