BIMSA Workshop on the physics of complex systemsMany physical, biological, engineering, and societal processes can be explained as complex systems, characterized by a large number of interacting degrees of freedom. The theoretical and computational tools for dissecting complex systems are founded on the physical principles, cross-pollinated by mathematics, statistics, ecology, evolutionary game...
AbstractLet Φ be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is, for most Φ, to (approximately) uniformly sample from its solution space.Let α=m/n be the density. The previous best algorithm runs in time n^poly(k,α) for any α≲2^(k/300) [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'2...