OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Hybrid Algorithm for Task Graph Scheduling
Venue: arXiv cs.CC 2011
Year: 2011

One of the important problems in multiprocessor systems is Task Graph Scheduling. Task Graph Scheduling is an NP-Hard problem. Both learning automata and genetic algorithms are search tools which are used for solving many NP-Hard problems. In this paper a new hybrid method based on Genetic Algorithm and Learning Automata is proposed. The proposed algorithm begins with an initial population of randomly generated chromosomes and after some stages, each chromosome maps to an automaton. Experimental results show that superiority of the proposed algorithm over the current approaches.
Sleep Mode Analysis via Workload Decomposition
Venue: arXiv cs.NI 2011
Year: 2011

The goal of this paper is to establish a general approach for analyzing queueing models with repeated inhomogeneous vacations. The server goes on for a vacation if the inactivity prolongs more than the vacation trigger duration. Once the system enters in vacation mode, it may continue for several consecutive vacations. At the end of a vacation, the server goes on another vacation, possibly with a different probability distribution; if during the previous vacation there have been no arrivals. However the system enters in vacation mode only if the inactivity is persisted beyond defined trigger duration. In order to get an insight on the influence of parameters on the performance, we choose to study a simple M/G/1 queue (Poisson arrivals and general independent service times) which has the advantage of being tractable analytically. The theoretical model is applied to the problem of power saving for mobile devices in which the sleep durations of a device correspond to the vacations of the server. Various system performance metrics such as the frame response time and the economy of energy are derived. A constrained optimization problem is formulated to maximize the economy of energy achieved in power save mode, with constraints as QoS conditions to be met. An illustration of the proposed methods is shown with a WiMAX system scenario to obtain design parameters for better performance. Our analysis allows us not only to optimize the system parameters for a given traffic intensity but also to propose parameters that provide the best performance under worst case conditions.
Channels That Die
Venue: arXiv cs.IT 2011
Year: 2011

Given the possibility of communication systems failing catastrophically, we investigate limits to communicating over channels that fail at random times. These channels are finite-state semi-Markov channels. We show that communication with arbitrarily small probability of error is not possible. Making use of results in finite blocklength channel coding, we determine sequences of blocklengths that optimize transmission volume communicated at fixed maximum message error probabilities. We provide a partial ordering of communication channels. A dynamic programming formulation is used to show the structural result that channel state feedback does not improve performance.
Soundness and completeness of the cirquent calculus system CL6 for computability logic
Venue: arXiv cs.LO 2011
Year: 2011

Computability logic is a formal theory of computability. The earlier article "Introduction to cirquent calculus and abstract resource semantics" by Japaridze proved soundness and completeness for the basic fragment CL5 of computability logic. The present article extends that result to the more expressive cirquent calculus system CL6, which is a conservative extension of both CL5 and classical propositional logic.
PRESY: A Context Based Query Reformulation Tool for Information Retrieval on the Web
Venue: arXiv cs.IR 2011
Year: 2011

Problem Statement: The huge number of information on the web as well as the growth of new inexperienced users creates new challenges for information retrieval. It has become increasingly difficult for these users to find relevant documents that satisfy their individual needs. Certainly the current search engines (such as Google, Bing and Yahoo) offer an efficient way to browse the web content. However, the result quality is highly based on uses queries which need to be more precise to find relevant documents. This task still complicated for the majority of inept users who cannot express their needs with significant words in the query. For that reason, we believe that a reformulation of the initial user's query can be a good alternative to improve the information selectivity. This study proposes a novel approach and presents a prototype system called PRESY (Profile-based REformulation SYstem) for information retrieval on the web. Approach: It uses an incremental approach to categorize users by constructing a contextual base. The latter is composed of two types of context (static and dynamic) obtained using the users' profiles. The architecture proposed was implemented using .Net environment to perform queries reformulating tests. Results: The experiments gives at the end of this article show that the precision of the returned content is effectively improved. The tests were performed with the most popular searching engine (i.e. Google, Bind and Yahoo) selected in particular for their high selectivity. Among the given results, we found that query reformulation improve the first three results by 10.7% and 11.7% of the next seven returned elements. So as we can see the reformulation of users' initial queries improves the pertinence of returned content.
Using Grossone to count the number of elements of infinite sets and the connection with bijections
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we look at how to count the number of elements of a set within the frame of Sergeyev's numeral system. We also look at the connection between the number of elements of a set and the notion of bijection in this new setting. We also show the difference between this new numeral system and the results of the traditional naive set theory.
False-name-proof Mechanisms for Hiring a Team
Venue: arXiv cs.GT 2011
Year: 2011

We study the problem of hiring a team of selfish agents to perform a task. Each agent is assumed to own one or more elements of a set system, and the auctioneer is trying to purchase a feasible solution by conducting an auction. Our goal is to design auctions that are truthful and false-name-proof, meaning that it is in the agents' best interest to reveal ownership of all elements (which may not be known to the auctioneer a priori) as well as their true incurred costs. We first propose and analyze a false-name-proof mechanism for the special case where each agent owns only one element in reality, but may pretend that this element is in fact a set of multiple elements. We prove that its frugality ratio is bounded by $2^n$, which, up to constants, matches a lower bound of $Ω(2^n)$ for all false-name-proof mechanisms in this scenario. We then propose a second mechanism for the general case in which agents may own multiple elements. It requires the auctioneer to choose a reserve cost a priori, and thus does not always purchase a solution. In return, it is false-name-proof even when agents own multiple elements. We experimentally evaluate the payment (as well as social surplus) of the second mechanism through simulation.
On the Sum Capacity of K-user Cascade Gaussian Z-Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

A $K$-user cascade Gaussian Z-interference channel is a subclass of the general $K$-user Gaussian interference channel, where each user, except the first one, experiences interference only from the previous user. Under simple Han-Kobayashi schemes assuming Gaussian inputs and no time sharing, it is shown that the maximum sum rate is achieved by each user transmitting either common or private signals. For K=3, channel conditions under which the achieved sum rate is either equal to or within 0.5 bits to the sum capacity are identified.
Eliciting Forecasts from Self-interested Experts: Scoring Rules for Decision Makers
Venue: arXiv cs.GT 2011
Year: 2011

Scoring rules for eliciting expert predictions of random variables are usually developed assuming that experts derive utility only from the quality of their predictions (e.g., score awarded by the rule, or payoff in a prediction market). We study a more realistic setting in which (a) the principal is a decision maker and will take a decision based on the expert's prediction; and (b) the expert has an inherent interest in the decision. For example, in a corporate decision market, the expert may derive different levels of utility from the actions taken by her manager. As a consequence the expert will usually have an incentive to misreport her forecast to influence the choice of the decision maker if typical scoring rules are used. We develop a general model for this setting and introduce the concept of a compensation rule. When combined with the expert's inherent utility for decisions, a compensation rule induces a net scoring rule that behaves like a normal scoring rule. Assuming full knowledge of expert utility, we provide a complete characterization of all (strictly) proper compensation rules. We then analyze the situation where the expert's utility function is not fully known to the decision maker. We show bounds on: (a) expert incentive to misreport; (b) the degree to which an expert will misreport; and (c) decision maker loss in utility due to such uncertainty. These bounds depend in natural ways on the degree of uncertainty, the local degree of convexity of net scoring function, and natural properties of the decision maker's utility function. They also suggest optimization procedures for the design of compensation rules. Finally, we briefly discuss the use of compensation rules as market scoring rules for self-interested experts in a prediction market.
Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections
Venue: arXiv cs.DS 2011
Year: 2011

Compression techniques that support fast random access are a core component of any information system. Current state-of-the-art methods group documents into fixed-sized blocks and compress each block with a general-purpose adaptive algorithm such as GZIP. Random access to a specific document then requires decompression of a block. The choice of block size is critical: it trades between compression effectiveness and document retrieval times. In this paper we present a scalable compression method for large document collections that allows fast random access. We build a representative sample of the collection and use it as a dictionary in a LZ77-like encoding of the rest of the collection, relative to the dictionary. We demonstrate on large collections, that using a dictionary as small as 0.1% of the collection size, our algorithm is dramatically faster than previous methods, and in general gives much better compression.
A Simple Multi-Processor Computer Based on Subleq
Venue: arXiv cs.DC 2011
Year: 2011

Subleq (Subtract and Branch on result Less than or Equal to zero) is both an instruction set and a programming language for One Instruction Set Computer (OISC). We describe a hardware implementation of an array of 28 one-instruction Subleq processors on a low-cost FPGA board. Our test results demonstrate that computational power of our Subleq OISC multi-processor is comparable to that of CPU of a modern personal computer. Additionally, we provide implementation details of our complier from a C-style language to Subleq.
Knowledge Dispersion Index for Measuring Intellectual Capital
Venue: arXiv cs.SI 2011
Year: 2011

In this paper we propose a novel index to quantify and measure the flow of information on macro and micro scales. We discuss the implications of this index for knowledge management fields and also as intellectual capital that can thus be utilized by entrepreneurs. We explore different function and human oriented metrics that can be used at micro-scales to process the flow of information. We present a table of about 23 metrics, such as change in IT inventory and percentage of employees with advanced degrees, that can be used at micro scales to wholly quantify knowledge dispersion as intellectual capital. At macro scales we split the economy in an industrial and consumer sector where the flow of information in each determines how fast an economy is going to grow and how overall an economy will perform given the aggregate demand. Lastly, we propose a model for knowledge dispersion based on graph theory and show how corrections in the flow become self-evident. Through the principals of flow conservation and capacity constrains we also speculate how this flow might seeks some equilibrium and exhibit self-correction codes. This proposed model allows us to account for perturbations in form of local noise, evolution of networks, provide robustness against local damage from lower nodes, and help determine the underlying classification into network super-families.
A Framework for Enabling Distributed Applications on the Internet
Venue: arXiv cs.DC 2011
Year: 2011

The last five years have seen the rapid rise in popularity of what we term internet distributed applications (IDAs). These are internet applications with which many users interact simultaneously. IDAs range from P2P file-sharing applications, to collaborative distributed computing projects, to massively multiplayer online games (MMOGs). Currently, there is no framework that combines IDAs collectively within a single context. We provide a basis for such a framework here. In considering IDAs collectively, we found that there was no generic description that had been applied to them as a group. We have therefore put forward such a description here. In our description, IDAs are functionality separated into three logic layers, which are designed and built individually. Each layer is represented by functionality on the software client running on each participating computer, which together comprise the overall IDA. The core contribution of this work is a framework, called the Internet Distributed Application Framework (IDAF), which outlines how IDAs can be designed, built and run. The IDAF outlines a set of constraints that each implementing software system must abide by. To verify the IDAF, we have built a system prototype implementation called the Internet Distributed Application System (IDAS). The IDAS includes an implementation of the IDAF layer model, which specifies IDAs are built. The IDAS also includes a generic software client that is capable of simultaneously running and managing arbitrary IDAs. We provide sample IDAs and demonstrations to verify both that the IDAF is implementable and that the IDAS is a workable usable system.
Geometric Simultaneous RAC Drawings of Graphs
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we introduce and study "geometric simultaneous RAC drawing problems", i.e., a combination of problems on geometric RAC drawings and geometric simultaneous graph drawings. To the best of our knowledge, this is the first time where such a combination is attempted.
Efficient algorithm for the vertex connectivity of trapezoid graphs
Venue: arXiv cs.DS 2011
Year: 2011

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. These graphs and their generalizations were applied in various fields, including modeling channel routing problems in VLSI design and identifying the optimal chain of non-overlapping fragments in bioinformatics. Using modified binary indexed tree data structure, we design an algorithm for calculating the vertex connectivity of trapezoid graph $G$ with time complexity $O (n \log n)$, where $n$ is the number of trapezoids. Furthermore, we establish sufficient and necessary condition for a trapezoid graph $G$ to be bipartite and characterize trees that can be represented as trapezoid graphs.
The Public Option: a Non-regulatory Alternative to Network Neutrality
Venue: arXiv cs.NI 2011
Year: 2011

Network neutrality and the role of regulation on the Internet have been heavily debated in recent times. Amongst the various definitions of network neutrality, we focus on the one which prohibits paid prioritization of content and we present an analytical treatment of the topic. We develop a model of the Internet ecosystem in terms of three primary players: consumers, ISPs and content providers. Our analysis looks at this issue from the point of view of the consumer, and we describe the desired state of the system as one which maximizes consumer surplus. By analyzing different scenarios of monopoly and competition, we obtain different conclusions on the desirability of regulation. We also introduce the notion of a Public Option ISP, an ISP that carries traffic in a network neutral manner. Our major findings are (i) in a monopolistic scenario, network neutral regulations benefit consumers; however, the introduction of a Public Option ISP is even better for consumers, as it aligns the interests of the monopolistic ISP with the consumer surplus and (ii) in an oligopolistic situation, the presence of a Public Option ISP is again preferable to network neutral regulations, although the presence of competing price-discriminating ISPs provides the most desirable situation for the consumers.
Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
Venue: arXiv cs.IT 2011
Year: 2011

The low-rank matrix recovery (LMR) is a rank minimization problem subject to linear equality constraints, and it arises in many fields such as signal and image processing, statistics, computer vision, system identification and control. This class of optimization problems is $\N¶$-hard and a popular approach replaces the rank function with the nuclear norm of the matrix variable. In this paper, we extend the concept of $s$-goodness for a sensing matrix in sparse signal recovery (proposed by Juditsky and Nemirovski [Math Program, 2011]) to linear transformations in LMR. Then, we give characterizations of $s$-goodness in the context of LMR. Using the two characteristic $s$-goodness constants, $γ_s$ and $\hatγ_s$, of a linear transformation, not only do we derive necessary and sufficient conditions for a linear transformation to be $s$-good, but also provide sufficient conditions for exact and stable $s$-rank matrix recovery via the nuclear norm minimization under mild assumptions. Moreover, we give computable upper bounds for one of the $s$-goodness characteristics which leads to verifiable sufficient conditions for exact low-rank matrix recovery.
Adaptive Monte Carlo applied to uncertainty estimation in a five axis machine tool link errors identification
Venue: arXiv cs.OH 2011
Year: 2011

Knowledge of a machine tool axis to axis location errors allows compensation and correcting actions to be taken to enhance its volumetric accuracy. Several procedures exist, involving either lengthy individual test for each geometric error or faster single tests to identify all errors at once. This study focuses on the closed kinematic Cartesian chain method which uses a single setup test to identify the eight link errors of a five axis machine tool. The identification is based on volumetric error measurements for different poses with a non-contact measuring instrument called CapBall, developed in house. In order to evaluate the uncertainty on each identified error, a multi-output Monte Carlo approach is implemented. Uncertainty sources in the measurement and identification chain - such as sensors output, machine drift and frame transformation uncertainties - can be included in the model and propagated to the identified errors. The estimated uncertainties are finally compared to experimental results to assess the method. It shows that the effect of the drift, a disturbance, must be simulated as a function of time the Monte Carlo approach. The machine drift is found to be an important uncertainty in sources for the machine tested.
Next Level of Data Fusion for Human Face Recognition
Venue: arXiv cs.CV 2011
Year: 2011

This paper demonstrates two different fusion techniques at two different levels of a human face recognition process. The first one is called data fusion at lower level and the second one is the decision fusion towards the end of the recognition process. At first a data fusion is applied on visual and corresponding thermal images to generate fused image. Data fusion is implemented in the wavelet domain after decomposing the images through Daubechies wavelet coefficients (db2). During the data fusion maximum of approximate and other three details coefficients are merged together. After that Principle Component Analysis (PCA) is applied over the fused coefficients and finally two different artificial neural networks namely Multilayer Perceptron(MLP) and Radial Basis Function(RBF) networks have been used separately to classify the images. After that, for decision fusion based decisions from both the classifiers are combined together using Bayesian formulation. For experiments, IRIS thermal/visible Face Database has been used. Experimental results show that the performance of multiple classifier system along with decision fusion works well over the single classifier system.
Surrogate Parenthood: Protected and Informative Graphs
Venue: arXiv cs.SI 2011
Year: 2011

Many applications, including provenance and some analyses of social networks, require path-based queries over graph-structured data. When these graphs contain sensitive information, paths may be broken, resulting in uninformative query results. This paper presents innovative techniques that give users more informative graph query results; the techniques leverage a common industry practice of providing what we call surrogates: alternate, less sensitive versions of nodes and edges releasable to a broader community. We describe techniques for interposing surrogate nodes and edges to protect sensitive graph components, while maximizing graph connectivity and giving users as much information as possible. In this work, we formalize the problem of creating a protected account G' of a graph G. We provide a utility measure to compare the informativeness of alternate protected accounts and an opacity measure for protected accounts, which indicates the likelihood that an attacker can recreate the topology of the original graph from the protected account. We provide an algorithm to create a maximally useful protected account of a sensitive graph, and show through evaluation with the PLUS prototype that using surrogates and protected accounts adds value for the user, with no significant impact on the time required to generate results for graph queries.
Information Equals Amortized Communication
Venue: arXiv cs.IT 2011
Year: 2011

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian-Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that M is a deterministic function of X. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. Our work implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible.