OpenRaiser/Intern-Atlas huggingface dataset:
On the Performance of Exhaustive Search with Cooperating agents
Venue: arXiv cs.DC 2012
Year: 2012

Despite the occurrence of elegant algorithms for solving complex problem, exhaustive search has retained its significance since many real-life problems exhibit no regular structure and exhaustive search is the only possible solution. The advent of high-performance computing either via multicore processors or distributed processors emphasizes the possibility for exhaustive search by multiple search agents. Here we analyse the performance of exhaustive search when it is conducted by multiple search agents. Several strategies for cooperation between the search agents are evaluated. We discover that the performance of the search improves with the increase in the level of cooperation. Same search performance can be achieved with homogeneous and heterogeneous search agents provided that the length of subregions allocated to individual search regions follow the differences in the speeds of heterogeneous search agents.
Compressive sampling with chaotic dynamical systems
Venue: arXiv cs.IT 2012
Year: 2012

We investigate the possibility of using different chaotic sequences to construct measurement matrices in compressive sampling. In particular, we consider sequences generated by Chua, Lorenz and Rossler dynamical systems and investigate the accuracy of reconstruction when using each of them to construct measurement matrices. Chua and Lorenz sequences appear to be suitable to construct measurement matrices. We compare the recovery rate of the original sequence with that obtained by using Gaussian, Bernoulli and uniformly distributed random measurement matrices. We also investigate the impact of correlation on the recovery rate. It appears that correlation does not influence the probability of exact reconstruction significantly.
Methods and Techniques of Quality Management for ICT Audit Processes
Venue: arXiv cs.OH 2012
Year: 2012

In modern organizations, Information and Communication Technologies are used to support the organizations' activities. To manage the quality of the organization processes, audit processes are implemented. Also, the audit processes can aim the quality of ICT systems themselves because their involvement in organization processes. The paper investigates the ways in which a quality management can be applied for audit processes in order to obtain a high level of quality for the audit recommendations.
Polyhedral Clinching Auctions and the Adwords Polytope
Venue: arXiv cs.GT 2012
Year: 2012

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for {\em polymatroidal} environments satisfying the above properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multi-unit auctions with decreasing marginal utilities in the presence of budget constraints.
ProofPeer - A Cloud-based Interactive Theorem Proving System
Venue: arXiv cs.MS 2012
Year: 2012

ProofPeer strives to be a system for cloud-based interactive theorem proving. After illustrating why such a system is needed, the paper presents some of the design challenges that ProofPeer needs to meet to succeed. Contexts are presented as a solution to the problem of sharing proof state among the users of ProofPeer. Chronicles are introduced as a way to organize and version contexts.
Symbian `vulnerability' and Mobile Threats
Venue: arXiv cs.CR 2012
Year: 2012

Modern technologies are becoming ever more integrated with each other. Mobile phones are becoming increasing intelligent, and handsets are growing ever more like computers in functionality. We are entering a new era - the age of smart houses, global advanced networks which encompass a wide range of devices, all of them exchanging data with each other. Such trends clearly open new horizons to malicious users, and the potential threats are self evident. In this paper, we study and discuss one of the most famous mobile operating systems 'Symbian'; its vulnerabilities and recommended protection technologies.
Expansion for Universal Quantifiers
Venue: arXiv cs.PL 2012
Year: 2012

Expansion is an operation on typings (i.e., pairs of typing environments and result types) defined originally in type systems for the lambda-calculus with intersection types in order to obtain principal (i.e., most informative, strongest) typings. In a type inference scenario, expansion allows postponing choices for whether and how to use non-syntax-driven typing rules (e.g., intersection introduction) until enough information has been gathered to make the right decision. Furthermore, these choices can be equivalent to inserting uses of such typing rules at deeply nested positions in a typing derivation, without needing to actually inspect or modify (or even have) the typing derivation. Expansion has in recent years become simpler due to the use of expansion variables (e.g., in System E). This paper extends expansion and expansion variables to systems with forall-quantifiers. We present System Fs, an extension of System F with expansion, and prove its main properties. This system turns type inference into a constraint solving problem; this could be helpful to design a modular type inference algorithm for System F types in the future.
Sublogarithmic uniform Boolean proof nets
Venue: arXiv cs.CC 2012
Year: 2012

Using a proofs-as-programs correspondence, Terui was able to compare two models of parallel computation: Boolean circuits and proof nets for multiplicative linear logic. Mogbil et. al. gave a logspace translation allowing us to compare their computational power as uniform complexity classes. This paper presents a novel translation in AC0 and focuses on a simpler restricted notion of uniform Boolean proof nets. We can then encode constant-depth circuits and compare complexity classes below logspace, which were out of reach with the previous translations.
Data Rate Limitations for Stabilization of Uncertain Systems over Lossy Channels
Venue: arXiv cs.SY 2012
Year: 2012

This paper considers data rate limitations for mean square stabilization of uncertain discrete-time linear systems via finite data rate and lossy channels. For a plant having parametric uncertainties, a necessary condition and a sufficient condition are derived, represented by the data rate, the packet loss probability, uncertainty bounds on plant parameters, and the unstable eigenvalues of the plant. The results extend those existing in the area of networked control, and in particular, the condition is exact for the scalar plant case.
DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
Venue: arXiv cs.NI 2012
Year: 2012

The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a few pairs and to predict the other ones without actually measuring them. This paper formulates the distance prediction problem as matrix completion where unknown entries of an incomplete matrix of pairwise distances are to be predicted. The problem is solvable because strong correlations among network distances exist and cause the constructed distance matrix to be low rank. The new formulation circumvents the well-known drawbacks of existing approaches based on Euclidean embedding. A new algorithm, so-called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD), is proposed to solve the network distance prediction problem. By letting network nodes exchange messages with each other, the algorithm is fully decentralized and only requires each node to collect and to process local measurements, with neither explicit matrix constructions nor special nodes such as landmarks and central servers. In addition, we compared comprehensively matrix factorization and Euclidean embedding to demonstrate the suitability of the former on network distance prediction. We further studied the incorporation of a robust loss function and of non-negativity constraints. Extensive experiments on various publicly-available datasets of network delays show not only the scalability and the accuracy of our approach but also its usability in real Internet applications.
New results on variants of covering codes in Sierpinski graphs
Venue: arXiv cs.DM 2012
Year: 2012

In this paper we study identifying codes, locating-dominating codes, and total-dominating codes in Sierpinski graphs. We compute the minimum size of such codes in Sierpinski graphs.
Structural Analysis: Shape Information via Points-To Computation
Venue: arXiv cs.PL 2012
Year: 2012

This paper introduces a new hybrid memory analysis, Structural Analysis, which combines an expressive shape analysis style abstract domain with efficient and simple points-to style transfer functions. Using data from empirical studies on the runtime heap structures and the programmatic idioms used in modern object-oriented languages we construct a heap analysis with the following characteristics: (1) it can express a rich set of structural, shape, and sharing properties which are not provided by a classic points-to analysis and that are useful for optimization and error detection applications (2) it uses efficient, weakly-updating, set-based transfer functions which enable the analysis to be more robust and scalable than a shape analysis and (3) it can be used as the basis for a scalable interprocedural analysis that produces precise results in practice. The analysis has been implemented for .Net bytecode and using this implementation we evaluate both the runtime cost and the precision of the results on a number of well known benchmarks and real world programs. Our experimental evaluations show that the domain defined in this paper is capable of precisely expressing the majority of the connectivity, shape, and sharing properties that occur in practice and, despite the use of weak updates, the static analysis is able to precisely approximate the ideal results. The analysis is capable of analyzing large real-world programs (over 30K bytecodes) in less than 65 seconds and using less than 130MB of memory. In summary this work presents a new type of memory analysis that advances the state of the art with respect to expressive power, precision, and scalability and represents a new area of study on the relationships between and combination of concepts from shape and points-to analyses.
A Novel Chaotic Encryption Scheme based on Pseudorandom Bit Padding
Venue: arXiv cs.CR 2012
Year: 2012

Cryptography is always very important in data origin authentications, entity authentication, data integrity and confidentiality. In recent years, a variety of chaotic cryptographic schemes have been proposed. These schemes have typical structure which performed the permutation and the diffusion stages, alternatively. The random number generators are intransitive in cryptographic schemes and be used in the diffusion functions of the image encryption for diffused pixels of plain image. In this paper, we propose a chaotic encryption scheme based on pseudorandom bit padding that the bits be generated by a novel logistic pseudorandom image algorithm. To evaluate the security of the cipher image of this scheme, the key space analysis, the correlation of two adjacent pixels and differential attack were performed. This scheme tries to improve the problem of failure of encryption such as small key space and level of security.
An Example for the Use of Bitwise Operations in Programming
Venue: arXiv cs.OH 2012
Year: 2012

This piece of work presents a meaningful example for the advantages of using bitwise operations for creating effective algorithms in programming. A task connected with mathematical modeling in weaving industry is examined and computed.
The Weakness of Weak Ties in the Classroom
Venue: arXiv cs.SI 2012
Year: 2012

Granovetter's "strength of weak ties" hypothesizes that isolated social ties offer limited access to external prospects, while heterogeneous social ties diversify one's opportunities. We analyze the most complete record of college student interactions to date (approximately 80,000 interactions by 290 students -- 16 times more interactions with almost 3 times more students than previous studies on educational networks) and compare the social interaction data with the academic scores of the students. Our first finding is that social diversity is negatively correlated with performance. This is explained by our second finding: highly performing students interact in groups of similarly performing peers. This effect is stronger the higher the student performance is. Indeed, low performance students tend to initiate many transient interactions independently of the performance of their target. In other words, low performing students act disassortatively with respect to their social network, whereas high scoring students act assortatively. Our data also reveals that highly performing students establish persistent interactions before mid and low performing ones and that they use more structured and longer cascades of information from which low performing students are excluded.
Toward a Motor Theory of Sign Language Perception
Venue: arXiv cs.CL 2012
Year: 2012

Researches on signed languages still strongly dissociate lin- guistic issues related on phonological and phonetic aspects, and gesture studies for recognition and synthesis purposes. This paper focuses on the imbrication of motion and meaning for the analysis, synthesis and evaluation of sign language gestures. We discuss the relevance and interest of a motor theory of perception in sign language communication. According to this theory, we consider that linguistic knowledge is mapped on sensory-motor processes, and propose a methodology based on the principle of a synthesis-by-analysis approach, guided by an evaluation process that aims to validate some hypothesis and concepts of this theory. Examples from existing studies illustrate the di erent concepts and provide avenues for future work.
Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
Venue: arXiv cs.DM 2012
Year: 2012

We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.
Secure Symmetrical Multilevel Diversity Coding
Venue: arXiv cs.IT 2012
Year: 2012

Symmetrical Multilevel Diversity Coding (SMDC) is a network compression problem introduced by Roche (1992) and Yeung (1995). In this setting, a simple separate coding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate (Roche, Yeung, and Hau, 1997) and the entire admissible rate region (Yeung and Zhang, 1999) of the problem. This paper considers a natural generalization of SMDC to the secure communication setting with an additional eavesdropper. It is required that all sources need to be kept perfectly secret from the eavesdropper as long as the number of encoder outputs available at the eavesdropper is no more than a given threshold. First, the problem of encoding individual sources is studied. A precise characterization of the entire admissible rate region is established via a connection to the problem of secure coding over a three-layer wiretap network and utilizing some basic polyhedral structure of the admissible rate region. Building on this result, it is then shown that superposition coding remains optimal in terms of achieving the minimum sum rate for the general secure SMDC problem.
Relaying for Multiuser Networks in the Absence of Codebook Information
Venue: arXiv cs.IT 2012
Year: 2012

This work considers relay assisted transmission for multiuser networks when the relay has no access to the codebooks used by the transmitters. The relay is called oblivious for this reason. Of particular interest is the generalized compress-and-forward (GCF) strategy, where the destinations jointly decode the compression indices and the transmitted messages, and their optimality in this setting. The relay-to-destination links are assumed to be out-of-band with finite capacity. Two models are investigated: the multiple access relay channel (MARC) and the interference relay channel (IFRC). For the MARC with an oblivious relay, a new outerbound is derived and it is shown to be tight by means of achievability of the capacity region using GCF scheme. For the IFRC with an oblivious relay, a new strong interference condition is established, under which the capacity region is found by deriving a new outerbound and showing that it is achievable using GCF scheme. The result is further extended to establish the capacity region of M-user MARC with an oblivious relay, and multicast networks containing M sources and K destinations with an oblivious relay.
Telescopers for Rational and Algebraic Functions via Residues
Venue: arXiv cs.SC 2012
Year: 2012

We show that the problem of constructing telescopers for functions of m variables is equivalent to the problem of constructing telescopers for algebraic functions of m -1 variables and present a new algorithm to construct telescopers for algebraic functions of two variables. These considerations are based on analyzing the residues of the input. According to experiments, the resulting algorithm for rational functions of three variables is faster than known algorithms, at least in some examples of combinatorial interest. The algorithm for algebraic functions implies a new bound on the order of the telescopers.
Adaptive Noise Reduction Scheme for Salt and Pepper
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, a new adaptive noise reduction scheme for images corrupted by impulse noise is presented. The proposed scheme efficiently identifies and reduces salt and pepper noise. MAG (Mean Absolute Gradient) is used to identify pixels which are most likely corrupted by salt and pepper noise that are candidates for further median based noise reduction processing. Directional filtering is then applied after noise reduction to achieve a good tradeoff between detail preservation and noise removal. The proposed scheme can remove salt and pepper noise with noise density as high as 90% and produce better result in terms of qualitative and quantitative measures of images.
Mobile node localization in cellular networks
Venue: arXiv cs.NI 2012
Year: 2012

Location information is the major component in location based applications. This information is used in different safety and service oriented applications to provide users with services according to their Geolocation. There are many approaches to locate mobile nodes in indoor and outdoor environments. In this paper, we are interested in outdoor localization particularly in cellular networks of mobile nodes and presented a localization method based on cell and user location information. Our localization method is based on hello message delay (sending and receiving time) and coordinate information of Base Transceiver Station (BTSs). To validate our method across cellular network, we implemented and simulated our method in two scenarios i.e. maintaining database of base stations in centralize and distributed system. Simulation results show the effectiveness of our approach and its implementation applicability in telecommunication systems.
Multi-sensor Information Processing using Prediction Market-based Belief Aggregation
Venue: arXiv cs.MA 2012
Year: 2012

We consider the problem of information fusion from multiple sensors of different types with the objective of improving the confidence of inference tasks, such as object classification, performed from the data collected by the sensors. We propose a novel technique based on distributed belief aggregation using a multi-agent prediction market to solve this information fusion problem. To monitor the improvement in the confidence of the object classification as well as to dis-incentivize agents from misreporting information, we have introduced a market maker that rewards the agents instantaneously as well as at the end of the inference task, based on the quality of the submitted reports. We have implemented the market maker's reward calculation in the form of a scoring rule and have shown analytically that it incentivizes truthful revelation or accurate reporting by each agent. We have experimentally verified our technique for multi-sensor information fusion for an automated landmine detection scenario. Our experimental results show that, for identical data distributions and settings, using our information aggregation technique increases the accuracy of object classification favorably as compared to two other commonly used techniques for information fusion for landmine detection.
Distance-Based Bias in Model-Directed Optimization of Additively Decomposable Problems
Venue: arXiv cs.NE 2012
Year: 2012

For many optimization problems it is possible to define a distance metric between problem variables that correlates with the likelihood and strength of interactions between the variables. For example, one may define a metric so that the dependencies between variables that are closer to each other with respect to the metric are expected to be stronger than the dependencies between variables that are further apart. The purpose of this paper is to describe a method that combines such a problem-specific distance metric with information mined from probabilistic models obtained in previous runs of estimation of distribution algorithms with the goal of solving future problem instances of similar type with increased speed, accuracy and reliability. While the focus of the paper is on additively decomposable problems and the hierarchical Bayesian optimization algorithm, it should be straightforward to generalize the approach to other model-directed optimization techniques and other problem classes. Compared to other techniques for learning from experience put forward in the past, the proposed technique is both more practical and more broadly applicable.