OpenRaiser/Intern-Atlas huggingface dataset:
A New Distributed Topology Control Algorithm for Wireless Environments with Non-Uniform Path Loss and Multipath Propagation
Venue: arXiv cs.NI 2009
Year: 2009

Each node in a wireless multi-hop network can adjust the power level at which it transmits and thus change the topology of the network to save energy by choosing the neighbors with which it directly communicates. Many previous algorithms for distributed topology control have assumed an ability at each node to deduce some location-based information such as the direction and the distance of its neighbor nodes with respect to itself. Such a deduction of location-based information, however, cannot be relied upon in real environments where the path loss exponents vary greatly leading to significant errors in distance estimates. Also, multipath effects may result in different signal paths with different loss characteristics, and none of these paths may be line-of-sight, making it difficult to estimate the direction of a neighboring node. In this paper, we present Step Topology Control (STC), a simple distributed topology control algorithm which reduces energy consumption while preserving the connectivity of a heterogeneous sensor network without use of any location-based information. We show that the STC algorithm achieves the same or better order of communication and computational complexity when compared to other known algorithms that also preserve connectivity without the use of location-based information. We also present a detailed simulation-based comparative analysis of the energy savings and interference reduction achieved by the algorithms. The results show that, in spite of not incurring a higher communication or computational complexity, the STC algorithm performs better than other algorithms in uniform wireless environments and especially better when path loss characteristics are non-uniform.
The P versus NP Brief
Venue: arXiv cs.CC 2009
Year: 2009

This paper discusses why P and NP are likely to be different. It analyses the essence of the concepts and points out that P and NP might be diverse by sheer definition. It also speculates that P and NP may be unequal due to natural laws.
Likelihood ratios and Bayesian inference for Poisson channels
Venue: arXiv cs.IT 2009
Year: 2009

In recent years, infinite-dimensional methods have been introduced for the Gaussian channels estimation. The aim of this paper is to study the application of similar methods to Poisson channels. In particular we compute the Bayesian estimator of a Poisson channel using the likelihood ratio and the discrete Malliavin gradient. This algorithm is suitable for numerical implementation via the Monte-Carlo scheme. As an application we provide an new proof of the formula obtained recently by Guo, Shamai and Verduú relating some derivatives of the input-output mutual information of a time-continuous Poisson channel and the conditional mean estimator of the input. These results are then extended to mixed Gaussian-Poisson channels.
Bounds for Visual Cryptography Schemes
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, we investigate the best pixel expansion of the various models of visual cryptography schemes. In this regard, we consider visual cryptography schemes introduced by Tzeng and Hu [13]. In such a model, only minimal qualified sets can recover the secret image and that the recovered secret image can be darker or lighter than the background. Blundo et al. [4] introduced a lower bound for the best pixel expansion of this scheme in terms of minimal qualified sets. We present another lower bound for the best pixel expansion of the scheme. As a corollary, we introduce a lower bound, based on an induced matching of hypergraph of qualified sets, for the best pixel expansion of the aforementioned model and the traditional model of visual cryptography realized by basis matrices. Finally, we study access structures based on graphs and we present an upper bound for the smallest pixel expansion in terms of strong chromatic index.
Generalized D-Forms Have No Spurious Creases
Venue: arXiv cs.CG 2009
Year: 2009

A convex surface that is flat everywhere but on finitely many smooth curves (or "seams") and points is a seam form. We show that the only creases through the flat components of a seam form are either between vertices or tangent to the seams. As corollaries we resolve open problems about certain special seam forms: the flat components of a D-form have no creases at all, and the flat component of a pita-form has at most one crease, between the seam's endpoints.
Rateless codes for AVC models
Venue: arXiv cs.IT 2009
Year: 2009

The arbitrarily varying channel (AVC) is a channel model whose state is selected maliciously by an adversary. Fixed-blocklength coding assumes a worst-case bound on the adversary's capabilities, which leads to pessimistic results. This paper defines a variable-length perspective on this problem, for which achievable rates are shown that depend on the realized actions of the adversary. Specifically, rateless codes are constructed which require a limited amount of common randomness. These codes are constructed for two kinds of AVC models. In the first the channel state cannot depend on the channel input, and in the second it can. As a byproduct, the randomized coding capacity of the AVC with state depending on the transmitted codeword is found and shown to be achievable with a small amount of common randomness. The results for this model are proved using a randomized strategy based on list decoding.
From vectors to mnesors
Venue: arXiv cs.LO 2009
Year: 2009

The mnesor theory is the adaptation of vectors to artificial intelligence. The scalar field is replaced by a lattice. Addition becomes idempotent and multiplication is interpreted as a selection operation. We also show that mnesors can be the foundation for a linear calculus.
Cognitive Networks Achieve Throughput Scaling of a Homogeneous Network
Venue: arXiv cs.IT 2009
Year: 2009

We study two distinct, but overlapping, networks that operate at the same time, space, and frequency. The first network consists of $n$ randomly distributed \emph{primary users}, which form either an ad hoc network, or an infrastructure-supported ad hoc network with $l$ additional base stations. The second network consists of $m$ randomly distributed, ad hoc secondary users or cognitive users. The primary users have priority access to the spectrum and do not need to change their communication protocol in the presence of secondary users. The secondary users, however, need to adjust their protocol based on knowledge about the locations of the primary nodes to bring little loss to the primary network's throughput. By introducing preservation regions around primary receivers and avoidance regions around primary base stations, we propose two modified multihop routing protocols for the cognitive users. Base on percolation theory, we show that when the secondary network is denser than the primary network, both networks can simultaneously achieve the same throughput scaling law as a stand-alone network. Furthermore, the primary network throughput is subject to only a vanishingly fractional loss. Specifically, for the ad hoc and the infrastructure-supported primary models, the primary network achieves sum throughputs of order $n^{1/2}$ and $\max\{n^{1/2},l\}$, respectively. For both primary network models, for any $δ>0$, the secondary network can achieve sum throughput of order $m^{1/2-δ}$ with an arbitrarily small fraction of outage. Thus, almost all secondary source-destination pairs can communicate at a rate of order $m^{-1/2-δ}$.
Node discovery in a networked organization
Venue: arXiv cs.AI 2009
Year: 2009

In this paper, I present a method to solve a node discovery problem in a networked organization. Covert nodes refer to the nodes which are not observable directly. They affect social interactions, but do not appear in the surveillance logs which record the participants of the social interactions. Discovering the covert nodes is defined as identifying the suspicious logs where the covert nodes would appear if the covert nodes became overt. A mathematical model is developed for the maximal likelihood estimation of the network behind the social interactions and for the identification of the suspicious logs. Precision, recall, and F measure characteristics are demonstrated with the dataset generated from a real organization and the computationally synthesized datasets. The performance is close to the theoretical limit for any covert nodes in the networks of any topologies and sizes if the ratio of the number of observation to the number of possible communication patterns is large.
Optimal Power Control over Fading Cognitive Radio Channels by Exploiting Primary User CSI
Venue: arXiv cs.IT 2009
Year: 2009

This paper is concerned with spectrum sharing cognitive radio networks, where a secondary user (SU) or cognitive radio link communicates simultaneously over the same frequency band with an existing primary user (PU) link. It is assumed that the SU transmitter has the perfect channel state information (CSI) on the fading channels from SU transmitter to both PU and SU receivers (as usually assumed in the literature), as well as the fading channel from PU transmitter to PU receiver (a new assumption). With the additional PU CSI, we study the optimal power control for the SU over different fading states to maximize the SU ergodic capacity subject to a new proposed constraint to protect the PU transmission, which limits the maximum ergodic capacity loss of the PU resulted from the SU transmission. It is shown that the proposed SU power-control policy is superior over the conventional policy under the constraint on the maximum tolerable interference power/interperferecne temperature at the PU receiver, in terms of the achievable ergodic capacities of both PU and SU.
Information Theoretic Operating Regimes of Large Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes--bandwidth- and power-limited--have proven indispensable in the design of good communication schemes. In this paper, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point-to-point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes. Our analysis shows that in a given wireless network with arbitrary size, area, power, bandwidth, etc., there are three parameters of importance: the short-distance SNR, the long-distance SNR, and the power path loss exponent of the environment. Depending on these parameters we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is {\em both} power and bandwidth limited. This regime has thus far remained hidden due to the limitations of the existing formulation. Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.
Towards applied theories based on computability logic
Venue: arXiv cs.LO 2009
Year: 2009

Computability logic (CL) (see http://www.cis.upenn.edu/~giorgi/cl.html) is a recently launched program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in it represent computational problems, "truth" means existence of an algorithmic solution, and proofs encode such solutions. Within the line of research devoted to finding axiomatizations for ever more expressive fragments of CL, the present paper introduces a new deductive system CL12 and proves its soundness and completeness with respect to the semantics of CL. Conservatively extending classical predicate calculus and offering considerable additional expressive and deductive power, CL12 presents a reasonable, computationally meaningful, constructive alternative to classical logic as a basis for applied theories. To obtain a model example of such theories, this paper rebuilds the traditional, classical-logic-based Peano arithmetic into a computability-logic-based counterpart. Among the purposes of the present contribution is to provide a starting point for what, as the author wishes to hope, might become a new line of research with a potential of interesting findings -- an exploration of the presumably quite unusual metatheory of CL-based arithmetic and other CL-based applied systems.
The Kleene-Rosser Paradox, The Liar's Paradox & A Fuzzy Logic Programming Paradox Imply SAT is (NOT) NP-complete
Venue: arXiv cs.LO 2009
Year: 2009

After examining the {\bf P} versus {\bf NP} problem against the Kleene-Rosser paradox of the $λ$-calculus [94], it was found that it represents a counter-example to NP-completeness. We prove that it contradicts the proof of Cook's theorem. A logical formalization of the liar's paradox leads to the same result. This formalization of the liar's paradox into a computable form is a 2-valued instance of a fuzzy logic programming paradox discovered in the system of [90]. Three proofs that show that {\bf SAT} is (NOT) NP-complete are presented. The counter-example classes to NP-completeness are also counter-examples to Fagin's theorem [36] and the Immermann-Vardi theorem [89,110], the fundamental results of descriptive complexity. All these results show that {\bf ZF$\not$C} is inconsistent.
Recursive Code Construction for Random Networks
Venue: arXiv cs.IT 2009
Year: 2009

A modification of Koetter-Kschischang codes for random networks is presented (these codes were also studied by Wang et al. in the context of authentication problems). The new codes have higher information rate, while maintaining the same error-correcting capabilities. An efficient error-correcting algorithm is proposed for these codes.
Rate and power allocation under the pairwise distributed source coding constraint
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of rate and power allocation for a sensor network under the pairwise distributed source coding constraint. For noiseless source-terminal channels, we show that the minimum sum rate assignment can be found by finding a minimum weight arborescence in an appropriately defined directed graph. For orthogonal noisy source-terminal channels, the minimum sum power allocation can be found by finding a minimum weight matching forest in a mixed graph. Numerical results are presented for both cases showing that our solutions always outperform previously proposed solutions. The gains are considerable when source correlations are high.
Optimal Beamforming for Two-Way Multi-Antenna Relay Channel with Analogue Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the wireless two-way relay channel (TWRC), where two source nodes, S1 and S2, exchange information through an assisting relay node, R. It is assumed that R receives the sum signal from S1 and S2 in one time-slot, and then amplifies and forwards the received signal to both S1 and S2 in the next time-slot. By applying the principle of analogue network (ANC), each of S1 and S2 cancels the so-called "self-interference" in the received signal from R and then decodes the desired message. Assuming that S1 and S2 are each equipped with a single antenna and R with multi-antennas, this paper analyzes the capacity region of an ANC-based TWRC with linear processing (beamforming) at R. The capacity region contains all the achievable bidirectional rate-pairs of S1 and S2 under the given transmit power constraints at S1, S2, and R. We present the optimal relay beamforming structure as well as an efficient algorithm to compute the optimal beamforming matrix based on convex optimization techniques. Low-complexity suboptimal relay beamforming schemes are also presented, and their achievable rates are compared against the capacity with the optimal scheme.
Relay-Assisted User Scheduling in Wireless Networks with Hybrid-ARQ
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the problem of relay-assisted user scheduling for downlink wireless transmission. The base station or access point employs hybrid automatic-repeat-request (HARQ) with the assistance of a set of fixed relays to serve a set of mobile users. By minimizing a cost function of the queue lengths at the base station and the number of retransmissions of the head-of-line packet for each user, the base station can schedule an appropriate user in each time slot and an appropriate transmitter to serve it. It is shown that a priority-index policy is optimal for a linear cost function with packets arriving according to a Poisson process and for an increasing convex cost function where packets must be drained from the queues at the base station.
Every Computably Enumerable Random Real Is Provably Computably Enumerable Random
Venue: arXiv cs.CC 2009
Year: 2009

We prove that every computably enumerable (c.e.) random real is provable in Peano Arithmetic (PA) to be c.e. random. A major step in the proof is to show that the theorem stating that "a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine" can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem. Our positive result can be contrasted with the case of computable functions, where not every computable function is provably computable in PA, or even more interestingly, with the fact that almost all random finite strings are not provably random in PA. We also prove two negative results: a) there exists a universal machine whose universality cannot be proved in PA, b) there exists a universal machine $U$ such that, based on $U$, PA cannot prove the randomness of its halting probability. The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as a formal proof of this theorem written with the proof assistant Isabelle.
On NFAs Where All States are Final, Initial, or Both
Venue: arXiv cs.CC 2009
Year: 2009

We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.
Cooperative Protocols for Random Access Networks
Venue: arXiv cs.IT 2009
Year: 2009

Cooperative communications have emerged as a significant concept to improve reliability and throughput in wireless systems. On the other hand, WLANs based on random access mechanism have become popular due to ease of deployment and low cost. Since cooperation introduces extra transmissions among the cooperating nodes and therefore increases the number of packet collisions, it is not clear whether there is any benefit from using physical layer cooperation under random access. In this paper, we develop new low complexity cooperative protocols for random access that outperform the conventional non cooperative scheme for a large range of signal-to-noise ratios.
Model-Based Compressive Sensing
Venue: arXiv cs.IT 2009
Year: 2009

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K << N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from M = O(K log(N/K)) measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal models - wavelet trees and block sparsity - into two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M=O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.
Forward Correction and Fountain codes in Delay Tolerant Networks
Venue: arXiv cs.NI 2009
Year: 2009

Delay tolerant Ad-hoc Networks make use of 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 delivery delay, the information that needs to be delivered is replicated in the network. Our objective in this paper is to study replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on fluid approximations, are compared to simulations which validate the model
HEP data analysis using jHepWork and Java
Venue: arXiv cs.CE 2009
Year: 2009

A role of Java in high-energy physics and recent progress in development of a platform-independent data-analysis framework, jHepWork, is discussed. The framework produces professional graphics and has many libraries for data manipulation.
Incoherent dictionaries and the statistical restricted isometry property
Venue: arXiv cs.IT 2009
Year: 2009

In this article we present a statistical version of the Candes-Tao restricted isometry property (SRIP for short) which holds in general for any incoherent dictionary which is a disjoint union of orthonormal bases. In addition, under appropriate normalization, the eigenvalues of the associated Gram matrix fluctuate around 1 according to the Wigner semicircle distribution. The result is then applied to various dictionaries that arise naturally in the setting of finite harmonic analysis, giving, in particular, a better understanding on a remark of Applebaum-Howard-Searle-Calderbank concerning RIP for the Heisenberg dictionary of chirp like functions.
Weyl's Predicative Classical Mathematics as a Logic-Enriched Type Theory
Venue: arXiv cs.LO 2009
Year: 2009

We construct a logic-enriched type theory LTTW that corresponds closely to the predicative system of foundations presented by Hermann Weyl in Das Kontinuum. We formalise many results from that book in LTTW, including Weyl's definition of the cardinality of a set and several results from real analysis, using the proof assistant Plastic that implements the logical framework LF. This case study shows how type theory can be used to represent a non-constructive foundation for mathematics.
The Potluck Problem
Venue: arXiv cs.GT 2009
Year: 2009

This paper proposes the Potluck Problem as a model for the behavior of independent producers and consumers under standard economic assumptions, as a problem of resource allocation in a multi-agent system in which there is no explicit communication among the agents.