@conference {4882, title = {The Community Structure of SAT Formulas}, booktitle = {Proc. of the 15th Int. Conf. on Theory and Applications of Satisfiability Testing, SAT{\textquoteright}12}, volume = {7317}, year = {2012}, month = {17/06/2012}, pages = {410-423}, publisher = {Springer}, organization = {Springer}, address = {Trento, Italy}, abstract = {The research community on complex networks has developed techniques of analysis and algorithms that can be used by the SAT community to improve our knowledge about the structure of industrial SAT instances. It is often argued that modern SAT solvers are able to exploit this hidden structure, without a precise definition of this notion. In this paper, we show that most industrial SAT instances have a high modularity that is not present in random instances. We also show that successful techniques, like learning, (indirectly) take into account this community structure. Our experimental study reveal that most learnt clauses are local on one of those modules or communities. }, author = {Carlos Ans{\'o}tegui and Jes{\'u}s Gir{\'a}ldez-Cru and Jordi Levy}, editor = {Alessandro Cimatti and Roberto Sebastiani} }