OpenRaiser/Intern-Atlas huggingface dataset:
A New Upper Bound for the Traveling Salesman Problem in Cubic Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an $n$-vertex graph can be solved in $O(1.2553^n)$ time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound $O(1.251^n)$ was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.
The GDOF of 3-user MIMO Gaussian interference channel
Venue: arXiv cs.IT 2012
Year: 2012

The paper establishes the optimal generalized degrees of freedom (GDOF) of 3-user $M \times N$ multiple-input multiple-output (MIMO) Gaussian interference channel (GIC) in which each transmitter has $M$ antennas and each receiver has $N$ antennas. A constraint of $2M \leq N$ is imposed so that random coding with message-splitting achieves the optimal GDOF. Unlike symmetric case, two cross channels to unintended receivers from each transmitter can have different strengths, and hence, well known Han-Kobayashi common-private message splitting would not achieve the optimal GDOF. Instead, splitting each user's message into three parts is shown to achieve the optimal GDOF. The capacity of the corresponding deterministic model is first established which provides systematic way of determining side information for converse. Although this deterministic model is philosophically similar to the one considered by Gou and Jafar, additional constraints are imposed so that capacity description of the deterministic model only contains the essential terms for establishing the GDOF of Gaussian case. Based on this, the optimal GDOF of Gaussian case is established with $\mathcal{O}(1)$ capacity approximation. The behavior of the GDOF is interestingly different from that of the corresponding symmetric case. Regarding the converse, several multiuser outer bounds which are suitable for asymmetric case are derived by non-trivial generalization of the symmetric case.
Power-Laws and the Conservation of Information in discrete token systems: Part 1 General Theory
Venue: arXiv cs.IT 2012
Year: 2012

The Conservation of Energy plays a pivotal part in the development of the physical sciences. With the growth of computation and the study of other discrete token based systems such as the genome, it is useful to ask if there are conservation principles which apply to such systems and what kind of functional behaviour they imply for such systems. Here I propose that the Conservation of Hartley-Shannon Information plays the same over-arching role in discrete token based systems as the Conservation of Energy does in physical systems. I will go on to prove that this implies power-law behaviour in component sizes in software systems no matter what they do or how they were built, and also implies the constancy of average gene length in biological systems as reported for example by Lin Xu et al (10.1093/molbev/msk019). These propositions are supported by very large amounts of experimental data extending the first presentation of these ideas in Hatton (2011, IFIP / SIAM / NIST Working Conference on Uncertainty Quantification in Scientific Computing, Boulder, August 2011).
Density Functions subject to a Co-Matroid Constraint
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we consider the problem of finding the {\em densest} subset subject to {\em co-matroid constraints}. We are given a {\em monotone supermodular} set function $f$ defined over a universe $U$, and the density of a subset $S$ is defined to be $f(S)/\crd{S}$. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid $\calM$ a set $S$ is feasible, iff the complement of $S$ is {\em independent} in the matroid. Under such constraints, the problem becomes $\np$-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thus, for instance, we improve the approximation guarantees for the result for partition matroids in the literature.
On the Relative Trust between Inconsistent Data and Inaccurate Constraints
Venue: arXiv cs.DB 2012
Year: 2012

Functional dependencies (FDs) specify the intended data semantics while violations of FDs indicate deviation from these semantics. In this paper, we study a data cleaning problem in which the FDs may not be completely correct, e.g., due to data evolution or incomplete knowledge of the data semantics. We argue that the notion of relative trust is a crucial aspect of this problem: if the FDs are outdated, we should modify them to fit the data, but if we suspect that there are problems with the data, we should modify the data to fit the FDs. In practice, it is usually unclear how much to trust the data versus the FDs. To address this problem, we propose an algorithm for generating non-redundant solutions (i.e., simultaneous modifications of the data and the FDs) corresponding to various levels of relative trust. This can help users determine the best way to modify their data and/or FDs to achieve consistency.
Semantic web based Sensor Planning Services (SPS) for Sensor Web Enablement (SWE)
Venue: arXiv cs.SE 2012
Year: 2012

The Sensor Planning Service (SPS) is service model to define the web service interface for requesting user driven acquisitions and observation. It's defined by the Open Geospatial Consortium (OGC) Sensor Web Enablement (SWE) group to provide standardized interface for tasking sensors to allow to defining, checking, modifying and cancelling tasks of sensor and sensor data. The goal of Sensor Planning Service (SPS) of OGC - SWE is standardize the interoperability between a client and a server collection management environment. The Sensor Planning Service (SPS) is need to automate complex data flow in a large enterprises that are depend on live & stored data from sensors and multimedia equipment. The obstacle are faced in Sensor Planning Service (SPS) are (I) Observation from sensor at the right time and right place will be problem, (II) acquisition information(data) that are collected at a specific time and specific place will be problem. The above two obstacle are accomplished and obtained by the web based semantic technology in order to provide & apply the ontology based semantic rule to user driven a acquisitions and observation of Sensor Planning Service (SPS). The novelty of our approach is by adding the semantic rule to Sensor Planning Service model in SWE and we implemented Sensor Planning Service (SPS) with semantic knowledge based to achieve high standardized service model for Sensor Planning Service (SPS) of OGC - SWE.
A Robust Signal Classification Scheme for Cognitive Radio
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a robust signal classification scheme for achieving comprehensive spectrum sensing of multiple coexisting wireless systems. It is built upon a group of feature-based signal detection algorithms enhanced by the proposed dimension cancelation (DIC) method for mitigating the noise uncertainty problem. The classification scheme is implemented on our testbed consisting real-world wireless devices. The simulation and experimental performances agree with each other well and shows the effectiveness and robustness of the proposed scheme.
Ranked Document Retrieval in (Almost) No Space
Venue: arXiv cs.IR 2012
Year: 2012

Ranked document retrieval is a fundamental task in search engines. Such queries are solved with inverted indexes that require additional 45%-80% of the compressed text space, and take tens to hundreds of microseconds per query. In this paper we show how ranked document retrieval queries can be solved within tens of milliseconds using essentially no extra space over an in-memory compressed representation of the document collection. More precisely, we enhance wavelet trees on bytecodes (WTBCs), a data structure that rearranges the bytes of the compressed collection, so that they support ranked conjunctive and disjunctive queries, using just 6%-18% of the compressed text space.
sSCADA: Securing SCADA Infrastructure Communications
Venue: arXiv cs.IT 2012
Year: 2012

Distributed control systems (DCS) and supervisory control and data acquisition (SCADA) systems were developed to reduce labour costs, and to allow system-wide monitoring and remote control from a central location. Control systems are widely used in critical infrastructures such as electric grid, natural gas, water and wastewater industries. While control systems can be vulnerable to a variety of types of cyber attacks that could have devastating consequences, little research has been done to secure the control systems. American Gas Association (AGA), IEC TC57 WG15, IEEE, NIST and National SCADA Test Bed Program have been actively designing cryptographic standard to protect SCADA systems. American Gas Association (AGA) had originally been designing cryptographic standard to protect SCADA communication links and finished the report AGA 12 part 1. The AGA 12 part 2 has been transferred to IEEE P1711. This paper presents an attack on the protocols in the first draft of AGA standard (Wright et al., 2004). This attack shows that the security mechanisms in the first version of the AGA standard protocol could be easily defeated. We then propose a suite of security protocols optimised for SCADA/DCS systems which include: point-to-point secure channels, authenticated broadcast channels, authenticated emergency channels, and revised authenticated emergency channels. These protocols are designed to address the specific challenges that SCADA systems have.
Edge-Colored Graphs with Applications To Homogeneous Faults
Venue: arXiv cs.DM 2012
Year: 2012

In this paper, we use the concept of colored edge graphs to model homogeneous faults in networks. We then use this model to study the minimum connectivity (and design) requirements of networks for being robust against homogeneous faults within certain thresholds. In particular, necessary and sufficient conditions for most interesting cases are obtained. For example, we will study the following cases: (1) the number of colors (or the number of non-homogeneous network device types) is one more than the homogeneous fault threshold; (2) there is only one homogeneous fault (i.e., only one color could fail); and (3) the number of non-homogeneous network device types is less than five.
Fewest repetitions in infinite binary words
Venue: arXiv cs.DM 2012
Year: 2012

A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold.
Identity-based Trusted Authentication in Wireless Sensor Network
Venue: arXiv cs.NI 2012
Year: 2012

Secure communication mechanisms in Wireless Sensor Networks (WSNs) have been widely deployed to ensure confidentiality, authenticity and integrity of the nodes and data. Recently many WSNs applications rely on trusted communication to ensure large user acceptance. Indeed, the trusted relationship thus far can only be achieved through Trust Management System (TMS) or by adding external security chip on the WSN platform. In this study an alternative mechanism is proposed to accomplish trusted communication between sensors based on the principles defined by Trusted Computing Group (TCG). The results of other related study have also been analyzed to validate and support our findings. Finally the proposed trusted mechanism is evaluated for the potential application on resource constraint devices by quantifying their power consumption on selected major processes. The result proved the proposed scheme can establish trust in WSN with less computation and communication and most importantly eliminating the need for neighboring evaluation for TMS or relying on external security chip.
Optimal Sequential Wireless Relay Placement on a Random Lattice Path
Venue: arXiv cs.NI 2012
Year: 2012

Our work is motivated by the need for impromptu (or "as-you-go") deployment of relay nodes (for establishing a packet communication path with a control centre) by fire-men/commandos while operating in an unknown environment. We consider a model, where a deployment operative steps along a random lattice path whose evolution is Markov. At each step, the path can randomly either continue in the same direction or take a turn "North" or "East," or come to an end, at which point a data source (e.g., a temperature sensor) has to be placed that will send packets to a control centre at the origin of the path. A decision has to be made at each step whether or not to place a wireless relay node. Assuming that the packet generation rate by the source is very low, and simple link-by-link scheduling, we consider the problem of relay placement so as to minimize the expectation of an end-to-end cost metric (a linear combination of the sum of convex hop costs and the number of relays placed). This impromptu relay placement problem is formulated as a total cost Markov decision process. First, we derive the optimal policy in terms of an optimal placement set and show that this set is characterized by a boundary beyond which it is optimal to place. Next, based on a simpler alternative one-step-look-ahead characterization of the optimal policy, we propose an algorithm which is proved to converge to the optimal placement set in a finite number of steps and which is faster than the traditional value iteration. We show by simulations that the distance based heuristic, usually assumed in the literature, is close to the optimal provided that the threshold distance is carefully chosen.
The Medusa of Spatial Sorting: Topological Construction
Venue: arXiv cs.CG 2012
Year: 2012

We consider the simultaneous movement of finitely many colored points in space, calling it a spatial sorting process. The name suggests a purpose that drives the collection to a configuration of increased or decreased order. Mapping such a process to a subset of space-time, we use persistent homology measurements of the time function to characterize the process topologically.
Maximizing Social Welfare in Operator-based Cognitive Radio Networks under Spectrum Uncertainty and Sensing Inaccuracy
Venue: arXiv cs.NI 2012
Year: 2012

In Cognitive Radio Networks (CRNs), secondary users (SUs) are allowed to opportunistically access the unused/under-utilized channels of primary users (PUs). To utilize spectrum resources efficiently, an auction scheme is often applied where an operator serves as an auctioneer and accepts spectrum requests from SUs. Most existing works on spectrum auctions assume that the operator has perfect knowledge of PU activities. In practice, however, it is more likely that the operator only has statistical information of the PU traffic when it is trading a spectrum hole, and it is acquiring more accurate information in real time. In this paper, we distinguish PU channels that are under the control of the operator, where accurate channel states are revealed in real-time, and channels that the operator acquires from PUs out of its control, where a sense-before-use paradigm has to be followed. Considering both spectrum uncertainty and sensing inaccuracy, we study the social welfare maximization problem for serving SUs with various levels of delay tolerance. We first model the problem as a finite horizon Markov decision process when the operator knows all spectrum requests in advance, and propose an optimal dynamic programming based algorithm. We then investigate the case when spectrum requests are submitted online, and propose a greedy algorithm that is 1/2-competitive for homogeneous channels and is comparable to the offline algorithm for more general settings. We further show that the online algorithm together with a payment scheme achieves incentive compatibility for the SUs while guaranteeing a non-negative revenue for the operator.
Ergodic Sum Capacity of Macrodiversity MIMO Systems in Flat Rayleigh Fading
Venue: arXiv cs.IT 2012
Year: 2012

The prospect of base station (BS) cooperation leading to joint combining at widely separated antennas has led to increased interest in macrodiversity systems, where both sources and receive antennas are geographically distributed. In this scenario, little is known analytically about channel capacity since the channel matrices have a very general form where each path may have a different power. Hence, in this paper we consider the ergodic sum capacity of a macrodiversity MIMO system with arbitrary numbers of sources and receive antennas operating over Rayleigh fading channels. For this system, we compute the exact ergodic capacity for a two-source system and a compact approximation for the general system, which is shown to be very accurate over a wide range of cases. Finally, we develop a highly simplified upper-bound which leads to insights into the relationship between capacity and the channel powers. Results are verified by Monte Carlo simulations and the impact on capacity of various channel power profiles is investigated
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances
Venue: arXiv cs.GT 2012
Year: 2012

We study a network extension to the Nash bargaining game, as introduced by Kleinberg and Tardos (STOC'08), where the set of players corresponds to vertices in a graph $G=(V,E)$ and each edge $ij\in E$ represents a possible deal between players $i$ and $j$. We reformulate the problem as a cooperative game and study the following question: Given a game with an empty core (i.e. an unstable game) is it possible, through minimal changes in the underlying network, to stabilize the game? We show that by removing edges in the network that belong to a blocking set we can find a stable solution in polynomial time. This motivates the problem of finding small blocking sets. While it has been previously shown that finding the smallest blocking set is NP-hard (Biro,Kern,Paulusma, TAMC'10), we show that it is possible to efficiently find approximate blocking sets in sparse graphs.
Submartingale Property of E_0 Under The Polarization Transformations
Venue: arXiv cs.IT 2012
Year: 2012

We prove that the relation $E_0(ρ, W^{-}) + E_0(ρ, W^{+}) \geq 2 E_0(ρ, W)$ holds for any binary input discrete memoryless channel $W$, and $ρ\geq 0$.
Transforming floundering into success
Venue: arXiv cs.PL 2012
Year: 2012

We show how logic programs with "delays" can be transformed to programs without delays in a way which preserves information concerning floundering (also known as deadlock). This allows a declarative (model-theoretic), bottom-up or goal independent approach to be used for analysis and debugging of properties related to floundering. We rely on some previously introduced restrictions on delay primitives and a key observation which allows properties such as groundness to be analysed by approximating the (ground) success set. This paper is to appear in Theory and Practice of Logic Programming (TPLP). Keywords: Floundering, delays, coroutining, program analysis, abstract interpretation, program transformation, declarative debugging
Improved Channel Estimation with Partial Sparse Constraint for AF Cooperative Communication Systems
Venue: arXiv cs.IT 2012
Year: 2012

Accurate channel state information (CSI) is necessary for coherent detection in amplify and forward (AF) broadband cooperative communication systems. Based on the assumption of ordinary sparse channel, efficient sparse channel estimation methods have been investigated in our previous works. However, when the cooperative channel exhibits partial sparse structure rather than ordinary sparsity, our previous method cannot take advantage of the prior information. In this paper, we propose an improved channel estimation method with partial sparse constraint on cooperative channel. At first, we formulate channel estimation as a compressive sensing problem and utilize sparse decomposition theory. Secondly, the cooperative channel is reconstructed by LASSO with partial sparse constraint. Finally, numerical simulations are carried out to confirm the superiority of proposed methods over ordinary sparse channel estimation methods.
Supervised Laplacian Eigenmaps with Applications in Clinical Diagnostics for Pediatric Cardiology
Venue: arXiv cs.LG 2012
Year: 2012

Electronic health records contain rich textual data which possess critical predictive information for machine-learning based diagnostic aids. However many traditional machine learning methods fail to simultaneously integrate both vector space data and text. We present a supervised method using Laplacian eigenmaps to augment existing machine-learning methods with low-dimensional representations of textual predictors which preserve the local similarities. The proposed implementation performs alternating optimization using gradient descent. For the evaluation we applied our method to over 2,000 patient records from a large single-center pediatric cardiology practice to predict if patients were diagnosed with cardiac disease. Our method was compared with latent semantic indexing, latent Dirichlet allocation, and local Fisher discriminant analysis. The results were assessed using AUC, MCC, specificity, and sensitivity. Results indicate supervised Laplacian eigenmaps was the highest performing method in our study, achieving 0.782 and 0.374 for AUC and MCC respectively. SLE showed an increase in 8.16% in AUC and 20.6% in MCC over the baseline which excluded textual data and a 2.69% and 5.35% increase in AUC and MCC respectively over unsupervised Laplacian eigenmaps. This method allows many existing machine learning predictors to effectively and efficiently utilize the potential of textual predictors.
Improving multivariate Horner schemes with Monte Carlo tree search
Venue: arXiv cs.SC 2012
Year: 2012

Optimizing the cost of evaluating a polynomial is a classic problem in computer science. For polynomials in one variable, Horner's method provides a scheme for producing a computationally efficient form. For multivariate polynomials it is possible to generalize Horner's method, but this leaves freedom in the order of the variables. Traditionally, greedy schemes like most-occurring variable first are used. This simple textbook algorithm has given remarkably efficient results. Finding better algorithms has proved difficult. In trying to improve upon the greedy scheme we have implemented Monte Carlo tree search, a recent search method from the field of artificial intelligence. This results in better Horner schemes and reduces the cost of evaluating polynomials, sometimes by factors up to two.
Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem
Venue: arXiv cs.DS 2012
Year: 2012

We study the approximability of instances of the minimum entropy set cover problem, parameterized by the average frequency of a random element in the covering sets. We analyze an algorithm combining a greedy approach with another one biased towards large sets. The algorithm is controled by the percentage of elements to which we apply the biased approach. The optimal parameter choice has a phase transition around average density $e$ and leads to improved approximation guarantees when average element frequency is less than $e$.