Covering problems are classical computational problems concerning whether a certain combinatorial structure 'covers' another. For example, the minimum vertex covering problem aims to find the smallest set of vertices in a graph so that each edge is incident to at least one vertex in that set. Interestingly, the computational complexity of the minimum vertex covering problem in graphs is closely related to the core percolation problem, where the core is a special subgraph obtained by the greedy leaf removal procedure. Here, by generalizing the greedy leaf removal procedure in graphs to hypergraphs, we introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for random hypergraphs with arbitrary vertex degree and hyperedge cardinality distributions. We also compute these two cores in several real-world hypergraphs, finding that they tend to be much smaller than their randomized counterparts. This result suggests that both the minimum hyperedge cover problem and the minimum vertex cover problem in those real-world hypergraphs can actually be solved in polynomial time. Finally, we map the minimum dominating set problem in graphs to the minimum hyperedge cover problem in hypergraphs. We show that our generalized greedy leaf removel procedure significantly outperforms the state-of-the-art method in solving the minimum dominating set problem.

In such different domains as neurosciences, spin glasses, social science, economics and finance, large ensemble of interacting individuals following (mainstream) or opposing (hipsters) to the majority are ubiquitous. In these systems, interactions generally occur after specific delays associated to transport, transmission or integration of information. We investigate here the impact of anti-conformism combined to delays in the emergent dynamics of large populations of mainstreams and hipsters. To this purpose, we introduce a class of simple statistical systems of interacting agents composed of (i) mainstreams and anti-conformists in the presence of (ii) delays, possibly heterogeneous, in the transmission of information. In this simple model, each agent can be in one of two states, and can change state in continuous time with a rate depending on the state of others in the past. We express the thermodynamic limit of these systems as the number of agents diverge, and investigate the solutions of the limit equation, with a particular focus on synchronized oscillations induced by delayed interactions. We show that when hipsters are too slow in detecting the trends, they will consistently make the same choice, and realizing this too late, they will switch, all together to another state where they remain alike. Similar synchronizations arise when the impact of mainstreams on hipsters choices (and reciprocally) dominate the impact of other hipsters choices, and we show that these may emerge only when the randomness in the hipsters decisions is sufficiently large. Beyond the choice of the best suit to wear this winter, this study may have important implications in understanding synchronization of nerve cells, investment strategies in finance, or emergent dynamics in social science, domains in which delays of communication and the geometry of information accessibility are prominent.

We report on the observation of suppression and revival of coherent backscattering of ultra-cold atoms launched in an optical disorder and submitted to a short dephasing pulse, as proposed in a recent paper of T. Micklitz \textit{et al.} [arXiv:1406.6915]. This observation, in a quasi-2D geometry, demonstrates a novel and general method to study weak localization by manipulating time reversal symmetry in disordered systems. In future experiments, this scheme could be extended to investigate higher order localization processes at the heart of Anderson (strong) localization.

Many-body-localized (MBL) systems do not thermalize under their intrinsic dynamics. The athermality of MBL, we propose, can be harnessed for thermodynamic tasks. We illustrate this ability by formulating an Otto engine cycle for a quantum many-body system. The system is ramped between a strongly localized MBL regime and a thermal (or weakly localized) regime. The difference between the energy-level correlations of MBL systems and of thermal systems enables mesoscale engines to run in parallel in the thermodynamic limit, enhances the engine's reliability, and suppresses worst-case trials. We estimate analytically and calculate numerically the engine's efficiency and per-cycle power. The efficiency mirrors the efficiency of the conventional thermodynamic Otto engine. The per-cycle power scales linearly with the system size and inverse-exponentially with a localization length. This work introduces a thermodynamic lens onto MBL, which, having been studied much recently, can now be considered for use in thermodynamic tasks.

The structure of the International Trade Network (ITN), whose nodes and links represent world countries and their trade relations respectively, affects key economic processes worldwide, including globalization, economic integration, industrial production, and the propagation of shocks and instabilities. Characterizing the ITN via a simple yet accurate model is an open problem. The traditional Gravity Model (GM) successfully reproduces the volume of trade between connected countries, using macroeconomic properties such as GDP, geographic distance, and possibly other factors. However, it predicts a network with complete or homogeneous topology, thus failing to reproduce the highly heterogeneous structure of the ITN. On the other hand, recent maximum-entropy network models successfully reproduce the complex topology of the ITN, but provide no information about trade volumes. Here we integrate these two currently incompatible approaches via the introduction of an Enhanced Gravity Model (EGM) of trade. The EGM is the simplest model combining the GM with the network approach within a maximum-entropy framework. Via a unified and principled mechanism that is transparent enough to be generalized to any economic network, the EGM provides a new econometric framework wherein trade probabilities and trade volumes can be separately controlled by any combination of dyadic and country-specific macroeconomic variables. The model successfully reproduces both the global topology and the local link weights of the ITN, parsimoniously reconciling the conflicting approaches. It also indicates that the probability that any two countries trade a certain volume should follow a geometric or exponential distribution with an additional point mass at zero volume.

Recent progress in applying complex network theory to problems in quantum information has resulted in a beneficial crossover. Complex network methods have successfully been applied to transport and entanglement models while information physics is setting the stage for a theory of complex systems with quantum information-inspired methods. Novel quantum induced effects have been predicted in random graphs---where edges represent entangled links---and quantum computer algorithms have been proposed to offer enhancement for several network problems. Here we review the results at the cutting edge, pinpointing the similarities and the differences found at the intersection of these two fields.

The Percus-Yevick theory for monodisperse hard spheres gives very good results for the pressure and structure factor of the system in a whole range of densities that lie within the liquid phase. However, the equation seems to lead to a very unacceptable result beyond that region. Namely, the Percus-Yevick theory predicts a smooth behavior of the pressure that diverges only when the volume fraction $\eta$ approaches unity. Thus, within the theory there seems to be no indication for the termination of the liquid phase and the transition to a solid or to a glass. In the present article we study the Percus-Yevick hard sphere pair distribution function, $g_2(r)$, for various spatial dimensions. We find that beyond a certain critical volume fraction $\eta_c$, the pair distribution function, $g_2(r)$, which should be positive definite, becomes negative at some distances. We also present an intriguing observation that the critical $\eta_c$ values we find are consistent with volume fractions where onsets of random close packing (or maximally random jammed states) are reported in the literature for various dimensions. That observation is supported by an intuitive argument. This work may have important implications for other systems for which a Percus-Yevick theory exists.

The "backward simulation" of a stochastic process is defined as the stochastic dynamics that trace a time-reversed path from the target region to the initial configuration. If the probabilities calculated by the original simulation are easily restored from those obtained by backward dynamics, we can use it as a computational tool. It is shown that the naive approach to backward simulation does not work as expected. As a remedy, the Time Reverse Monte Carlo method (TRMC) based on the ideas of Sequential Importance Sampling (SIS) and Sequential Monte Carlo (SMC) is proposed and successfully tested with a stochastic typhoon model and the Lorenz 96 model. TRMC with SMC, which contains resampling steps, is shown to be more efficient for simulations with a larger number of time steps. A limitation of TRMC and its relation to the Bayes formula are also discussed.

We report the results of a direct comparison of a freely expanding turbulent Bose-Einstein condensate and the propagation of an optical speckle pattern. We found remarkably similar statistical properties underlying the spatial propagation of both phenomena. The calculated second-order correlation together with the typical correlation length of each system is used to compare and substantiate our observations. We believe that the close analogy existing in between an expanding turbulent quantum gas and a traveling optical speckle, might burgeon into an exciting new research field investigating disordered quantum matter.

We use trace class scattering theory to exclude the possibility of absolutely continuous spectrum in a large class of self-adjoint operators with an underlying hierarchical structure and provide applications to certain random hierarchical operators and matrices. We proceed to contrast the localizing effect of the hierarchical structure in the deterministic setting with previous results and conjectures in the random setting. Furthermore, we survey stronger localization statements truly exploiting the disorder for the hierarchical Anderson model and report recent results concerning the spectral statistics of the ultrametric random matrix ensemble.

In this paper, we study the extreme statistics in the complex Ginibre ensemble of $N \times N$ random matrices with complex Gaussian entries, but with no other symmetries. All the $N$ eigenvalues are complex random variables and their joint distribution can be interpreted as a $2d$ Coulomb gas with a logarithmic repulsion between any pair of particles and in presence of a confining harmonic potential $v(r) \propto r^2$. We study the statistics of the eigenvalue with the largest modulus $r_{\max}$ in the complex plane. The typical and large fluctuations of $r_{\max}$ around its mean had been studied before, and they match smoothly to the right of the mean. However, it remained a puzzle to understand why the large and typical fluctuations to the left of the mean did not match. In this paper, we show that there is indeed an intermediate fluctuation regime that interpolates smoothly between the large and the typical fluctuations to the left of the mean. Moreover, we compute explicitly this "intermediate deviation function" (IDF) and show that it is universal, i.e. independent of the confining potential $v(r)$ as long as it is spherically symmetric and increases faster than $\ln r^2$ for large $r$ with an unbounded support. If the confining potential $v(r)$ has a finite support, i.e. becomes infinite beyond a finite radius, we show via explicit computation that the corresponding IDF is different. Interestingly, in the borderline case where the confining potential grows very slowly as $v(r) \sim \ln r^2$ for $r \gg 1$ with an unbounded support, the intermediate regime disappears and there is a smooth matching between the central part and the left large deviation regime.

Quantum states cohere and interfere. Quantum systems composed of many atoms arranged imperfectly rarely display these properties. Here we demonstrate an exception in a disordered quantum magnet that divides itself into nearly isolated subsystems. We probe these coherent clusters of spins by driving the system beyond its linear response regime at a single frequency and measuring the resulting "hole" in the overall linear spectral response. The Fano shape of the hole encodes the incoherent lifetime as well as coherent mixing of the localized excitations. For the disordered Ising magnet, $\mathrm{LiHo_{0.045}Y_{0.955}F_4}$, the quality factor $Q$ for spectral holes can be as high as 100,000. We tune the dynamics of the quantum degrees of freedom by sweeping the Fano mixing parameter $q$ through zero via the amplitude of the ac pump as well as a static external transverse field. The zero-crossing of $q$ is associated with a dissipationless response at the drive frequency, implying that the off-diagonal matrix element for the two-level system also undergoes a zero-crossing. The identification of localized two-level systems in a dense and disordered dipolar-coupled spin system represents a solid state implementation of many-body localization, pushing the search forward for qubits emerging from strongly-interacting, disordered, many-body systems.

We study the Anderson-like localization transition in the spectrum of the Dirac operator of quenched QCD. Above the deconfining transition we determine the temperature dependence of the mobility edge separating localized and delocalized eigenmodes in the spectrum. We show that the temperature where the mobility edge vanishes and localized modes disappear from the spectrum, coincides with the critical temperature of the deconfining transition. We also identify topological charge related close to zero modes in the Dirac spectrum and show that they account for only a small fraction of localized modes, a fraction that is rapidly falling as the temperature increases.

An imperative condition for the functioning of a power-grid network is that its power generators remain synchronized. Disturbances can prompt desynchronization, which is a process that has been involved in large power outages. Here we derive a condition under which the desired synchronous state of a power grid is stable, and use this condition to identify tunable parameters of the generators that are determinants of spontaneous synchronization. Our analysis gives rise to an approach to specify parameter assignments that can enhance synchronization of any given network, which we demonstrate for a selection of both test systems and real power grids. Because our results concern spontaneous synchronization, they are relevant both for reducing dependence on conventional control devices, thus offering an additional layer of protection given that most power outages involve equipment or operational errors, and for contributing to the development of "smart grids" that can recover from failures in real time.

We study the singularity of the order parameter at the transition between a critical phase and an ordered phase of bond percolation on pointed hierarchical graphs. In pointed hierarchical graphs, the renormalization group (RG) equation explicitly depends on the bare parameter, which causes the phase transitions that correspond to the bifurcation of the RG fixed point. We derive the relation between the type of this bifurcation and the type of the singularity of the order parameter. In the case of a saddle node bifurcation, the singularity of the order parameter is power-law or essential one depending on the fundamental local structure of the graph. In the case of pitchfork and transcritical bifurcations, the singularity is essential and power-law ones, respectively. These becomes power-law and discontinuous ones, respectively, in the absence of the first-order perturbation to the largest eigenvalue of the combining matrix, which gives the growth rate of the cluster size. We also show that the first-order perturbation vanishes if the relevant RG parameter is unique and the backbone of the pointed hierarchical graph is simply connected via nesting subunits.

In physics, biology and engineering, network systems abound. How does the connectivity of a network system combine with the behavior of its individual components to determine its collective function? We approach this question for networks with linear time-invariant dynamics by relating internal network feedbacks to the statistical prevalence of connectivity motifs, a set of surprisingly simple and local statistics of connectivity. This results in a reduced order model of the network input-output dynamics in terms of motifs structures. As an example, the new formulation dramatically simplifies the classic Erdos-Renyi graph, reducing the overall network behavior to one proportional feedback wrapped around the dynamics of a single node. For general networks, higher-order motifs systematically provide further layers and types of feedback to regulate the network response. Thus, the local connectivity shapes temporal and spectral processing by the network as a whole, and we show how this enables robust, yet tunable, functionality such as extending the time constant with which networks remember past signals. The theory also extends to networks composed from heterogeneous nodes with distinct dynamics and connectivity, and patterned input to (and readout from) subsets of nodes. These statistical descriptions provide a powerful theoretical framework to understand the functionality of real-world network systems, as we illustrate with examples including the mouse brain connectome.

Changes in brain states, as found in many neurological diseases such as epilepsy, are often described as bifurcations in mesoscopic neural models. Nearly all of these models rely on a mathematically convenient, but biophysically inaccurate, description of the synaptic input to neurons called current-based synapses. We develop a novel analytical framework to analyze the effects of a more biophysically realistic description, known as conductance-based synapses. These are implemented in a mesoscopic neural model and compared to the standard approximation via a single parameter homotopic mapping. A bifurcation analysis using the homotopy parameter demonstrates that if a more realistic synaptic coupling mechanism is used in this class of models, then a bifurcation or transition to an abnormal brain state does not occur in the same parameter space. We show that the more realistic coupling has additional mathematical parameters that require a fundamentally different biophysical mechanism to undergo a state transition. These results demonstrate the importance of incorporating more realistic synapses in mesoscopic neural models and challenge the accuracy of previous models, especially those describing brain state transitions such as epilepsy.

The Anderson metal-insulator transition (MIT) is central to our understanding of the quantum mechanical nature of disordered materials. Despite extensive efforts by theory and experiment, there is still no agreement on the value of the critical exponent $\nu$ describing the universality of the transition --- the so-called "exponent puzzle". In this work, going beyond the standard Anderson model, we employ ab initio methods to study the MIT in a realistic model of a doped semiconductor. We use linear-scaling DFT to simulate prototypes of sulfur-doped silicon (Si:S). From these we build larger tight-binding models close to the critical concentration of the MIT. When the dopant concentration is increased, an impurity band forms and eventually delocalizes. We characterize the MIT via multifractal finite-size scaling, obtaining the phase diagram and estimates of $\nu$. Our results suggest an explanation of the long-standing exponent puzzle, which we link to the hybridization of conduction and impurity bands.

We consider rank-one non-symmetric tensor estimation and derive simple formulas for the mutual information. We start by the order 2 problem, namely matrix factorization. We treat it completely in a simpler fashion than previous proofs using a new type of interpolation method developed in [1]. We then show how to harness the structure in "layers" of tensor estimation in order to obtain a formula for the mutual information for the order 3 problem from the knowledge of the formula for the order 2 problem, still using the same kind of interpolation. Our proof technique straightforwardly generalizes and allows to rigorously obtain the mutual information at any order in a recursive way.

We develop a time-dependent real-space renormalization-group approach which can be applied to Hamiltonians with time-dependent random terms. To illustrate the renormalization-group analysis, we focus on the quantum Ising Hamiltonian with random site- and time-dependent (adiabatic) transverse-field and nearest-neighbour exchange couplings. We demonstrate how the method works in detail, by calculating the off-critical flows and recovering the ground state properties of the Hamiltonian such as magnetization and correlation functions. The adiabatic time allows us to traverse the parameter space, remaining near-to the ground state which is broadened if the rate of change of the Hamiltonian is finite. The quantum critical point, or points, depend on time through the time-dependence of the parameters of the Hamiltonian. We, furthermore, make connections with Kibble-Zurek dynamics and provide a scaling argument for the density of defects as we adiabatically pass through the critical point of the system.

We construct a complexity-based morphospace to study systems-level properties of conscious & intelligent systems. The axes of this space label 3 complexity types: autonomous, cognitive & social. Given recent proposals to synthesize consciousness, a generic complexity-based conceptualization provides a useful framework for identifying defining features of conscious & synthetic systems. Based on current clinical scales of consciousness that measure cognitive awareness and wakefulness, we take a perspective on how contemporary artificially intelligent machines & synthetically engineered life forms measure on these scales. It turns out that awareness & wakefulness can be associated to computational & autonomous complexity respectively. Subsequently, building on insights from cognitive robotics, we examine the function that consciousness serves, & argue the role of consciousness as an evolutionary game-theoretic strategy. This makes the case for a third type of complexity for describing consciousness: social complexity. Having identified these complexity types, allows for a representation of both, biological & synthetic systems in a common morphospace. A consequence of this classification is a taxonomy of possible conscious machines. We identify four types of consciousness, based on embodiment: (i) biological consciousness, (ii) synthetic consciousness, (iii) group consciousness (resulting from group interactions), & (iv) simulated consciousness (embodied by virtual agents within a simulated reality). This taxonomy helps in the investigation of comparative signatures of consciousness across domains, in order to highlight design principles necessary to engineer conscious machines. This is particularly relevant in the light of recent developments at the crossroads of cognitive neuroscience, biomedical engineering, artificial intelligence & biomimetics.

Perceptrons are the building blocks of many theoretical approaches to a wide range of complex systems, ranging from neural networks and deep learning machines, to constraint satisfaction problems, glasses and ecosystems. Despite their applicability and importance, a detailed study of their Langevin dynamics has never been performed yet. Here we derive the mean-field dynamical equations that describe the continuous random perceptron in the thermodynamic limit, in a very general setting with arbitrary noise and friction kernels, not necessarily related by equilibrium relations. We derive the equations in two ways: via a dynamical cavity method, and via a path-integral approach in its supersymmetric formulation. The end point of both approaches is the reduction of the dynamics of the system to an effective stochastic process for a representative dynamical variable. Because the perceptron is formally very close to a system of interacting particles in a high dimensional space, the methods we develop here can be transferred to the study of liquid and glasses in high dimensions. Potentially interesting applications are thus the study of the glass transition in active matter, the study of the dynamics around the jamming transition, and the calculation of rheological properties in driven systems.

We investigate the first and second moments of the inverse participation ratio (IPR) for all eigenvectors of the Laplacian on finite random regular graphs with $n$ vertices and degree $z$. By exactly diagonalizing a large set of $z$-regular graphs, we find that as $n$ becomes large, the mean of the inverse participation ratio on each graph, when averaged over a large ensemble of graphs, approaches the numerical value $3$. This universal number is understood as the large-$n$ limit of the average of the quartic polynomial corresponding to the IPR over an appropriate $(n-2)$-dimensional hypersphere of $\mathbb{R}^n$. For a large, but not exhaustive ensemble of graphs, the mean variance of the inverse participation ratio for all graph Laplacian eigenvectors deviates from its continuous hypersphere average due to large graph-to-graph fluctuations that arise from the existence of highly localized modes.

In this article, we present an alternative method for simulating charge transport in disordered organic materials by using a buffer lattice at the boundary. This method does not require careful tracking of carrier's hopping pattern across boundaries. Suitability of this method is established by reproducing the field dependence of mobility, carrier relaxation and carrier diffusion in disordered organic systems obtained by simulating the charge transport for the full length of the systems along the field direction without and boundary condition. The significance of the buffer lattice is emphasized by simulating field dependence of mobility without using a buffer lattice, which results in negative field dependence of mobiltiy (NFDM) at low field regime due to the extra bias the carrier gains from the neglected hops and boundaries along field direction.

Using a proper cooling procedure, a controllable amount of non-magnetic structural disorder can be introduced at low temperature in (TMTSF)2ClO4. Here we performed simultaneous measurements of transport and magnetic properties of (TMTSF)2ClO4 in its normal and superconducting states, while finely covering three orders of magnitude of the cooling rate around the anion ordering temperature. Our result reveals, with increasing density of disorder, the existence of a crossover between homogeneous defect-controlled d-wave superconductivity and granular superconductivity. At slow cooling rates, with small amount of disorder, the evolution of superconducting properties is well described with the Abrikosov-Gorkov theory, providing further confirmation of non-s-wave pairing in this compound. In contrast, at fast cooling rates, zero resistance and diamagnetic shielding are achieved through a randomly distributed network of superconducting puddles embedded in an normal conducting background and interconnected by proximity effect coupling. The temperature dependence of the AC complex susceptibility reveals features typical for a network of granular superconductors. This makes (TMTSF)2ClO4 a model system for granular superconductivity where the grain size and their concentration are tunable within the same sample.