This paper presents a novel spectral algorithm with additive clustering designed to identify overlapping communities in networks. The algorithm is based on geometric properties of the spectrum of the expected adjacency matrix in a random graph model
that we call stochastic blockmodel with overlap (SBMO). An adaptive version of the algorithm, that does not require the knowledge of the number of hidden communities, is proved to be consistent under the SBMO when the degrees in the graph are (slightly more than) logarithmic. The algorithm is shown to perform well on simulated data and on real-world graphs with known overlapping communities.
The halting problem is undecidable --- but can it be solved for most inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural fram
ework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-Lof random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approxima
Spin-orbit effects [1-4] have the potential of radically changing the field of spintronics by allowing transfer of spin angular momentum to a whole new class of materials. In a seminal letter to Nature [5], Kajiwara et al. showed that by depositing P
latinum (Pt, a normal metal) on top of a 1.3 $mu$m thick Yttrium Iron Garnet (YIG, a magnetic insulator), one could effectively transfer spin angular momentum through the interface between these two different materials. The outstanding feature was the detection of auto-oscillation of the YIG when enough dc current was passed in the Pt. This finding has created a great excitement in the community for two reasons: first, one could control electronically the damping of insulators, which can offer improved properties compared to metals, and here YIG has the lowest damping known in nature; second, the damping compensation could be achieved on very large objects, a particularly relevant point for the field of magnonics [6,7] whose aim is to use spin-waves as carriers of information. However, the degree of coherence of the observed auto-oscillations has not been addressed in ref. [5]. In this work, we emphasize the key role of quasi-degenerate spin-wave modes, which increase the threshold current. This requires to reduce both the thickness and lateral size in order to reach full damping compensation [8] , and we show clear evidence of coherent spin-orbit torque induced auto-oscillation in micron-sized YIG discs of thickness 20 nm.
I give an epistemological analysis of the developments of relativistic cosmology from 1917 to 1966, based on the seminal articles by Einstein, de Sitter, Friedmann, Lemaitre, Hubble, Gamow and other historical figures of the field. It appears that mo
st of the ingredients of the present-day standard cosmological model, including the acceleration of the expansion due to a repulsive dark energy, the interpretation of the cosmological constant as vacuum energy or the possible non-trivial topology of space, had been anticipated by Georges Lemaitre, although his articles remain mostly unquoted.
We study pure-strategy Nash equilibria in multi-player concurrent deterministic games, for a variety of preference relations. We provide a novel construction, called the suspect game, which transforms a multi-player concurrent game into a two-player
turn-based game which turns Nash equilibria into winning strategies (for some objective that depends on the preference relations of the players in the original game). We use that transformation to design algorithms for computing Nash equilibria in finite games, which in most cases have optimal worst-case complexity, for large classes of preference relations. This includes the purely qualitative framework, where each player has a single omega-regular objective that she wants to satisfy, but also the larger class of semi-quantitative objectives, where each player has several omega-regular objectives equipped with a preorder (for instance, a player may want to satisfy all her objectives, or to maximise the number of objectives that she achieves.)
On its way to turbulence, plane Couette flow - the flow between counter-translating parallel plates - displays a puzzling steady oblique laminar-turbulent pattern. We approach this problem via Galerkin modelling of the Navier-Stokes equations. The wa
ll-normal dependence of the hydrodynamic field is treated by means of expansions on functional bases fitting the boundary conditions exactly. This yields a set of partial differential equations for the spatiotemporal dynamics in the plane of the flow. Truncating this set beyond lowest nontrivial order is numerically shown to produce the expected pattern, therefore improving over what was obtained at cruder effective wall-normal resolution. Perspectives opened by the approach are discussed.
During the pre-Swift era, a clustering of light curves was observed in the X-ray, optical and infrared afterglow of gamma-ray bursts. We used a sample of 254 GRB X-ray afterglows to check this fact in the Swift era. We corrected fluxes for distance,
time dilation and losses of energy due to cosmological effects. With all our data in hand, we faced with a problem: our data were scattered. We investigated 3 possibilities to explain this, namely: the clustering does not exist, there are problems during calibration of data, and there are instrumental problems. We finally confirm that our sample is consistent with Dainotti correlation.
The softened point mass model is commonly used in simulations of gaseous discs including self-gravity while the value of associated length lambda remains, to some degree, controversial. This ``parameter is however fully constrained when, in a discret
ized disc, all fluid cells are demanded to obey Newtons law. We examine the topology of solutions in this context, focusing on cylindrical cells more or less vertically elongated. We find that not only the nominal length depends critically on the cells shape (curvature, radial extension, height), but it is either a real or an imaginary number. Setting lambda as a fraction of the local disc thickness -- as usually done -- is indeed not the optimal choice. We then propose a novel prescription valid irrespective of the disc properties and grid spacings. The benefit, which amounts to 2-3 more digits typically, is illustrated in a few concrete cases. A detailed mathematical analysis is in progress.
Paper in honour of Michel Henon, based on a talk presented at Institut Henri Poincare, Paris, 5 Decembre 2013.
We report on the archival near-infrared and mid-infrared observations of 7 persistent X-ray sources situated in the Galactic bulge using data from the UKIRT Infrared Deep Sky Survey (UKIDSS), Spitzer Galactic Legacy Infrared Mid-Plane Survey Extraord
inaire (GLIMPSE) and the Wide-field Infrared Survey Explorer (WISE) all-sky survey. We were able to successfully identify, or provide upper flux limits for the systems SAX J1747.0-2853, IGR J17464-2811, AX J1754.2-2754, IGR J17597-2201, IGR J18134-1636, IGR J18256-1035, Ser X-1 and constrain the nature of these systems. In the case of IGR J17597-2201 we present arguments that the source accretes matter from the stellar wind rather than via Roche lobe overflow of the secondary. We suggest that, at its X-ray luminosity of $10^{34-35}$ erg s$^{-1}$, we are probing the poorly known class of wind-fed low-mass X-ray binaries (LMXBs).
