Local and Global Interactions in an Evolutionary Resource Game

Conditions for the emergence of cooperation in a spatial common-pool resource game are studied. This combines in a unique way local and global interactions. A fixed number of harvesters are located on a spatial grid. Harvesters choose among three strategies: defection, cooperation, and enforcement. Individual payoffs are affected by both global factors, namely, aggregate harvest and resource stock level, and local factors, such as the imposition of sanctions on neighbors by enforcers. The evolution of strategies in the population is driven by social learning through imitation, based on local interaction or locally available information. Numerous types of equilibria exist in these settings. An important new finding is that clusters of cooperators and enforcers can survive among large groups of defectors. We discuss how the results contrast with the non-spatial, but otherwise similar, game of Sethi and Somanathan (American Economic Review 86(4):766–789, 1996).      

The cell probe complexity of succinct data structures

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n$n$-bit data with s=n+r$s=n+r$ bits such that queries (of a certain type) about the data can be answered by reading at most t$t$ bits of the representation. Ideally, we would like to keep both s$s$ and t$t$ small, but there are tradeoffs between the values of s$s$ and t$t$ that limit the possibilities of keeping both parameters small.     

On partitioning a graph into two connected subgraphs

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known as the 2-Disjoint Connected Subgraphs problem. It is already NP-complete for the class of n-vertex graphs G=(V,E) in which Z₁ and Z₂ each contain a connected set that dominates all vertices in V?(Z₁∪Z₂). We present an O^∗(1.2051ⁿ) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O^∗(1.2051ⁿ) time for the classes of n-vertex P₆-free graphs and split graphs. This is an improvement upon a recent O^∗(1.5790ⁿ) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer.     

A Hierarchical Grid Based Framework for Fast Collision Detection

We present a novel hierarchical grid based method for fast collision detection (CD) for deformable models on GPU architecture. A two‐level grid is employed to accommodate the non‐uniform distribution of practical scene geometry. A bottom‐to‐top method is implemented to assign the triangles into the hierarchical grid without any iteration while a deferred scheme is introduced to efficiently update the data structure. To address the issue of load balancing, which greatly influences the performance in SIMD parallelism, a propagation scheme which utilizes a parallel scan and a segmented scan is presented, distributing workloads evenly across all concurrent threads. The proposed method supports both discrete collision detection (DCD) and continuous collision detection (CCD) with self‐collision. Some typical benchmarks are tested to verify the effectiveness of our method. The results highlight our speedups over prior algorithms on different commodity GPUs.     

Treatment of uncertain material interfaces in compressible flows

To treat uncertain interface position is an important issue for complex applications. In this paper, we address the characterization of randomly perturbed interfaces between fluids thanks to stochastic modeling and uncertainty quantification through the 2D Euler system. The perturbed interface is modeled as a random field and represented by a Karhunen–Loève expansion. The stochastic 2D Euler system is solved applying Polynomial Chaos theory through the Intrusive Polynomial Moment Method (IPMM). This stochastic resolution method is fully explained and studied (theoretically and numerically). Stochastic Richtmyer–Meshkov unstable flows are solved and presented for several configurations of the uncertain interface (different rugosities) between the fluids. The probability density functions of the mass density of the fluid in the vicinity of the interface are computed built and compared for the different simulations: the system exhibits strong sensitivity with respect to the stochastic initially leading modes.     

Generalized Perpendicular Bisector and exhaustive discrete circle recognition

This paper presents a generalization of the notion of circumcenter as the intersection of perpendicular bisectors. We define Generalized Perpendicular Bisectors between two regions as an area where each point is the center of at least one circle crossing both regions. This allows us to determine all the possible discrete circle centers that cross a given set of pixels. The possible radii can then easily be determined. This exhaustive digital circle parameter computation is adapted to various types of circles/digitization schemes such as Naïve, Pythagorean and standard/supercover circles.     

Incremental Branching Programs

We propose a new model of restricted branching programs specific to solving GEN problems, which we call incremental branching programs. We show that syntactic incremental branching programs capture previously studied models of computation for the problem GEN, namely marking machines (Cook, S.A. in J. Comput. Syst. Sci. 9(3):308–316, 1974) and Poon’s extension (Proc. of the 34th IEEE Symp. on the Foundations of Computer Science, pp. 218–227, 1993) of jumping automata on graphs (Cook, S.A., Rackoff, C.W. in SIAM J. Comput. 9:636–652, 1980). We then prove exponential size lower bounds for our syntactic incremental model, and for some other variants of branching program computation for GEN. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN sub-problem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems. A preliminary version of this paper appears as (Gál, A., Koucky, M., McKenzie, P., Incremental branching programs, in Proc. of the 2006 Computer Science in Russia Conference CSR06. Lecture Notes in Computer Science, vol. 3967, pp. 178–190, 2006). A. Gal supported in part by NSF Grant CCF-0430695 and an Alfred P. Sloan Research Fellowship. M. Koucky did part of this work while being a postdoctoral fellow at McGill University, Canada and at CWI, Amsterdam, Netherlands. Supported in part by NWO vici project 2004–2009, project No. 1M0021620808 of MŠMT ČR, grants 201/07/P276, 201/05/0124 of GA ČR, and Institutional Research Plan No. AV0Z10190503. P. McKenzie supported by the NSERC of Canada and the (Québec) FQRNT.     

Integrating job parallelism in real-time scheduling theory

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.     

Food vacuole proteome of the malarial parasite Plasmodium falciparum

The Plasmodium falciparum food vacuole (FV) is a lysosome-like organelle where erythrocyte hemoglobin digestion occurs. It is a favorite target in the development of antimalarials. We have used a tandem mass spectrometry approach to investigate the proteome of an FV-enriched fraction and identified 116 proteins. The electron microscopy analysis and the Western blot data showed that the major component of the fraction was the FV and, as expected, the majority of previously known FV markers were recovered. Of particular interest, several proteins involved in vesicle-mediated trafficking were identified, which are likely to play a key role in FV biogenesis and/or FV protein trafficking. Recovery of parasite surface proteins lends support to the cytostomal pathway of hemoglobin ingestion as a FV trafficking route. We have identified 32 proteins described as hypothetical in the databases. This insight into FV protein content provides new clues towards understanding the biological function of this organelle in P. falciparum.