OpenRaiser/Intern-Atlas huggingface dataset:
The interval constrained 3-coloring problem
Venue: arXiv cs.DM 2009
Year: 2009

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance.
Block-length dependent thresholds in block-sparse compressed sensing
Venue: arXiv cs.IT 2009
Year: 2009

One of the most basic problems in compressed sensing is solving an under-determined system of linear equations. Although this problem seems rather hard certain $\ell_1$-optimization algorithm appears to be very successful in solving it. The recent work of \cite{CRT,DonohoPol} rigorously proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that $\ell_1$-optimization algorithm succeeds in solving the system. In more recent papers \cite{StojnicICASSP09block,StojnicJSTSP09} we considered the setup of the so-called \textbf{block}-sparse unknown vectors. In a large dimensional and statistical context, we determined sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations such that an $\ell_2/\ell_1$-optimization algorithm succeeds in solving the system. The results established in \cite{StojnicICASSP09block,StojnicJSTSP09} assumed a fairly large block-length of the block-sparse vectors. In this paper we consider the block-length to be a parameter of the system. Consequently, we then establish sharp lower bounds on the values of the allowable block-sparsity as functions of the block-length.
Service-oriented high level architecture
Venue: arXiv cs.SE 2009
Year: 2009

Service-oriented High Level Architecture (SOHLA) refers to the high level architecture (HLA) enabled by Service-Oriented Architecture (SOA) and Web Services etc. techniques which supports distributed interoperating services. The detailed comparisons between HLA and SOA are made to illustrate the importance of their combination. Then several key enhancements and changes of HLA Evolved Web Service API are introduced in comparison with native APIs, such as Federation Development and Execution Process, communication mechanisms, data encoding, session handling, testing environment and performance analysis. Some approaches are summarized including Web-Enabling HLA at the communication layer, HLA interface specification layer, federate interface layer and application layer. Finally the problems of current research are discussed, and the future directions are pointed out.
Vertex Cover Problem Parameterized Above and Below Tight Bounds
Venue: arXiv cs.CC 2009
Year: 2009

We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan, Raman and Sikdar, J. Computer and System Sciences, 75(2):137--153, 2009) are fixed-parameter tractable and two other parameterizations are W[1]-hard (one of them is, in fact, W[2]-hard).
Quotient Complexity of Regular Languages
Venue: arXiv cs.FL 2009
Year: 2009

The past research on the state complexity of operations on regular languages is examined, and a new approach based on an old method (derivatives of regular expressions) is presented. Since state complexity is a property of a language, it is appropriate to define it in formal-language terms as the number of distinct quotients of the language, and to call it "quotient complexity". The problem of finding the quotient complexity of a language f(K,L) is considered, where K and L are regular languages and f is a regular operation, for example, union or concatenation. Since quotients can be represented by derivatives, one can find a formula for the typical quotient of f(K,L) in terms of the quotients of K and L. To obtain an upper bound on the number of quotients of f(K,L) all one has to do is count how many such quotients are possible, and this makes automaton constructions unnecessary. The advantages of this point of view are illustrated by many examples. Moreover, new general observations are presented to help in the estimation of the upper bounds on quotient complexity of regular operations.
Positional Effects on Citation and Readership in arXiv
Venue: arXiv cs.DL 2009
Year: 2009

arXiv.org mediates contact with the literature for entire scholarly communities, both through provision of archival access and through daily email and web announcements of new materials, potentially many screenlengths long. We confirm and extend a surprising correlation between article position in these initial announcements, ordered by submission time, and later citation impact, due primarily to intentional "self-promotion" on the part of authors. A pure "visibility" effect was also present: the subset of articles accidentally in early positions fared measurably better in the long-term citation record than those lower down. Astrophysics articles announced in position 1, for example, overall received a median number of citations 83\% higher, while those there accidentally had a 44\% visibility boost. For two large subcommunities of theoretical high energy physics, hep-th and hep-ph articles announced in position 1 had median numbers of citations 50\% and 100\% larger than for positions 5--15, and the subsets there accidentally had visibility boosts of 38\% and 71\%. We also consider the positional effects on early readership. The median numbers of early full text downloads for astro-ph, hep-th, and hep-ph articles announced in position 1 were 82\%, 61\%, and 58\% higher than for lower positions, respectively, and those there accidentally had medians visibility-boosted by 53\%, 44\%, and 46\%. Finally, we correlate a variety of readership features with long-term citations, using machine learning methods, thereby extending previous results on the predictive power of early readership in a broader context. We conclude with some observations on impact metrics and dangers of recommender mechanisms.
Cooperative Jamming for Wireless Physical Layer Security
Venue: arXiv cs.IT 2009
Year: 2009

Cooperative jamming is an approach that has been recently proposed for improving physical layer based security for wireless networks in the presence of an eavesdropper. While the source transmits its message to its destination, a relay node transmits a jamming signal to create interference at the eavesdropper. In this paper, a scenario in which the relay is equipped with multiple antennas is considered. A novel system design is proposed for determining the antenna weights and transmit power of source and relay, so that the system secrecy rate is maximized subject to a total transmit power constraint, or, the transmit power is minimized subject to a secrecy rate constraint. Since the optimal solutions to these problems are difficult to obtain, suboptimal closed-form solutions are proposed that introduce an additional constraint, i.e., the complete nulling of jamming signal at the destination.
An Explicit Construction of Gauss-Jordan Elimination Matrix
Venue: arXiv cs.SC 2009
Year: 2009

A constructive approach to get the reduced row echelon form of a given matrix $A$ is presented. It has been shown that after the $k$th step of the Gauss-Jordan procedure, each entry $a^k_{ij}(i<>j; j > k)$ in the new matrix $A^k$ can always be expressed as a ratio of two determinants whose entries are from the original matrix $A$. The new method also gives a more general generalization of Cramer's rule than existing methods.
On the Number of Membranes in Unary P Systems
Venue: arXiv cs.FL 2009
Year: 2009

We consider P systems with a linear membrane structure working on objects over a unary alphabet using sets of rules resembling homomorphisms. Such a restricted variant of P systems allows for a unique minimal representation of the generated unary language and in that way for an effective solution of the equivalence problem. Moreover, we examine the descriptional complexity of unary P systems with respect to the number of membranes.
On Languages Accepted by P/T Systems Composed of joins
Venue: arXiv cs.FL 2009
Year: 2009

Recently, some studies linked the computational power of abstract computing systems based on multiset rewriting to models of Petri nets and the computation power of these nets to their topology. In turn, the computational power of these abstract computing devices can be understood by just looking at their topology, that is, information flow. Here we continue this line of research introducing J languages and proving that they can be accepted by place/transition systems whose underlying net is composed only of joins. Moreover, we investigate how J languages relate to other families of formal languages. In particular, we show that every J language can be accepted by a log n space-bounded non-deterministic Turing machine with a one-way read-only input. We also show that every J language has a semilinear Parikh map and that J languages and context-free languages (CFLs) are incomparable.
Translation from Classical Two-Way Automata to Pebble Two-Way Automata
Venue: arXiv cs.FL 2009
Year: 2009

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata with an additional "pebble" movable along the input tape. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic pebble two-way automata. However, we show that these two machine models are not independent: if there exists a polynomial trade-off for the classical two-way automata, then there must also exist a polynomial trade-off for the pebble two-way automata. Thus, we have an upward collapse (or a downward separation) from the classical two-way automata to more powerful pebble automata, still staying within the class of regular languages. The same upward collapse holds for complementation of nondeterministic two-way machines. These results are obtained by showing that each pebble machine can be, by using suitable inputs, simulated by a classical two-way automaton with a linear number of states (and vice versa), despite the existing exponential blow-up between the classical and pebble two-way machines.
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Venue: arXiv cs.FL 2009
Year: 2009

Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals simultaneously rewritten during any derivation step can be limited by a small constant regardless of other factors.
Collaborative Training in Sensor Networks: A graphical model approach
Venue: arXiv cs.DC 2009
Year: 2009

Graphical models have been widely applied in solving distributed inference problems in sensor networks. In this paper, the problem of coordinating a network of sensors to train a unique ensemble estimator under communication constraints is discussed. The information structure of graphical models with specific potential functions is employed, and this thus converts the collaborative training task into a problem of local training plus global inference. Two important classes of algorithms of graphical model inference, message-passing algorithm and sampling algorithm, are employed to tackle low-dimensional, parametrized and high-dimensional, non-parametrized problems respectively. The efficacy of this approach is demonstrated by concrete examples.
Recursive Random Number Generator Using Prime Reciprocals
Venue: arXiv cs.CR 2009
Year: 2009

A recursive random number generator using prime reciprocals is described.
Speedup in the Traveling Repairman Problem with Unit Time Windows
Venue: arXiv cs.DS 2009
Year: 2009

The input to the unrooted traveling repairman problem is an undirected metric graph and a subset of nodes, each of which has a time window of unit length. Given that a repairman can start at any location, the goal is to plan a route that visits as many nodes as possible during their respective time windows. A polynomial-time bicriteria approximation algorithm is presented for this problem, gaining an increased fraction of repairman visits for increased speedup of repairman motion. For speedup $s$, we find a $6γ/(s + 1)$-approximation for $s$ in the range $1 \leq s \leq 2$ and a $4γ/s$-approximation for $s$ in the range $2 \leq s \leq 4$, where $γ= 1$ on tree-shaped networks and $γ= 2 + ε$ on general metric graphs.
Knowledge Elecitation for Factors Affecting Taskforce Productivity using a Questionnaire
Venue: arXiv cs.CY 2009
Year: 2009

In this paper we present the process of Knowledge Elicitation through a structured questionnaire technique. This is an effort to depict a problem domain as Investigation of factors affecting taskforce productivity. The problem has to be solved using the expert system technology. This problem is the very first step how to acquire knowledge from the domain experts. Knowledge Elicitation is one of the difficult tasks in knowledge base formation which is a key component of expert system. The questionnaire was distributed among 105 different domain experts of Public and Private Organizations (i.e. Education Institutions, Industries and Research etc) in Pakistan. A total 61 responses from these experts were received. All the experts were well qualified, highly experienced and has been remained the members for selection committees a number of times for different posts. Facts acquired were analyzed from which knowledge was extracted and elicited. A standard shape was given to the questionnaire for further research as a knowledge learning tool. This tool may be used as a standard document for selection and promotion of employees.
Dynamic control of Coding in Delay Tolerant Networks
Venue: arXiv cs.NI 2009
Year: 2009

Delay tolerant Networks (DTNs) leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other. To decrease message delivery delay, the information to be transmitted is replicated in the network. We study replication mechanisms that include Reed-Solomon type codes as well as network coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows us to compute the probability of successful delivery. We study the effect of coding on the performance of the network while optimizing parameters that govern routing.
Feasibility/Desirability Games for Normal Form Games, Choice Models and Evolutionary Games
Venue: arXiv cs.GT 2009
Year: 2009

An abstraction of normal form games is proposed, called Feasibility/Desirability Games (or FD Games in short). FD Games can be seen from three points of view: as a new presentation of games in which Nash equilibria can be found, as choice models in microeconomics or as a model of evolution in games.
A hitting set construction, with application to arithmetic circuit lower bounds
Venue: arXiv cs.CC 2009
Year: 2009

A polynomial identity testing algorithm must determine whether a given input polynomial is identically equal to 0. We give a deterministic black-box identity testing algorithm for univariate polynomials of the form $\sum_{j=0}^t c_j X^{α_j} (a + b X)^{β_j}$. From our algorithm we derive an exponential lower bound for representations of polynomials such as $\prod_{i=1}^{2^n} (X^i-1)$ under this form. It has been conjectured that these polynomials are hard to compute by general arithmetic circuits. Our result shows that the "hardness from derandomization" approach to lower bounds is feasible for a restricted class of arithmetic circuits. The proof is based on techniques from algebraic number theory, and more precisely on properties of the height function of algebraic numbers.
Applicability of a Novel Integer Programming Model for Wireless Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper presents an applicability analysis over a novel integer programming model devoted to optimize power consumption efficiency in heterogeneous wireless sensor networks. This model is based upon a schedule of sensor allocation plans in multiple time intervals subject to coverage and connectivity constraints. By turning off a specific set of redundant sensors in each time interval, it is possible to reduce the total energy consumption in the network and, at the same time, avoid partitioning the whole network by losing some strategic sensors too prematurely. Since the network is heterogeneous, sensors can sense different phenomena from different demand points, with different sample rates. As the problem instances grows the time spent to the execution turns impracticable.
BGP Route Analysis and Management Systems
Venue: arXiv cs.NI 2009
Year: 2009

The Border Gateway Protocol (BGP) is an important component in today's IP network infrastructure. As the main routing protocol of the Internet, clear understanding of its dynamics is crucial for configuring, diagnosing and debugging Internet routing problems. Despite the increase in the services that BGP provide such as MPLS VPNs, there is no much progress achieved in automating the BGP management tasks. In this paper we discuss some of the problems encountered by network engineers when managing BGP networks. We also describe some of the open source tools and methods that attempt to resolve these issues. Then we present some of the features that, if implemented, will ease BGP management related tasks.
Novel Framework for Hidden Data in the Image Page within Executable File Using Computation between Advanced Encryption Standard and Distortion Techniques
Venue: arXiv cs.CR 2009
Year: 2009

The hurried development of multimedia and internet allows for wide distribution of digital media data. It becomes much easier to edit, modify and duplicate digital information. In additional, digital document is also easy to copy and distribute, therefore it may face many threats. It became necessary to find an appropriate protection due to the significance, accuracy and sensitivity of the information. Furthermore, there is no formal method to be followed to discover a hidden data. In this paper, a new information hiding framework is presented.The proposed framework aim is implementation of framework computation between advance encryption standard (AES) and distortion technique (DT) which embeds information in image page within executable file (EXE file) to find a secure solution to cover file without change the size of cover file. The framework includes two main functions; first is the hiding of the information in the image page of EXE file, through the execution of four process (specify the cover file, specify the information file, encryption of the information, and hiding the information) and the second function is the extraction of the hiding information through three process (specify the stego file, extract the information, and decryption of the information).
FPGA-based Controller for a Mobile Robot
Venue: arXiv cs.RO 2009
Year: 2009

With application in the robotics and automation, more and more it becomes necessary the development of applications based on methodologies that facilitate future modifications, updates and enhancements in the original projected system. This project presents a conception of mobile robots using rapid prototyping, distributing the several control actions in growing levels of complexity and computing proposal oriented to embed systems implementation. This kind of controller can be tested on different platform representing the mobile robots using reprogrammable logic components (FPGA). This mobile robot will detect obstacle and also be able to control the speed. Different modules will be Actuators, Sensors, wireless transmission. All this modules will be interfaced using FPGA controller. I would like to construct a mechanically simple robot model, which can measure the distance from obstacle with the aid of sensor and accordingly should able to control the speed of motor. I would like to construct a mechanically simple robot model, which can measure the distance from obstacle with the aid of sensor and accordingly should able to control the speed of motor.
Applications of the DFLU flux to systems of conservation laws
Venue: arXiv cs.NA 2009
Year: 2009

The DFLU numerical flux was introduced in order to solve hyperbolic scalar conservation laws with a flux function discontinuous in space. We show how this flux can be used to solve systems of conservation laws. The obtained numerical flux is very close to a Godunov flux. As an example we consider a system modeling polymer flooding in oil reservoir engineering.
Utility Maximization for Delay Constrained QoS in Wireless
Venue: arXiv cs.NI 2009
Year: 2009

This paper studies the problem of utility maximization for clients with delay based QoS requirements in wireless networks. We adopt a model used in a previous work that characterizes the QoS requirements of clients by their delay constraints, channel reliabilities, and delivery ratio requirements. In this work, we assume that the utility of a client is a function of the delivery ratio it obtains. We treat the delivery ratio for a client as a tunable parameter by the access point (AP), instead of a given value as in the previous work. We then study how the AP should assign delivery ratios to clients so that the total utility of all clients is maximized. We apply the techniques introduced in two previous papers to decompose the utility maximization problem into two simpler problems, a CLIENT problem and an ACCESS-POINT problem. We show that this decomposition actually describes a bidding game, where clients bid for the service time from the AP. We prove that although all clients behave selfishly in this game, the resulting equilibrium point of the game maximizes the total utility. In addition, we also establish an efficient scheduling policy for the AP to reach the optimal point of the ACCESS-POINT problem. We prove that the policy not only approaches the optimal point but also achieves some forms of fairness among clients. Finally, simulation results show that our proposed policy does achieve higher utility than all other compared policies.
Byzantine Convergence in Robots Networks: The Price of Asynchrony
Venue: arXiv cs.DC 2009
Year: 2009

We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.