Synthesising Programs with Non-trivial Constants.

Program synthesis is the mechanised construction of software. One of the main difficulties is the efficient exploration of the very large solution space, and tools often require a user-provided syntactic restriction of the search space. While useful in general, such syntactic restrictions provide little help for the generation of programs that contain non-trivial constants, unless the user is able to provide the constants in advance. This is a fundamentally difficult task for state-of-the-art synthesisers. We propose a new approach to the synthesis of programs with non-trivial constants that combines the strengths of a counterexample-guided inductive synthesiser with those of a theory solver, exploring the solution space more efficiently without relying on user guidance. We call this approach CEGIS(T), where T is a first-order theory. We present two exemplars, one based on Fourier-Motzkin (FM) variable elimination and one based on first-order satisfiability. We demonstrate the practical value of CEGIS(T) by automatically synthesising programs for a set of intricate benchmarks. Additionally, we present a case study where we integrate CEGIS(T) within the mature synthesiser CVC4 and show that CEGIS(T) improves CVC4's results.

The 'spiteful' origins of human cooperation.

We analyse generosity, second-party ('spiteful') punishment (2PP), and third-party ('altruistic') punishment (3PP) in a cross-cultural experimental economics project. We show that smaller societies are less generous in the Dictator Game but no less prone to 2PP in the Ultimatum Game. We might assume people everywhere would be more willing to punish someone who hurt them directly (2PP) than someone who hurt an anonymous third person (3PP). While this is true of small societies, people in large societies are actually more likely to engage in 3PP than 2PP. Strong reciprocity, including generous offers and 3PP, exists mostly in large, complex societies that face numerous challenging collective action problems. We argue that 'spiteful' 2PP, motivated by the basic emotion of anger, is more universal than 3PP and sufficient to explain the origins of human cooperation.

G2SAT: Learning to Generate SAT Formulas.

The Boolean Satisfiability (SAT) problem is the canonical NP-complete problem and is fundamental to computer science, with a wide array of applications in planning, verification, and theorem proving. Developing and evaluating practical SAT solvers relies on extensive empirical testing on a set of real-world benchmark formulas. However, the availability of such real-world SAT formulas is limited. While these benchmark formulas can be augmented with synthetically generated ones, existing approaches for doing so are heavily hand-crafted and fail to simultaneously capture a wide range of characteristics exhibited by real-world SAT instances. In this work, we present G2SAT, the first deep generative framework that learns to generate SAT formulas from a given set of input formulas. Our key insight is that SAT formulas can be transformed into latent bipartite graph representations which we model using a specialized deep generative neural network. We show that G2SAT can generate SAT formulas that closely resemble given real-world SAT instances, as measured by both graph metrics and SAT solver behavior. Further, we show that our synthetic SAT formulas could be used to improve SAT solver performance on real-world benchmarks, which opens up new opportunities for the continued development of SAT solvers and a deeper understanding of their performance.

Markets, religion, community size, and the evolution of fairness and punishment.

Large-scale societies in which strangers regularly engage in mutually beneficial transactions are puzzling. The evolutionary mechanisms associated with kinship and reciprocity, which underpin much of primate sociality, do not readily extend to large unrelated groups. Theory suggests that the evolution of such societies may have required norms and institutions that sustain fairness in ephemeral exchanges. If that is true, then engagement in larger-scale institutions, such as markets and world religions, should be associated with greater fairness, and larger communities should punish unfairness more. Using three behavioral experiments administered across 15 diverse populations, we show that market integration (measured as the percentage of purchased calories) positively covaries with fairness while community size positively covaries with punishment. Participation in a world religion is associated with fairness, although not across all measures. These results suggest that modern prosociality is not solely the product of an innate psychology, but also reflects norms and institutions that have emerged over the course of human history.

Costly punishment across human societies.

Recent behavioral experiments aimed at understanding the evolutionary foundations of human cooperation have suggested that a willingness to engage in costly punishment, even in one-shot situations, may be part of human psychology and a key element in understanding our sociality. However, because most experiments have been confined to students in industrialized societies, generalizations of these insights to the species have necessarily been tentative. Here, experimental results from 15 diverse populations show that (i) all populations demonstrate some willingness to administer costly punishment as unequal behavior increases, (ii) the magnitude of this punishment varies substantially across populations, and (iii) costly punishment positively covaries with altruistic behavior across populations. These findings are consistent with models of the gene-culture coevolution of human altruism and further sharpen what any theory of human cooperation needs to explain.