OpenRaiser/Intern-Atlas huggingface dataset:
Timed Parity Games: Complexity and Robustness
Venue: arXiv cs.LO 2008
Year: 2008

We consider two-player games played in real time on game structures with clocks and parity objectives. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., nonconcurrent) finite-state (i.e., untimed) parity games. The states of the resulting game are pairs of clock regions of the original game. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust strategies. Using a limit-robust strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.
Beyond Node Degree: Evaluating AS Topology Models
Venue: arXiv cs.NI 2008
Year: 2008

Many models have been proposed to generate Internet Autonomous System (AS) topologies, most of which make structural assumptions about the AS graph. In this paper we compare AS topology generation models with several observed AS topologies. In contrast to most previous works, we avoid making assumptions about which topological properties are important to characterize the AS topology. Our analysis shows that, although matching degree-based properties, the existing AS topology generation models fail to capture the complexity of the local interconnection structure between ASs. Furthermore, we use BGP data from multiple vantage points to show that additional measurement locations significantly affect local structure properties, such as clustering and node centrality. Degree-based properties, however, are not notably affected by additional measurements locations. These observations are particularly valid in the core. The shortcomings of AS topology generation models stems from an underestimation of the complexity of the connectivity in the core caused by inappropriate use of BGP data.
Inapproximability for metric embeddings into R^d
Venue: arXiv cs.CG 2008
Year: 2008

We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R^d, where d is fixed (and small). For d=1, it was known that approximating the minimum distortion with a factor better than roughly n^(1/12) is NP-hard. From this result we derive inapproximability with factor roughly n^(1/(22d-10)) for every fixed d\ge 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala). For d\ge 3, we obtain a stronger inapproximability result by a different reduction: assuming P \ne NP, no polynomial-time algorithm can distinguish between spaces embeddable in R^d with constant distortion from spaces requiring distortion at least n^(c/d), for a constant c>0. The exponent c/d has the correct order of magnitude, since every n-point metric space can be embedded in R^d with distortion O(n^{2/d}\log^{3/2}n) and such an embedding can be constructed in polynomial time by random projection. For d=2, we give an example of a metric space that requires a large distortion for embedding in R^2, while all not too large subspaces of it embed almost isometrically.
Congestion Reduction Using Ad hoc Message Dissemination in Vehicular Networks
Venue: arXiv cs.NI 2008
Year: 2008

Vehicle-to-vehicle communications can be used effectively for intelligent transport systems (ITS) and location-aware services. The ability to disseminate information in an ad-hoc fashion allows pertinent information to propagate faster through the network. In the realm of ITS, the ability to spread warning information faster and further is of great advantage to the receivers of this information. In this paper we propose and present a message-dissemination procedure that uses vehicular wireless protocols for influencing traffic flow, reducing congestion in road networks. The computational experiments presented in this paper show how an intelligent driver model (IDM) and car-following model can be adapted to 'react' to the reception of information. This model also presents the advantages of coupling together traffic modelling tools and network simulation tools.
Ordinateur porté support de réalité augmentée pour des activités de maintenance et de dépannage
Venue: arXiv cs.HC 2008
Year: 2008

In this paper we present a case study of use of wearable computer within the framework of activities of maintenance and repairing. Besides the study of configuration of this wearable computer and its peripherals, we show the integration of context, in-situ storage, traceability and regulation in these activities. This case study is in the scope of a huge project called HMTD (Help Me To Do) which aim is to apply MOCOCO (Mobility, COoperation, COntextualisation) and IMERA (Mobile Interaction in the Augmented Real Environment) principles for better use, maintenance and repairing of equipments in the domestic, public and professional situations.
Energy-Efficient Power Control in Multipath CDMA Channels via Large System Analysis
Venue: arXiv cs.IT 2008
Year: 2008

This paper is focused on the design and analysis of power control procedures for the uplink of multipath code-division-multiple-access (CDMA) channels based on the large system analysis (LSA). Using the tools of LSA, a new decentralized power control algorithm aimed at energy efficiency maximization and requiring very little prior information on the interference background is proposed; moreover, it is also shown that LSA can be used to predict with good accuracy the performance and operational conditions of a large network operating at the equilibrium over a multipath channel, i.e. the power, signal-to-interference-plus-noise ratio (SINR) and utility profiles across users, wherein the utility is defined as the number of bits reliably delivered to the receiver for each energy-unit used for transmission. Additionally, an LSA-based performance comparison among linear receivers is carried out in terms of achieved energy efficiency at the equilibrium. Finally, the problem of the choice of the utility-maximizing training length is also considered. Numerical results show a very satisfactory agreement of the theoretical analysis with simulation results obtained with reference to systems with finite (and not so large) numbers of users.
The two-user Gaussian interference channel: a deterministic view
Venue: arXiv cs.IT 2008
Year: 2008

This paper explores the two-user Gaussian interference channel through the lens of a natural deterministic channel model. The main result is that the deterministic channel uniformly approximates the Gaussian channel, the capacity regions differing by a universal constant. The problem of finding the capacity of the Gaussian channel to within a constant error is therefore reduced to that of finding the capacity of the far simpler deterministic channel. Thus, the paper provides an alternative derivation of the recent constant gap capacity characterization of Etkin, Tse, and Wang. Additionally, the deterministic model gives significant insight towards the Gaussian channel.
Another Co*cryption Method
Venue: arXiv cs.CR 2008
Year: 2008

We consider the enciphering of a data stream while being compressed by a LZ algorithm. This has to be compared to the classical encryption after compression methods used in security protocols. Actually, most cryptanalysis techniques exploit patterns found in the plaintext to crack the cipher; compression techniques reduce these attacks. Our scheme is based on a LZ compression in which a Vernam cipher has been added. We make some security remarks by trying to measure its randomness with statistical tests. Such a scheme could be employed to increase the speed of security protocols and to decrease the computing power for mobile devices.
An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership
Venue: arXiv cs.NI 2008
Year: 2008

In highly distributed Internet measurement systems distributed agents periodically measure the Internet using a tool called {\tt traceroute}, which discovers a path in the network graph. Each agent performs many traceroute measurement to a set of destinations in the network, and thus reveals a portion of the Internet graph as it is seen from the agent locations. In every period we need to check whether previously discovered edges still exist in this period, a process termed {\em validation}. For this end we maintain a database of all the different measurements performed by each agent. Our aim is to be able to {\em validate} the existence of all previously discovered edges in the minimum possible time. In this work we formulate the validation problem as a generalization of the well know set cover problem. We reduce the set cover problem to the validation problem, thus proving that the validation problem is ${\cal NP}$-hard. We present a $O(\log n)$-approximation algorithm to the validation problem, where $n$ in the number of edges that need to be validated. We also show that unless ${\cal P = NP}$ the approximation ratio of the validation problem is $Ω(\log n)$.
Recover plaintext attack to block ciphers
Venue: arXiv cs.CR 2008
Year: 2008

we will present an estimation for the upper-bound of the amount of 16-bytes plaintexts for English texts, which indicates that the block ciphers with block length no more than 16-bytes will be subject to recover plaintext attacks in the occasions of plaintext -known or plaintext-chosen attacks.
Multiplication in Cyclotomic Rings and its Application to Finite Fields
Venue: arXiv cs.DM 2008
Year: 2008

A representation of finite fields that has proved useful when implementing finite field arithmetic in hardware is based on an isomorphism between subrings and fields. In this paper, we present an unified formulation for multiplication in cyclotomic rings and cyclotomic fields in that most arithmetic operations are done on vectors. From this formulation we can generate optimized algorithms for multiplication. For example, one of the proposed algorithms requires approximately half the number of coordinate-level multiplications at the expense of extra coordinate-level additions. Our method is then applied to the finite fields GF(q^m) to further reduce the number of operations. We then present optimized algorithms for multiplication in finite fields with type-I and type-II optimal normal bases.
Modularity clustering is force-directed layout
Venue: arXiv cs.DM 2008
Year: 2008

Two natural and widely used representations for the community structure of networks are clusterings, which partition the vertex set into disjoint subsets, and layouts, which assign the vertices to positions in a metric space. This paper unifies prominent characterizations of layout quality and clustering quality, by showing that energy models of pairwise attraction and repulsion subsume Newman and Girvan's modularity measure. Layouts with optimal energy are relaxations of, and are thus consistent with, clusterings with optimal modularity, which is of practical relevance because both representations are complementary and often used together.
Encapsulation theory fundamentals
Venue: arXiv cs.SE 2008
Year: 2008

This paper proposes a theory of encapsulation, establishing a relationship between encapsulation and information hiding through the concept of potential structural complexity (P.S.C.), the maximum possible number of source code dependencies that can exist between program units in a software system. The P.S.C. of various, simple systems is examined in an attempt to demonstrate how P.S.C. changes as program units are encapsulated among different configurations of subsystems.
Avoider robot design to dim the fire with dt basic mini system
Venue: arXiv cs.RO 2008
Year: 2008

Avoider robot is mean robot who is designed to avoid the block in around. Except that, this robot is also added by an addition application to dim the fire. This robot is made with ultrasonic sensor PING. This sensor is set on the front, right and left from robot. This sensor is used robot to look for the right street, so that robot can walk on. After the robot can look for the right street, next accomplished the robot is looking for the fire in around. And the next, dim the fire with fan. This robot is made with basic stamp 2 micro-controller. And that micro-controller can be found in dt-basic mini system module. This robot is made with servo motor on the right and left side, which is used to movement.
AceWiki: A Natural and Expressive Semantic Wiki
Venue: arXiv cs.HC 2008
Year: 2008

We present AceWiki, a prototype of a new kind of semantic wiki using the controlled natural language Attempto Controlled English (ACE) for representing its content. ACE is a subset of English with a restricted grammar and a formal semantics. The use of ACE has two important advantages over existing semantic wikis. First, we can improve the usability and achieve a shallow learning curve. Second, ACE is more expressive than the formal languages of existing semantic wikis. Our evaluation shows that people who are not familiar with the formal foundations of the Semantic Web are able to deal with AceWiki after a very short learning phase and without the help of an expert.
A Compositional Query Algebra for Second-Order Logic and Uncertain Databases
Venue: arXiv cs.DB 2008
Year: 2008

World-set algebra is a variable-free query language for uncertain databases. It constitutes the core of the query language implemented in MayBMS, an uncertain database system. This paper shows that world-set algebra captures exactly second-order logic over finite structures, or equivalently, the polynomial hierarchy. The proofs also imply that world-set algebra is closed under composition, a previously open problem.
Capacity and Performance of Adaptive MIMO System Based on Beam-Nulling
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose a scheme called "beam-nulling" for MIMO adaptation. In the beam-nulling scheme, the eigenvector of the weakest subchannel is fed back and then signals are sent over a generated subspace orthogonal to the weakest subchannel. Theoretical analysis and numerical results show that the capacity of beam-nulling is closed to the optimal water-filling at medium SNR. Additionally, signal-to-interference-plus-noise ratio (SINR) of MMSE receiver is derived for beam-nulling. Then the paper presents the associated average bit-error rate (BER) of beam-nulling numerically which is verified by simulation. Simulation results are also provided to compare beam-nulling with beamforming. To improve performance further, beam-nulling is concatenated with linear dispersion code. Simulation results are also provided to compare the concatenated beam-nulling scheme with the beamforming scheme at the same data rate. Additionally, the existing beamforming and new proposed beam-nulling can be extended if more than one eigenvector is available at the transmitter. The new extended schemes are called multi-dimensional (MD) beamforming and MD beam-nulling. Theoretical analysis and numerical results in terms of capacity are also provided to evaluate the new extended schemes. Simulation results show that the MD scheme with LDC can outperform the MD scheme with STBC significantly when the data rate is high.
Message-passing for Maximum Weight Independent Set
Venue: arXiv cs.AI 2008
Year: 2008

We investigate the use of message-passing algorithms for the problem of finding the max-weight independent set (MWIS) in a graph. First, we study the performance of the classical loopy max-product belief propagation. We show that each fixed point estimate of max-product can be mapped in a natural way to an extreme point of the LP polytope associated with the MWIS problem. However, this extreme point may not be the one that maximizes the value of node weights; the particular extreme point at final convergence depends on the initialization of max-product. We then show that if max-product is started from the natural initialization of uninformative messages, it always solves the correct LP -- if it converges. This result is obtained via a direct analysis of the iterative algorithm, and cannot be obtained by looking only at fixed points. The tightness of the LP relaxation is thus necessary for max-product optimality, but it is not sufficient. Motivated by this observation, we show that a simple modification of max-product becomes gradient descent on (a convexified version of) the dual of the LP, and converges to the dual optimum. We also develop a message-passing algorithm that recovers the primal MWIS solution from the output of the descent algorithm. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of MAP estimation for probability distributions over finite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation.
Branching proofs of infeasibility in low density subset sum problems
Venue: arXiv cs.CC 2008
Year: 2008

We prove that the subset sum problem has a polynomial time computable certificate of infeasibility for all $a$ weight vectors with density at most $1/(2n)$ and for almost all integer right hand sides. The certificate is branching on a hyperplane, i.e. by a methodology dual to the one explored by Lagarias and Odlyzko; Frieze; Furst and Kannan; and Coster et. al. The proof has two ingredients. We first prove that a vector that is near parallel to $a$ is a suitable branching direction, regardless of the density. Then we show that for a low density $a$ such a near parallel vector can be computed using diophantine approximation, via a methodology introduced by Frank and Tardos. We also show that there is a small number of long intervals whose disjoint union covers the integer right hand sides, for which the infeasibility is proven by branching on the above hyperplane.
Use of Astronomical Literature - A Report on Usage Patterns
Venue: arXiv cs.DL 2008
Year: 2008

In this paper we present a number of metrics for usage of the SAO/NASA Astrophysics Data System (ADS). Since the ADS is used by the entire astronomical community, these are indicative of how the astronomical literature is used. We will show how the use of the ADS has changed both quantitatively and qualitatively. We will also show that different types of users access the system in different ways. Finally, we show how use of the ADS has evolved over the years in various regions of the world. The ADS is funded by NASA Grant NNG06GG68G.
A Reliable SVD based Watermarking Schem
Venue: arXiv cs.MM 2008
Year: 2008

We propose a novel scheme for watermarking of digital images based on singular value decomposition (SVD), which makes use of the fact that the SVD subspace preserves significant amount of information of an image, as compared to its singular value matrix, Zhang and Li (2005). The principal components of the watermark are embedded in the original image, leaving the detector with a complimentary set of singular vectors for watermark extraction. The above step invariably ensures that watermark extraction from the embedded watermark image, using a modified matrix, is not possible, thereby removing a major drawback of an earlier proposed algorithm by Liu and Tan (2002).
Generalized Cross-correlation Properties of Chu Sequences
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we analyze the cross-correlation properties for Chu sequences, which provide information on the distribution of the maximum magnitudes of the cross-correlation function. Furthermore, we can obtain the number of available sequences for a given maximum magnitude of the cross-correlation function and the sequence length.
Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three
Venue: arXiv cs.CC 2008
Year: 2008

We study the model checking problem, for fixed structures A, over positive equality-free first-order logic -- a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(A). We prove a complete complexity classification for this problem when A ranges over 1.) boolean structures and 2.) digraphs of size (less than or equal to) three. The former class displays dichotomy between Logspace and Pspace-complete, while the latter class displays tetrachotomy between Logspace, NP-complete, co-NP-complete and Pspace-complete.
On Complexity of Minimum Leaf Out-branching Problem
Venue: arXiv cs.DS 2008
Year: 2008

Given a digraph $D$, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in $D$ an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. Gutin, Razgon and Kim (2008) proved that MinLOB is polynomial time solvable for acyclic digraphs which are exactly the digraphs of directed path-width (DAG-width, directed tree-width, respectively) 0. We investigate how much one can extend this polynomiality result. We prove that already for digraphs of directed path-width (directed tree-width, DAG-width, respectively) 1, MinLOB is NP-hard. On the other hand, we show that for digraphs of restricted directed tree-width (directed path-width, DAG-width, respectively) and a fixed integer $k$, the problem of checking whether there is an out-branching with at most $k$ leaves is polynomial time solvable.
Optimization of Location Management for PCS Networks with CTRW Mobility Model
Venue: arXiv cs.NI 2008
Year: 2008

This paper considers the design of the optimal locationupdate area (LA) of the distance-based scheme for personal communication service (PCS) networks. We focus on the optimization of two design parameters associated with the LA: 1) initial position upon LA update; 2) distance threshold for triggering of LA update. Based on the popular continuous-time random walk (CTRW) mobility model, we propose a novel analytical framework that uses a diffusion equation to minimize the location management cost. In this framework, a number of measurable physical parameters, such as length of road section, angle between road sections, and road section crossing time, can be integrated into the system design. This framework allows us to easily evaluate the total cost under general call arrival distributions and LA of different shapes. For the particular case of circular LA and small Poisson call-arrival rate, we prove the following: (1) When the drift is weak, the optimal initial position approaches the center of the LA; when the drift is strong, it approaches the boundary of the LA. (2) Comparing the optimal initial-position and center-initial-position solutions (which is assumed in most prior work), when the drift is weak, the optimal distance threshold and the minimum total cost are roughly equal; when the drift is strong, the optimal distance threshold in the later is about 1.260 times that in the former, and the minimum total cost in the later is about 1.587 times that in the former. That is, optimizing on initial position, which previous work did not consider, has the potential of reducing the cost measure by 37%.