OpenRaiser/Intern-Atlas huggingface dataset:
Resource-Optimal Planning For An Autonomous Planetary Vehicle
Venue: arXiv cs.AI 2010
Year: 2010

Autonomous planetary vehicles, also known as rovers, are small autonomous vehicles equipped with a variety of sensors used to perform exploration and experiments on a planet's surface. Rovers work in a partially unknown environment, with narrow energy/time/movement constraints and, typically, small computational resources that limit the complexity of on-line planning and scheduling, thus they represent a great challenge in the field of autonomous vehicles. Indeed, formal models for such vehicles usually involve hybrid systems with nonlinear dynamics, which are difficult to handle by most of the current planning algorithms and tools. Therefore, when offline planning of the vehicle activities is required, for example for rovers that operate without a continuous Earth supervision, such planning is often performed on simplified models that are not completely realistic. In this paper we show how the UPMurphi model checking based planning tool can be used to generate resource-optimal plans to control the engine of an autonomous planetary vehicle, working directly on its hybrid model and taking into account several safety constraints, thus achieving very accurate results.
Comparison of Support Vector Machine and Back Propagation Neural Network in Evaluating the Enterprise Financial Distress
Venue: arXiv cs.LG 2010
Year: 2010

Recently, applying the novel data mining techniques for evaluating enterprise financial distress has received much research alternation. Support Vector Machine (SVM) and back propagation neural (BPN) network has been applied successfully in many areas with excellent generalization results, such as rule extraction, classification and evaluation. In this paper, a model based on SVM with Gaussian RBF kernel is proposed here for enterprise financial distress evaluation. BPN network is considered one of the simplest and are most general methods used for supervised training of multilayered neural network. The comparative results show that through the difference between the performance measures is marginal; SVM gives higher precision and lower error rates.
CLP-based protein fragment assembly
Venue: arXiv cs.AI 2010
Year: 2010

The paper investigates a novel approach, based on Constraint Logic Programming (CLP), to predict the 3D conformation of a protein via fragments assembly. The fragments are extracted by a preprocessor-also developed for this work- from a database of known protein structures that clusters and classifies the fragments according to similarity and frequency. The problem of assembling fragments into a complete conformation is mapped to a constraint solving problem and solved using CLP. The constraint-based model uses a medium discretization degree Ca-side chain centroid protein model that offers efficiency and a good approximation for space filling. The approach adapts existing energy models to the protein representation used and applies a large neighboring search strategy. The results shows the feasibility and efficiency of the method. The declarative nature of the solution allows to include future extensions, e.g., different size fragments for better accuracy.
Distributed Demand Response and User Adaptation in Smart Grids
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a distributed framework for demand response and user adaptation in smart grid networks. In particular, we borrow the concept of congestion pricing in Internet traffic control and show that pricing information is very useful to regulate user demand and hence balance network load. User preference is modeled as a willingness to pay parameter which can be seen as an indicator of differential quality of service. Both analysis and simulation results are presented to demonstrate the dynamics and convergence behavior of the algorithm.
Balanced Combinations of Solutions in Multi-Objective Optimization
Venue: arXiv cs.DS 2010
Year: 2010

For every list of integers x_1, ..., x_m there is some j such that x_1 + ... + x_j - x_{j+1} - ... - x_m \approx 0. So the list can be nearly balanced and for this we only need one alternation between addition and subtraction. But what if the x_i are k-dimensional integer vectors? Using results from topological degree theory we show that balancing is still possible, now with k alternations. This result is useful in multi-objective optimization, as it allows a polynomial-time computable balance of two alternatives with conflicting costs. The application to two multi-objective optimization problems yields the following results: - A randomized 1/2-approximation for multi-objective maximum asymmetric traveling salesman, which improves and simplifies the best known approximation for this problem. - A deterministic 1/2-approximation for multi-objective maximum weighted satisfiability.
Degree of Separation in Social Networks
Venue: arXiv cs.SI 2010
Year: 2010

According to the small-world concept, the entire world is connected through short chains of acquaintances. In popular imagination this is captured in the phrase six degrees of separation, implying that any two individuals are, at most, six handshakes away. Social network analysis is the understanding of concepts and information on relationships among interacting units in an ecological system. In this analysis the properties of the actors are explained in terms of the structures of links amongst them. In general, the relational links between the actors are primary and the properties of the actors are secondary. This paper presents two methods to calculate the average degree of separation between the actors or nodes in a graph. We apply this approach to other random graphs depicting social networks and then compare the characteristics of these graphs with the average degree of separation.
Distributed Beamforming in Wireless Multiuser Relay-Interference Networks with Quantized Feedback
Venue: arXiv cs.IT 2010
Year: 2010

We study quantized beamforming in wireless amplify-and-forward relay-interference networks with any number of transmitters, relays, and receivers. We design the quantizer of the channel state information to minimize the probability that at least one receiver incorrectly decodes its desired symbol(s). Correspondingly, we introduce a generalized diversity measure that encapsulates the conventional one as the first-order diversity. Additionally, it incorporates the second-order diversity, which is concerned with the transmitter power dependent logarithmic terms that appear in the error rate expression. First, we show that, regardless of the quantizer and the amount of feedback that is used, the relay-interference network suffers a second-order diversity loss compared to interference-free networks. Then, two different quantization schemes are studied: First, using a global quantizer, we show that a simple relay selection scheme can achieve maximal diversity. Then, using the localization method, we construct both fixed-length and variable-length local (distributed) quantizers (fLQs and vLQs). Our fLQs achieve maximal first-order diversity, whereas our vLQs achieve maximal diversity. Moreover, we show that all the promised diversity and array gains can be obtained with arbitrarily low feedback rates when the transmitter powers are sufficiently large. Finally, we confirm our analytical findings through simulations.
WLAN PIDS
Venue: arXiv cs.OH 2010
Year: 2010

This paper discuss two structures of WLAN system fit to Passenger Information Display System which is partly of subway.
On optimizing low SNR wireless networks using network coding
Venue: arXiv cs.IT 2010
Year: 2010

The rate optimization for wireless networks with low SNR is investigated. While the capacity in the limit of disappearing SNR is known to be linear for fading and non-fading channels, we study the problem of operating in low SNR wireless network with given node locations that use network coding over flows. The model we develop for low SNR Gaussian broadcast channel and multiple access channel respectively operates in a non-trivial feasible rate region. We show that the problem reduces to the optimization of total network power which can be casted as standard linear multi-commodity min-cost flow program with no inherent combinatorially difficult structure when network coding is used with non integer constraints (which is a reasonable assumption). This is essentially due to the linearity of the capacity with respect to vanishing SNR which helps avoid the effect of interference for the degraded broadcast channel and multiple access environment in consideration, respectively. We propose a fully decentralized Primal-Dual Subgradient Algorithm for achieving optimal rates on each subgraph (i.e. hyperarcs) of the network to support the set of traffic demands (multicast/unicast connections).
On Optimal Deadlock Detection Scheduling
Venue: arXiv cs.DC 2010
Year: 2010

Deadlock detection scheduling is an important, yet often overlooked problem that can significantly affect the overall performance of deadlock handling. Excessive initiation of deadlock detection increases overall message usage, resulting in degraded system performance in the absence of deadlocks; while insufficient initiation of deadlock detection increases the deadlock persistence time, resulting in an increased deadlock resolution cost in the presence of deadlocks. The investigation of this performance tradeoff, however, is missing in the literature. This paper studies the impact of deadlock detection scheduling on the overall performance of deadlock handling. In particular, we show that there exists an optimal deadlock detection frequency that yields the minimum long-run mean average cost, which is determined by the message complexities of the deadlock detection and resolution algorithms being used, as well as the rate of deadlock formation, denoted as $λ$. For the best known deadlock detection and resolution algorithms, we show that the asymptotically optimal frequency of deadlock detection scheduling that minimizes the overall message overhead is ${\cal O}((λn)^{1/3})$, when the total number $n$ of processes is sufficiently large. Furthermore, we show that in general fully distributed (uncoordinated) deadlock detection scheduling cannot be performed as efficiently as centralized (coordinated) deadlock detection scheduling.
A Framework for Partial Secrecy
Venue: arXiv cs.IT 2010
Year: 2010

We consider theoretical limits of partial secrecy in a setting where an eavesdropper attempts to causally reconstruct an information sequence with low distortion based on an intercepted transmission and the past of the sequence. The transmitter and receiver have limited secret key at their disposal but not enough to establish perfect secrecy with a one-time pad. From another viewpoint, the eavesdropper is acting as an adversary, competing in a zero-sum repeated game against the sender and receiver of the secrecy system. In this case, the information sequence represents a sequence of actions, and the distortion function captures the payoff of the game. We give an information theoretic region expressing the tradeoff between secret key rate and max-min distortion for the eavesdropper. We also simplify this characterization to a linear program. As an example, we discuss how to optimally use secret key to hide Bernoulli-p bits from an eavesdropper so that they incur maximal Hamming distortion.
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
Venue: arXiv cs.CC 2010
Year: 2010

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are \#P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.
Is submodularity testable?
Venue: arXiv cs.DS 2010
Year: 2010

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f:{0,1}^n \rightarrow R. The distance to submodularity is the minimum fraction of values of $f$ that need to be modified to make f submodular. If this distance is more than epsilon > 0, then we say that f is epsilon-far from being submodular. The aim is to have an efficient procedure that, given input f that is epsilon-far from being submodular, certifies that f is not submodular. We analyze a very natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be very efficient in terms of epsilon. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.
Associative control processor with a rigid structure
Venue: arXiv cs.AR 2010
Year: 2010

The approach of applying associative processor for decision making problem was proposed. It focuses on hardware implementations of fuzzy processing systems, associativity as effective management basis of fuzzy processor. The structural approach is being developed resulting in a quite simple and compact parallel associative memory unit (PAMU). The memory cost and speed comparison of processors with rigid and soft-variable structure is given. Also the example PAMU flashing is considered.
An Information-Theoretic Analysis of the Security of Communication Systems Employing the Encoding-Encryption Paradigm
Venue: arXiv cs.CR 2010
Year: 2010

This paper proposes a generic approach for providing enhanced security to communication systems which encode their data for reliability before encrypting it through a stream cipher for security. We call this counter-intuitive technique the {\em encoding-encryption} paradigm, and use as motivating example the standard for mobile telephony GSM. The enhanced security is based on a dedicated homophonic or wire-tap channel coding that introduces pure randomness, combined with the randomness of the noise occurring over the communication channel. Security evaluation regarding recovery of the secret key employed in the keystream generator is done through an information theoretical approach. We show that with the aid of a dedicated wire-tap encoder, the amount of uncertainty that the adversary must face about the secret key given all the information he could gather during different passive or active attacks he can mount, is a decreasing function of the sample available for cryptanalysis. This means that the wire-tap encoder can indeed provide an information theoretical security level over a period of time, but after a large enough sample is collected the function tends to zero, entering a regime in which a computational security analysis is needed for estimation of the resistance against the secret key recovery.
Robust Adaptive Beamforming Based on Steering Vector Estimation via Semidefinite Programming Relaxation
Venue: arXiv cs.IT 2010
Year: 2010

We develop a new approach to robust adaptive beamforming in the presence of signal steering vector errors. Since the signal steering vector is known imprecisely, its presumed (prior) value is used to find a more accurate estimate of the actual steering vector, which then is used for obtaining the optimal beamforming weight vector. The objective for finding such an estimate of the actual signal steering vector is the maximization of the beamformer output power, while the constraints are the normalization condition and the requirement that the estimate of the steering vector does not converge to an interference steering vector. Our objective and constraints are free of any design parameters of non-unique choice. The resulting optimization problem is a non-convex quadratically constrained quadratic program, which is NP hard in general. However, for our problem we show that an efficient solution can be found using the semi-definite relaxation technique. Moreover, the strong duality holds for the proposed problem and can also be used for finding the optimal solution efficiently and at low complexity. In some special cases, the solution can be even found in closed-form. Our simulation results demonstrate the superiority of the proposed method over other previously developed robust adaptive beamforming methods for several frequently encountered types of signal steering vector errors.
Witness (Delaunay) Graphs
Venue: arXiv cs.CG 2010
Year: 2010

Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis, and have also received substantial attention from the graph drawing community, as they are a natural way of implicitly representing graphs. However, as a tool for graph representation, proximity graphs have some limitations that may be overcome with suitable generalizations. We introduce a generalization, witness graphs, that encompasses both the goal of more power and flexibility for graph drawing issues and a wider spectrum for neighborhood analysis. We study in detail two concrete examples, both related to Delaunay graphs, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness graphs.
Web to Semantic Web & Role of Ontology
Venue: arXiv cs.OH 2010
Year: 2010

In this research paper we are briefly presenting current major web problems and introducing semantic web technologies with the claim of solving existing web's problems. Furthermore we are describing Ontology as the main building block of semantic web and focusing on its contributions to semantic web progress and current limitations.
Coloring translates and homothets of a convex body
Venue: arXiv cs.DM 2010
Year: 2010

We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in $\RR^n$.
Codes over Matrix Rings for Space-Time Coded Modulations
Venue: arXiv cs.IT 2010
Year: 2010

It is known that, for transmission over quasi-static MIMO fading channels with n transmit antennas, diversity can be obtained by using an inner fully diverse space-time block code while coding gain, derived from the determinant criterion, comes from an appropriate outer code. When the inner code has a cyclic algebra structure over a number field, as for perfect space-time codes, an outer code can be designed via coset coding. More precisely, we take the quotient of the algebra by a two-sided ideal which leads to a finite alphabet for the outer code, with a cyclic algebra structure over a finite field or a finite ring. We show that the determinant criterion induces various metrics on the outer code, such as the Hamming and Bachoc distances. When n=2, partitioning the 2x2 Golden code by using an ideal above the prime 2 leads to consider codes over either M2(F_2) or M2(F_2[i]), both being non-commutative alphabets. Matrix rings of higher dimension, suitable for 3x3 and 4x4 perfect codes, give rise to more complex examples.
Towards Design and Implementation of a Language Technology based Information Processor for PDM Systems
Venue: arXiv cs.IR 2010
Year: 2010

Product Data Management (PDM) aims to provide 'Systems' contributing in industries by electronically maintaining organizational data, improving data repository system, facilitating with easy access to CAD and providing additional information engineering and management modules to access, store, integrate, secure, recover and manage information. Targeting one of the unresolved issues i.e., provision of natural language based processor for the implementation of an intelligent record search mechanism, an approach is proposed and discussed in detail in this manuscript. Designing an intelligent application capable of reading and analyzing user's structured and unstructured natural language based text requests and then extracting desired concrete and optimized results from knowledge base is still a challenging task for the designers because it is still very difficult to completely extract Meta data out of raw data. Residing within the limited scope of current research and development; we present an approach capable of reading user's natural language based input text, understanding the semantic and extracting results from repositories. To evaluate the effectiveness of implemented prototyped version of proposed approach, it is compared with some existing PDM Systems, in the end the discussion is concluded with an abstract presentation of resultant comparison amongst implemented prototype and some existing PDM Systems.
Fast, precise and dynamic distance queries
Venue: arXiv cs.DS 2010
Year: 2010

We present an approximate distance oracle for a point set S with n points and doubling dimension λ. For every ε>0, the oracle supports (1+ε)-approximate distance queries in (universal) constant time, occupies space [ε^{-O(λ)} + 2^{O(λ log λ)}]n, and can be constructed in [2^{O(λ)} log3 n + ε^{-O(λ)} + 2^{O(λ log λ)}]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2^{O(λ)} log n + ε^{-O(λ)} + 2^{O(λ log λ)} update time. This is the first fully dynamic (1+ε)-distance oracle.