Syllabus
* Critical phenomena
Phenomenology of critical phenomena, singular behavior near critical point, critical exponents, universality, universality classes.
* Algorithmic complexity
P, NP, NP-complete problems, relation to slow dynamics close to critical point, cellular automata, self-organized criticality
* Network theory and random graphs
Erdös-Rényi model, scale-free networks
* Combinatorial optimization simulated annealing, replica method, spin glasses, neural networks, travelling salesman problem, K-SAT
Annotation
The lecture represents an introduction into an area where statistical physics and computer science meet. We show how the algorithmic complexity relates to critical behavior close to phase transition. We explain the methods used in statistical physics of complex systems and applied in modelling complex networks by random graphs, in combinatorial optimization and algorithm design.
For master and PhD students.