Too much information: Why CDCL solvers need to forget learned clauses.

Conflict-driven clause learning (CDCL) is a remarkably successful paradigm for solving the satisfiability problem of propositional logic. Instead of a simple depth-first backtracking approach, this kind of solver learns the reason behind occurring conflicts in the form of additional clauses. However, despite the enormous success of CDCL solvers, there is still only a limited understanding of what influences the performance of these solvers in what way. Considering different measures, this paper demonstrates, quite surprisingly, that clause learning (without being able to get rid of some clauses) can not only help the solver but can oftentimes deteriorate the solution process dramatically. By conducting extensive empirical analysis, we furthermore find that the runtime distributions of CDCL solvers are multimodal. This multimodality can be seen as a reason for the deterioration phenomenon described above. Simultaneously, it also gives an indication of why clause learning in combination with clause deletion is virtually the de facto standard of SAT solving, in spite of this phenomenon. As a final contribution, we show that Weibull mixture distributions can accurately describe the multimodal distributions. Thus, adding new clauses to a base instance has an inherent effect of making runtimes long-tailed. This insight provides an explanation as to why the technique of forgetting clauses is useful in CDCL solvers apart from the optimization of unit propagation speed.

Individual attitude change and societal dynamics: Computational experiments with psychological theories.

We present an agent-based model for studying the societal implications of attitude change theories. Various psychological theories of persuasive communication at the individual level are implemented as simulation experiments. The model allows us to investigate the effects of contagion and assimilation, motivated cognition, polarity, source credibility, and idiosyncratic attitude formation. Simulations show that different theories produce different characteristic macrolevel patterns. Contagion and assimilation are central mechanisms for generating consensus, however, contagion generates a radicalized consensus. Motivated cognition causes societal polarization or the fragmentation of attitudes. Polarity and source credibility have comparatively little effect on the societal distribution of attitudes. We discuss how the simulations provide a bridge between microlevel psychological theories and the aggregated macrolevel studied by sociology. This approach enables new types of evidence for evaluating psychological theory to complement experimental approaches, thus answering calls to enhance the role of coherent and formalized theory in psychological science. (PsycInfo Database Record (c) 2021 APA, all rights reserved).

Statistical privacy-preserving message broadcast for peer-to-peer networks.

Privacy concerns are widely discussed in research and society in general. For the public infrastructure of financial blockchains, this discussion encompasses the privacy of the originator of a transaction broadcasted on the underlying peer-to-peer network. Adaptive diffusion is an approach to expose an alternative source of a message to attackers. However, this approach assumes an unsuitable attacker model and a non-realistic network model for current peer-to-peer networks on the Internet. We transform adaptive diffusion into a new statistical privacy-preserving broadcast protocol for realistic current networks. We model a class of unstructured peer-to-peer networks as organically growing graphs and provide models for other classes of such networks. We show that the distribution of shortest paths can be modelled using a normal distribution [Formula: see text]. We determine statistical estimators for µ, σ via multivariate models. The model behaves logarithmic over the number of nodes n and proportional to an inverse exponential over the number of added edges per node k. These results facilitate the computation of optimal forwarding probabilities during the dissemination phase for maximum privacy, with participants having only limited information about network topology.

Unobtrusive monitoring: Statistical dissemination latency estimation in Bitcoin's peer-to-peer network.

The cryptocurrency system Bitcoin uses a peer-to-peer network to distribute new transactions to all participants. For risk estimation and usability aspects of Bitcoin applications, it is necessary to know the time required to disseminate a transaction within the network. Unfortunately, this time is not immediately obvious and hard to acquire. Measuring the dissemination latency requires many connections into the Bitcoin network, wasting network resources. Some third parties operate that way and publish large scale measurements. Relying on these measurements introduces a dependency and requires additional trust. This work describes how to unobtrusively acquire reliable estimates of the dissemination latencies for transactions without involving a third party. The dissemination latency is modelled with a lognormal distribution, and we estimate their parameters using a Bayesian model that can be updated dynamically. Our approach provides reliable estimates even when using only eight connections, the minimum connection number used by the default Bitcoin client. We provide an implementation of our approach as well as datasets for modelling and evaluation. Our approach, while slightly underestimating the latency distribution, is largely congruent with observed dissemination latencies.

The triple-filter bubble: Using agent-based modelling to test a meta-theoretical framework for the emergence of filter bubbles and echo chambers.

Filter bubbles and echo chambers have both been linked recently by commentators to rapid societal changes such as Brexit and the polarization of the US American society in the course of Donald Trump's election campaign. We hypothesize that information filtering processes take place on the individual, the social, and the technological levels (triple-filter-bubble framework). We constructed an agent-based modelling (ABM) and analysed twelve different information filtering scenarios to answer the question under which circumstances social media and recommender algorithms contribute to fragmentation of modern society into distinct echo chambers. Simulations show that, even without any social or technological filters, echo chambers emerge as a consequence of cognitive mechanisms, such as confirmation bias, under conditions of central information propagation through channels reaching a large part of the population. When social and technological filtering mechanisms are added to the model, polarization of society into even more distinct and less interconnected echo chambers is observed. Merits and limits of the theoretical framework, and more generally of studying complex social phenomena using ABM, are discussed. Directions for future research such as ways of comparing our simulations with actual empirical data and possible measures against societal fragmentation on the three different levels are suggested.

Completion Probabilities and Parallel Restart Strategies under an Imposed Deadline.

Let A be any fixed cut-off restart algorithm running in parallel on multiple processors. If the algorithm is only allowed to run for up to time D, then it is no longer guaranteed that a result can be found. In this case, the probability of finding a solution within the time D becomes a measure for the quality of the algorithm. In this paper we address this issue and provide upper and lower bounds for the probability of A finding a solution before a deadline passes under varying assumptions. We also show that the optimal restart times for a fixed cut-off algorithm running in parallel is identical for the optimal restart times for the algorithm running on a single processor. Finally, we conclude that the odds of finding a solution scale superlinearly in the number of processors.

Redistribution spurs growth by using a portfolio effect on risky human capital.

We demonstrate by mathematical analysis and systematic computer simulations that redistribution can lead to sustainable growth in a society. In accordance with economic models of risky human capital, we assume that dynamics of human capital is modeled as a multiplicative stochastic process which, in the long run, leads to the destruction of individual human capital. When agents are linked by fully redistributive taxation the situation might turn to individual growth in the long run. We consider that a government collects a proportion of income and reduces it by a fraction as costs for administration (efficiency losses). The remaining public good is equally redistributed to all agents. Sustainable growth is induced by redistribution despite the losses from the random growth process and despite administrative costs. Growth results from a portfolio effect. The findings are verified for three different tax schemes: proportional tax, taking proportionally more from the rich, and proportionally more from the poor. We discuss which of these tax schemes performs better with respect to maximize growth under a fixed rate of administrative costs, and the governmental income. This leads us to general conclusions about governmental decisions, the relation to public good games with free riding, and the function of taxation in a risk-taking society.

How social influence can undermine the wisdom of crowd effect.

Social groups can be remarkably smart and knowledgeable when their averaged judgements are compared with the judgements of individuals. Already Galton [Galton F (1907) Nature 75:7] found evidence that the median estimate of a group can be more accurate than estimates of experts. This wisdom of crowd effect was recently supported by examples from stock markets, political elections, and quiz shows [Surowiecki J (2004) The Wisdom of Crowds]. In contrast, we demonstrate by experimental evidence (N = 144) that even mild social influence can undermine the wisdom of crowd effect in simple estimation tasks. In the experiment, subjects could reconsider their response to factual questions after having received average or full information of the responses of other subjects. We compare subjects' convergence of estimates and improvements in accuracy over five consecutive estimation periods with a control condition, in which no information about others' responses was provided. Although groups are initially "wise," knowledge about estimates of others narrows the diversity of opinions to such an extent that it undermines the wisdom of crowd effect in three different ways. The "social influence effect" diminishes the diversity of the crowd without improvements of its collective error. The "range reduction effect" moves the position of the truth to peripheral regions of the range of estimates so that the crowd becomes less reliable in providing expertise for external observers. The "confidence effect" boosts individuals' confidence after convergence of their estimates despite lack of improved accuracy. Examples of the revealed mechanism range from misled elites to the recent global financial crisis.

Measuring single small molecule binding via rupture forces of a split aptamer.

The rupture force of a split (bipartite) aptamer that forms binding pockets for adenosine monophosphate (AMP) was measured by atomic force spectroscopy. Changes in the rupture force were observed in the presence of AMP, while this effect was absent when mutant aptamers or inosine were used. Thus, changes in the rupture force were a direct consequence of specific binding of AMP to the split aptamer. The split aptamer concept allowed the detection of nonlabeled AMP and enabled us to determine the dissociation constant on a single-molecule level.