Abstract: The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilon-error, R-round, b-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)).

Abstract: The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the kth level of the Sherali--Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory.

Abstract: Consensus is an emergent property of many complex systems, considering this as an absolute majority phenomenon. In this work we study consensus dynamics in grids (in silicon), where individuals (the vertices) with two possible opinions (binary states) interact with the eight nearest neighbors (Moore’s neighborhood). Dynamics emerge once the majority rule drives the evolution of the system. In this work, we fully characterize the sub-neighborhoods on which the consensus may be reached or not. Given this, we study the quality of the consensus proposing two new measures, namely effectiveness and efficiency. We characterize attraction basins through the energy-like and magnetization-like functions similar to the Ising spin model.

Abstract: In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all n-node labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved.

Abstract: In this paper, we present the development of a low-cost multi-agent system experimental platform for teaching, and research purposes. The platform consists of train-like autonomous agents equipped with local speed estimation, distance sensing to their nearest predecessor, and wireless communications with other agents and a central coordinator. The individual agents can be used for simple PID experiments in a classroom or laboratory setting, while a collection of agents are capable of performing decentralized platooning with cooperative adaptive cruise control in a variety of settings, the latter being the main goal of the platform. The agents are built from low cost components and programmed with open source software, enabling teaching experiences and experimental work with a larger number of agents that would otherwise be possible with other existing solutions. Additionally, we illustrate with experimental results some of the teaching activities that the platform is capable of performing.

Abstract: Numerous approaches have been developed to control the crystalline and morphology of calcium carbonate. In this paper, nanobubbles were studied as a novel aid for the structure transition from vaterite to calcite. The vaterite particles turned into calcite (100%) in deionized water containing nanobubbles generated by high-speed shearing after 4 h, in comparison to a mixture of vaterite (33.6%) and calcite (66.3%) by the reaction in the deionized water in the absence of nanobubbles. The nanobubbles can coagulate with calcite based on the potential energy calculated and confirmed by the extended DLVO (Derjaguin-Landau-Verwey-Overbeek) theory. According to the nanobubble bridging capillary force, nanobubbles were identified as the binder in strengthening the coagulation between calcite and vaterite and accelerated the transformation from vaterite to calcite.