Artículos con la etiqueta ‘complejidad y computación’

Trends in Computer Network Modeling Towards the Future Internet

Por • 6 mar, 2014 • Category: Ciencia y tecnología

This article provides a taxonomy of current and past network modeling efforts. In all these efforts over the last few years we see a trend towards not only describing the network, but connected devices as well. This is especially current given the many Future Internet projects, which are combining different models, and resources in order to provide complete virtual infrastructures to users. An important mechanism for managing complexity is the creation of an abstract model, a step which has been undertaken in computer networks too. The fact that more and more devices are network capable, coupled with increasing popularity of the Internet, has made computer networks an important focus area for modeling. The large number of connected devices creates an increasing complexity which must be harnessed to keep the networks functioning.

Virality Prediction and Community Structure in Social Networks

Por • 25 nov, 2013 • Category: sociologia

How does network structure affect diffusion? Recent studies suggest that the answer depends on the type of contagion. Complex contagions, unlike infectious diseases (simple contagions), are affected by social reinforcement and homophily. Hence, the spread within highly clustered communities is enhanced, while diffusion across communities is hampered. A common hypothesis is that memes and behaviors are complex contagions. We show that, while most memes indeed behave like complex contagions, a few viral memes spread across many communities, like diseases. We demonstrate that the future popularity of a meme can be predicted by quantifying its early spreading pattern in terms of community concentration. The more communities a meme permeates, the more viral it is. We present a practical method to translate data about community structure into predictive knowledge about what information will spread widely. This connection may lead to significant advances in computational social science, social media analytics, and marketing applications.

Exploiting Similarities among Languages for Machine Translation

Por • 27 sep, 2013 • Category: Ciencia y tecnología

Dictionaries and phrase tables are the basis of modern statistical machine translation systems. This paper develops a method that can automate the process of generating and extending dictionaries and phrase tables. Our method can translate missing word and phrase entries by learning language structures based on large monolingual data and mapping between languages from small bilingual data. It uses distributed representation of words and learns a linear mapping between vector spaces of languages. Despite its simplicity, our method is surprisingly effective: we can achieve almost 90% precision@5 for translation of words between English and Spanish. This method makes little assumption about the languages, so it can be used to extend and refine dictionaries and translation tables for any language pairs.

Closing a Gap in the Complexity of Refinement Modal Logic

Por • 25 sep, 2013 • Category: Crítica

Refinement Modal Logic (RML), which was recently introduced by Bozzelli et al., is an extension of classical modal logic which allows one to reason about a changing model. In this paper we study computational complexity questions related to this logic, settling a number of open problems. Specifically, we study the complexity of satisfiability for the existential fragment of RML, a problem posed by Bozzelli, van Ditmarsch and Pinchinat. Our main result is a tight PSPACE upper bound for this problem, which we achieve by introducing a new tableau system. As a direct consequence, we obtain a tight characterization of the complexity of RML satisfiability for any fixed number of alternations of refinement quantifiers. Additionally, through a simple reduction we establish that the model checking problem for RML is PSPACE-complete, even for formulas with a single quantifier.

Nonlinear quantum search using the Gross–Pitaevskii equation

Por • 27 jun, 2013 • Category: Leyes

We solve the unstructured search problem in constant time by computing with a physically motivated nonlinearity of the Gross–Pitaevskii type. This speedup comes, however, at the novel expense of increasing the time-measurement precision. Jointly optimizing these resource requirements results in an overall scaling of N1/4. This is a significant, but not unreasonable, improvement over the N1/2 scaling of Grover’s algorithm. Since the Gross–Pitaevskii equation approximates the multi-particle (linear) Schrödinger equation, for which Grover’s algorithm is optimal, our result leads to a quantum information-theoretic lower bound on the number of particles needed for this approximation to hold, asymptotically

Incomputability after Alan Turing

Por • 24 abr, 2013 • Category: Leyes

Incomputability as a mathematical notion arose from work of Alan Turing and Alonzo Church in the 1930s. Like Turing himself, it attracted less attention than it deserved beyond the confines of mathematics. Today our experiences in computer science, physics, biology, artificial intelligence, economics and the humanities point to the importance of the notion for understanding the world around us. This article takes a Turing centenary look at how the interface between the computable world and the incomputable formed a central theme in Turing’s work – from the early establishment of the standard model of the stored program computer, to the late work on emergence of form in nature, and the first approaches to understanding and simulating human intelligence.

Regular graphs and the spectra of two-variable logic with counting

Por • 14 abr, 2013 • Category: Crítica

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. This notion has been shown to be closely linked with complexity theory. In fact, asking whether the spectra of first-order logic sentences is closed under complement is equivalent to asking whether NE=coNE. In this paper we show that when restricted to using only two variables, the spectra of first-order logic sentences are closed under complement. In particular, we show that they are semilinear. At the heart of our proof are semilinear characterisations for the existence of regular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.

Human brain, Internet, and cosmology: similar laws at work?

Por • 30 nov, 2012 • Category: Leyes

Having the ability to predict — let alone trying to control — the dynamics of complex networks remains a central challenge throughout network science. Structural and dynamical similarities among different real networks suggest that some universal laws might be in action, although the nature and common origin of such laws remain elusive. “These findings have key implications for both network science and cosmology,” noted Krioukov. “We discovered that the large-scale growth dynamics of complex networks and causal networks are asymptotically (at large times) the same, explaining the structural similarity between these networks.” “The most frequent question that people may ask is whether the discovered asymptotic equivalence between complex networks and the universe could be a coincidence,” said Krioukov. “Of course it could be, but the probability of such a coincidence is extremely low. Coincidences in physics are extremely rare, and almost never happen. There is always an explanation, which may be not immediately obvious.”

Neuropsychological constraints to human data production on a global scale

Por • 3 dic, 2011 • Category: Opinion

Which are the factors underlying human information production on a global level? In order to gain an insight into this question we study a corpus of 252-633 Million publicly available data files on the Internet corresponding to an overall storage volume of 284-675 Terabytes. Analyzing the file size distribution for several distinct data types we find indications that the neuropsychological capacity of the human brain to process and record information may constitute the dominant limiting factor for the overall growth of globally stored information, with real-world economic constraints having only a negligible influence. This supposition draws support from the observation that the files size distributions follow a power law for data without a time component, like images, and a log-normal distribution for multimedia files, for which time is a defining qualia.

The network of global corporate control

Por • 25 oct, 2011 • Category: Economía

The structure of the control network of transnational corporations affects global market competition and financial stability. So far, only small national samples were studied and there was no appropriate methodology to assess control globally. We present the first investigation of the architecture of the international ownership network, along with the computation of the control held by each global player. We find that transnational corporations form a giant bow-tie structure and that a large portion of control flows to a small tightly-knit core of financial institutions. This core can be seen as an economic “super-entity” that raises new important issues both for researchers and policy makers.