OpenRaiser/Intern-Atlas huggingface dataset:
On estimating total time to solve SAT in distributed computing environments: Application to the SAT@home project
Venue: arXiv cs.AI 2013
Year: 2013

This paper proposes a method to estimate the total time required to solve SAT in distributed environments via partitioning approach. It is based on the observation that for some simple forms of problem partitioning one can use the Monte Carlo approach to estimate the time required to solve an original problem. The method proposed is based on an algorithm for searching for partitioning with an optimal solving time estimation. We applied this method to estimate the time required to perform logical cryptanalysis of the widely known stream ciphers A5/1 and Bivium. The paper also describes a volunteer computing project SAT@home aimed at solving hard combinatorial problems reduced to SAT. In this project during several months there were solved 10 problems of logical cryptanalysis of the A5/1 cipher thatcould not be solved using known rainbow tables.
XPath Satisfiability with Parent Axes or Qualifiers Is Tractable under Many of Real-World DTDs
Venue: arXiv cs.DB 2013
Year: 2013

This paper aims at finding a subclass of DTDs that covers many of the real-world DTDs while offering a polynomial-time complexity for deciding the XPath satisfiability problem. In our previous work, we proposed RW-DTDs, which cover most of the real-world DTDs (26 out of 27 real-world DTDs and 1406 out of 1407 DTD rules). However, under RW-DTDs, XPath satisfiability with only child, descendant-or-self, and sibling axes is tractable. In this paper, we propose MRW-DTDs, which are slightly smaller than RW-DTDs but have tractability on XPath satisfiability with parent axes or qualifiers. MRW-DTDs are a proper superclass of duplicate-free DTDs proposed by Montazerian et al., and cover 24 out of the 27 real-world DTDs and 1403 out of the 1407 DTD rules. Under MRW-DTDs, we show that XPath satisfiability problems with (1) child, parent, and sibling axes, and (2) child and sibling axes and qualifiers are both tractable, which are known to be intractable under RW-DTDs.
Quasi-dynamic Traffic Light Control for a Single Intersection
Venue: arXiv cs.SY 2013
Year: 2013

We address the traffic light control problem for a single intersection by viewing it as a stochastic hybrid system and developing a Stochastic Flow Model (SFM) for it. We adopt a quasi-dynamic control policy based on partial state information defined by detecting whether vehicle backlog is above or below a certain threshold, without the need to observe an exact vehicle count. The policy is parameterized by green and red cycle lengths which depend on this partial state information. Using Infinitesimal Perturbation Analysis (IPA), we derive online gradient estimators of an average traffic congestion metric with respect to these controllable green and red cycle lengths when the vehicle backlog is above or below the threshold. The estimators are used to iteratively adjust light cycle lengths so as to improve performance and, in conjunction with a standard gradient-based algorithm, to seek optimal values which adapt to changing traffic conditions. Simulation results are included to illustrate the approach and quantify the benefits of quasidynamic traffic light control over earlier static approaches.
Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider distributed optimization in random networks where N nodes cooperatively minimize the sum \sum_{i=1}^N f_i(x) of their individual convex costs. Existing literature proposes distributed gradient-like methods that are computationally cheap and resilient to link failures, but have slow convergence rates. In this paper, we propose accelerated distributed gradient methods that: 1) are resilient to link failures; 2) computationally cheap; and 3) improve convergence rates over other gradient methods. We model the network by a sequence of independent, identically distributed random matrices {W(k)} drawn from the set of symmetric, stochastic matrices with positive diagonals. The network is connected on average and the cost functions are convex, differentiable, with Lipschitz continuous and bounded gradients. We design two distributed Nesterov-like gradient methods that modify the D-NG and D-NC methods that we proposed for static networks. We prove their convergence rates in terms of the expected optimality gap at the cost function. Let k and K be the number of per-node gradient evaluations and per-node communications, respectively. Then the modified D-NG achieves rates O(log k/k) and O(\log K/K), and the modified D-NC rates O(1/k^2) and O(1/K^{2-ξ}), where ξ>0 is arbitrarily small. For comparison, the standard distributed gradient method cannot do better than Ω(1/k^{2/3}) and Ω(1/K^{2/3}), on the same class of cost functions (even for static networks). Simulation examples illustrate our analytical findings.
WikiPulse - A News-Portal Based on Wikipedia
Venue: arXiv cs.IR 2013
Year: 2013

More and more user-generated content is complementing conventional journalism. While we don't think that CNN or New York Times and its professional journalists will disappear anytime soon, formidable competition is emerging through humble Wikipedia editors. In earlier work (Becker 2012), we found that entertainment and sports news appeared on average about two hours earlier on Wikipedia than on CNN and Reuters online. In this project we build a news-reader that automatically identifies late-breaking news among the most recent Wikipedia articles and then displays it on a dedicated Web site.
Pattern Languages as Media for the Creative Society
Venue: arXiv cs.CY 2013
Year: 2013

This paper proposes new languages for basic skills in the Creative Society, where people create their own goods, tools, concepts, knowledge, and mechanisms with their own hands: the skills of learning, presentation, and collaboration. These languages are written as a pattern language, which is a way of describing the tacit practical knowledge. In this paper, a new type of pattern languages are proposed as "Pattern Languages 3.0" and three examples are introduced: Learning Patterns, Collaboration Patterns, and Presentation Patterns. By analyzing the functions with the social systems theory and the creative systems theory, pattern languages are considered as communication media and discovery media.
Generation of Secret Key for Physical Layer to Evaluate Channel Characteristics in Wireless Communications
Venue: arXiv cs.CR 2013
Year: 2013

This manuscript aims to generate a secret key for a PHY layer to evaluate the channel characteristics in wireless communications. An algorithmic approach is adopted for multimedia encryption to generate a secret key between two entities communicating with each other in a real time simulation environment such as MATLAB. Two classes of PHY key generation schemes are analyzed for designing the algorithm such as received-signal-strength-based and channel- phase-based protocols. We present a performance comparison of them in terms of key disagreement probability, key generation rate, key bit randomness, scalability, and implementation issues.
Evolution of Cloud Storage as Cloud Computing Infrastructure Service
Venue: arXiv cs.DC 2013
Year: 2013

Enterprises are driving towards less cost, more availability, agility, managed risk - all of which is accelerated towards Cloud Computing. Cloud is not a particular product, but a way of delivering IT services that are consumable on demand, elastic to scale up and down as needed, and follow a pay-for-usage model. Out of the three common types of cloud computing service models, Infrastructure as a Service (IaaS) is a service model that provides servers, computing power, network bandwidth and Storage capacity, as a service to their subscribers. Cloud can relate to many things but without the fundamental storage pieces, which is provided as a service namely Cloud Storage, none of the other applications is possible. This paper introduces Cloud Storage, which covers the key technologies in cloud computing and Cloud Storage, management insights about cloud computing, different types of cloud services, driving forces of cloud computing and cloud storage, advantages and challenges of cloud storage and concludes by pinpointing few challenges to be addressed by the cloud storage providers.
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
Venue: arXiv cs.DS 2013
Year: 2013

Consider a database of $n$ people, each represented by a bit-string of length $d$ corresponding to the setting of $d$ binary attributes. A $k$-way marginal query is specified by a subset $S$ of $k$ attributes, and a $|S|$-dimensional binary vector $β$ specifying their values. The result for this query is a count of the number of people in the database whose attribute vector restricted to $S$ agrees with $β$. Privately releasing approximate answers to a set of $k$-way marginal queries is one of the most important and well-motivated problems in differential privacy. Information theoretically, the error complexity of marginal queries is well-understood: the per-query additive error is known to be at least $Ω(\min\{\sqrt{n},d^{\frac{k}{2}}\})$ and at most $\tilde{O}(\min\{\sqrt{n} d^{1/4},d^{\frac{k}{2}}\})$. However, no polynomial time algorithm with error complexity as low as the information theoretic upper bound is known for small $n$. In this work we present a polynomial time algorithm that, for any distribution on marginal queries, achieves average error at most $\tilde{O}(\sqrt{n} d^{\frac{\lceil k/2 \rceil}{4}})$. This error bound is as good as the best known information theoretic upper bounds for $k=2$. This bound is an improvement over previous work on efficiently releasing marginals when $k$ is small and when error $o(n)$ is desirable. Using private boosting we are also able to give nearly matching worst-case error bounds. Our algorithms are based on the geometric techniques of Nikolov, Talwar, and Zhang. The main new ingredients are convex relaxations and careful use of the Frank-Wolfe algorithm for constrained convex minimization. To design our relaxations, we rely on the Grothendieck inequality from functional analysis.
Improving the GPU space of computation under triangular domain problems
Venue: arXiv cs.DC 2013
Year: 2013

There is a stage in the GPU computing pipeline where a grid of thread-blocks is mapped to the problem domain. Normally, this grid is a k-dimensional bounding box that covers a k-dimensional problem no matter its shape. Threads that fall inside the problem domain perform computations, otherwise they are discarded at runtime. For problems with non-square geometry, this is not always the best idea because part of the space of computation is executed without any practical use. Two- dimensional triangular domain problems, alias td-problems, are a particular case of interest. Problems such as the Euclidean distance map, LU decomposition, collision detection and simula- tions over triangular tiled domains are all td-problems and they appear frequently in many areas of science. In this work, we propose an improved GPU mapping function g(lambda), that maps any lambda block to a unique location (i, j) in the triangular domain. The mapping is based on the properties of the lower triangular matrix and it works at a block level, thus not compromising thread organization within a block. The theoretical improvement from using g(lambda) is upper bounded as I < 2 and the number of wasted blocks is reduced from O(n^2) to O(n). We compare our strategy with other proposed methods; the upper-triangular mapping (UTM), the rectangular box (RB) and the recursive partition (REC). Our experimental results on Nvidias Kepler GPU architecture show that g(lambda) is between 12% and 15% faster than the bounding box (BB) strategy. When compared to the other strategies, our mapping runs significantly faster than UTM and it is as fast as RB in practical use, with the advantage that thread organization is not compromised, as in RB. This work also contributes at presenting, for the first time, a fair comparison of all existing strategies running the same experiments under the same hardware.
On the Independent Set and Common Subgraph Problems in Random Graphs
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph $G$, each pair of vertices are joined by an edge with a probability $p$, where $p$ is a constant between $0$ and $1$. We show that, a maximum independent set in a random graph that contains $n$ vertices can be computed in expected computation time $2^{O(\log_{2}^{2}{n})}$. Using techniques based on enumeration, we develop an algorithm that can find a largest common subgraph in two random graphs in $n$ and $m$ vertices ($m \leq n$) in expected computation time $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$. In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in $n$ vertices can be approximated within a ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected polynomial time.
Universal codes of the natural numbers
Venue: arXiv cs.LO 2013
Year: 2013

A code of the natural numbers is a uniquely-decodable binary code of the natural numbers with non-decreasing codeword lengths, which satisfies Kraft's inequality tightly. We define a natural partial order on the set of codes, and show how to construct effectively a code better than a given sequence of codes, in a certain precise sense. As an application, we prove that the existence of a scale of codes (a well-ordered set of codes which contains a code better than any given code) is independent of ZFC.
Optimizing for confidence - Costs and opportunities at the frontier between abstraction and reality
Venue: arXiv cs.CY 2013
Year: 2013

Is there a relationship between computing costs and the confidence people place in the behavior of computing systems? What are the tuning knobs one can use to optimize systems for human confidence instead of correctness in purely abstract models? This report explores these questions by reviewing the mechanisms by which people build confidence in the match between the physical world behavior of machines and their abstract intuition of this behavior according to models or programming language semantics. We highlight in particular that a bottom-up approach relies on arbitrary trust in the accuracy of I/O devices, and that there exists clear cost trade-offs in the use of I/O devices in computing systems. We also show various methods which alleviate the need to trust I/O devices arbitrarily and instead build confidence incrementally "from the outside" by considering systems as black box entities. We highlight cases where these approaches can reach a given confidence level at a lower cost than bottom-up approaches.
Geometric Relationships Between Gaussian and Modulo-Lattice Error Exponents
Venue: arXiv cs.IT 2013
Year: 2013

Lattice coding and decoding have been shown to achieve the capacity of the additive white Gaussian noise (AWGN) channel. This was accomplished using a minimum mean-square error scaling and randomization to transform the AWGN channel into a modulo-lattice additive noise channel of the same capacity. It has been further shown that when operating at rates below capacity but above the critical rate of the channel, there exists a rate-dependent scaling such that the associated modulo-lattice channel attains the error exponent of the AWGN channel. A geometric explanation for this result is developed. In particular, it is shown how the geometry of typical error events for the modulo-lattice channel coincides with that of a spherical code for the AWGN channel.
A simple combinatorial interpretation of certain generalized Bell and Stirling numbers
Venue: arXiv cs.DM 2013
Year: 2013

In a series of papers, P. Blasiak et al. developed a wide-ranging generalization of Bell numbers (and of Stirling numbers of the second kind) that appears to be relevant to the so-called Boson normal ordering problem. They provided a recurrence and, more recently, also offered a (fairly complex) combinatorial interpretation of these numbers. We show that by restricting the numbers somewhat (but still widely generalizing Bell and Stirling numbers), one can supply a much more natural combinatorial interpretation. In fact, we offer two different such interpretations, one in terms of graph colourings and another one in terms of certain labelled Eulerian digraphs.
Linear Network Coding on Multi-Mesh of Trees (MMT) using All to All Broadcast (AAB)
Venue: arXiv cs.DC 2013
Year: 2013

We introduce linear network coding on parallel architecture for multi-source finite acyclic network. In this problem, different messages in diverse time periods are broadcast and every nonsource node in the network decodes and encodes the message based on further communication.We wish to minimize the communication steps and time complexity involved in transfer of data from node-to-node during parallel communication.We have used Multi-Mesh of Trees (MMT) topology for implementing network coding. To envisage our result, we use all-to-all broadcast as communication algorithm.
The Price of Anarchy in Bilateral Network Formation in an Adversary Model
Venue: arXiv cs.GT 2013
Year: 2013

We study network formation with the bilateral link formation rule (Jackson and Wolinsky 1996) with $n$ players and link cost $α>0$. After the network is built, an adversary randomly destroys one link according to a certain probability distribution. Cost for player $v$ incorporates the expected number of players to which $v$ will become disconnected. This model was previously studied for unilateral link formation (K. 2011). We prove existence of pairwise Nash equilibria under moderate assumptions on the adversary and $n\geq 9$. As the main result, we prove bounds on the price of anarchy for two special adversaries: one destroys a link chosen uniformly at random, while the other destroys a link that causes a maximum number of player pairs to be separated. We prove bounds tight up to constants, namely $O(1)$ for one adversary (if $α>1/2$), and $Θ(n)$ for the other (if $α>2$ considered constant and $n \geq 9$). The latter is the worst that can happen for any adversary in this model (if $α=Ω(1)$).
Model and Performance of a No-Reference Quality Assessment Metric for Video Streaming
Venue: arXiv cs.MM 2013
Year: 2013

Video streaming via TCP networks has become a popular and highly demanded service, but its quality assessment in both objective and subjective terms has not been properly addressed. In this paper, based on statistical analysis a full analytic model of a no-reference objective metric, namely Pause Intensity, for video quality assessment is presented. The model characterizes the video playout buffer behavior in connection with the network performance (throughput) and the video playout rate. This allows for instant quality measurement and control without requiring a reference video. Pause intensity specifically addresses the need for assessing the quality issue in terms of the continuity in the playout of TCP streaming videos, which cannot be properly measured by other objective metrics such as PSNR, SSIM and buffer underrun or pause frequency. The performance of the analytical model is rigidly verified by simulation results and subjective tests using a range of video clips. It is demonstrated that pause intensity is closely correlated with viewer opinion scores regardless of the vastly different composition of individual elements, such as pause duration and pause frequency which jointly constitute this new quality metric. It is also shown that the correlation performance of pause intensity is consistent and content independent.
An Optimization Framework to Improve 4D-Var Data Assimilation System Performance
Venue: arXiv cs.CE 2013
Year: 2013

This paper develops a computational framework for optimizing the parameters of data assimilation systems in order to improve their performance. The approach formulates a continuous meta-optimization problem for parameters; the meta-optimization is constrained by the original data assimilation problem. The numerical solution process employs adjoint models and iterative solvers. The proposed framework is applied to optimize observation values, data weighting coefficients, and the location of sensors for a test problem. The ability to optimize a distributed measurement network is crucial for cutting down operating costs and detecting malfunctions.
Comparing cost and performance of replication and erasure coding
Venue: arXiv cs.IT 2013
Year: 2013

Data storage systems are more reliable than their individual components. In order to build highly reliable systems out of less reliable parts, systems introduce redundancy. In replicated systems, objects are simply copied several times with each copy residing on a different physical device. While such an approach is simple and direct, more elaborate approaches such as erasure coding can achieve equivalent levels of data protection while using less redundancy. This report examines the trade-offs in cost and performance between replicated and erasure encoded storage systems.
Time series modeling with pruned multi-layer perceptron and 2-stage damped least-squares method
Venue: arXiv cs.NE 2013
Year: 2013

A Multi-Layer Perceptron (MLP) defines a family of artificial neural networks often used in TS modeling and forecasting. Because of its "black box" aspect, many researchers refuse to use it. Moreover, the optimization (often based on the exhaustive approach where "all" configurations are tested) and learning phases of this artificial intelligence tool (often based on the Levenberg-Marquardt algorithm; LMA) are weaknesses of this approach (exhaustively and local minima). These two tasks must be repeated depending on the knowledge of each new problem studied, making the process, long, laborious and not systematically robust. In this paper a pruning process is proposed. This method allows, during the training phase, to carry out an inputs selecting method activating (or not) inter-nodes connections in order to verify if forecasting is improved. We propose to use iteratively the popular damped least-squares method to activate inputs and neurons. A first pass is applied to 10% of the learning sample to determine weights significantly different from 0 and delete other. Then a classical batch process based on LMA is used with the new MLP. The validation is done using 25 measured meteorological TS and cross-comparing the prediction results of the classical LMA and the 2-stage LMA.
Space as an invention of biological organisms
Venue: arXiv cs.AI 2013
Year: 2013

The question of the nature of space around us has occupied thinkers since the dawn of humanity, with scientists and philosophers today implicitly assuming that space is something that exists objectively. Here we show that this does not have to be the case: the notion of space could emerge when biological organisms seek an economic representation of their sensorimotor flow. The emergence of spatial notions does not necessitate the existence of real physical space, but only requires the presence of sensorimotor invariants called `compensable' sensory changes. We show mathematically and then in simulations that naïve agents making no assumptions about the existence of space are able to learn these invariants and to build the abstract notion that physicists call rigid displacement, which is independent of what is being displaced. Rigid displacements may underly perception of space as an unchanging medium within which objects are described by their relative positions. Our findings suggest that the question of the nature of space, currently exclusive to philosophy and physics, should also be addressed from the standpoint of neuroscience and artificial intelligence.