OpenRaiser/Intern-Atlas huggingface dataset:
Fading Broadcast Channels with State Information at the Receivers
Venue: arXiv cs.IT 2009
Year: 2009

Despite considerable progress on the information-theoretic broadcast channel, the capacity region of fading broadcast channels with channel state known at the receivers but unknown at the transmitter remains unresolved. We address this subject by introducing a layered erasure broadcast channel model in which each component channel has a state that specifies the received signal levels in an instance of a deterministic binary expansion channel. We find the capacity region of this class of broadcast channels. The capacity achieving strategy assigns each signal level to the user that derives the maximum expected rate from that level. The outer bound is based on a channel enhancement that creates a degraded broadcast channel for which the capacity region is known. This same approach is then used to find inner and outer bounds to the capacity region of fading Gaussian broadcast channels. The achievability scheme employs a superposition of binary inputs. For intermittent AWGN channels and for Rayleigh fading channels, the achievable rates are observed to be with 1-2 bits of the outer bound at high SNR. We also prove that the achievable rate region is within 6.386 bits/s/Hz of the capacity region for all fading AWGN broadcast channels.
Ramp: Fast Frequent Itemset Mining with Efficient Bit-Vector Projection Technique
Venue: arXiv cs.DB 2009
Year: 2009

Mining frequent itemset using bit-vector representation approach is very efficient for dense type datasets, but highly inefficient for sparse datasets due to lack of any efficient bit-vector projection technique. In this paper we present a novel efficient bit-vector projection technique, for sparse and dense datasets. To check the efficiency of our bit-vector projection technique, we present a new frequent itemset mining algorithm Ramp (Real Algorithm for Mining Patterns) build upon our bit-vector projection technique. The performance of the Ramp is compared with the current best (all, maximal and closed) frequent itemset mining algorithms on benchmark datasets. Different experimental results on sparse and dense datasets show that mining frequent itemset using Ramp is faster than the current best algorithms, which show the effectiveness of our bit-vector projection idea. We also present a new local maximal frequent itemsets propagation and maximal itemset superset checking approach FastLMFI, build upon our PBR bit-vector projection technique. Our different computational experiments suggest that itemset maximality checking using FastLMFI is fast and efficient than a previous will known progressive focusing approach.
JConstHide: A Framework for Java Source Code Constant Hiding
Venue: arXiv cs.CR 2009
Year: 2009

Software obfuscation or obscuring a software is an approach to defeat the practice of reverse engineering a software for using its functionality illegally in the development of another software. Java applications are more amenable to reverse engineering and re-engineering attacks through methods such as decompilation because Java class files store the program in a semi complied form called byte codes. The existing obfuscation systems obfuscate the Java class files. Obfuscated source code produce obfuscated byte codes and hence two level obfuscation (source code and byte code level) of the program makes it more resilient to reverse engineering attacks . But source code obfuscation is much more difficult due to richer set of programming constructs and the scope of the different variables used in the program and only very little progress has been made on this front. We in this paper are proposing a framework named JConstHide for hiding constants, especially integers in the java source codes, to defeat reverse engineering through decompilation. To the best of our knowledge, no data hiding software are available for java source code constant hiding.
Incentive Compatible Budget Elicitation in Multi-unit Auctions
Venue: arXiv cs.GT 2009
Year: 2009

In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski {\em et al} show that the {\em adaptive clinching} auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show thatthere is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that a randomized modification to the adaptive clinching auction is incentive compatible and Pareto-optimal with private budgets. The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction. Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization.
On using floating-point computations to help an exact linear arithmetic decision procedure
Venue: arXiv cs.LO 2009
Year: 2009

We consider the decision problem for quantifier-free formulas whose atoms are linear inequalities interpreted over the reals or rationals. This problem may be decided using satisfiability modulo theory (SMT), using a mixture of a SAT solver and a simplex-based decision procedure for conjunctions. State-of-the-art SMT solvers use simplex implementations over rational numbers, which perform well for typical problems arising from model-checking and program analysis (sparse inequalities, small coefficients) but are slow for other applications (denser problems, larger coefficients). We propose a simple preprocessing phase that can be adapted on existing SMT solvers and that may be optionally triggered. Despite using floating-point computations, our method is sound and complete - it merely affects efficiency. We implemented the method and provide benchmarks showing that this change brings a naive and slow decision procedure ("textbook simplex" with rational numbers) up to the efficiency of recent SMT solvers, over test cases arising from model-checking, and makes it definitely faster than state-of-the-art SMT solvers on dense examples.
Deconstruction of Infinite Extensive Games using coinduction
Venue: arXiv cs.GT 2009
Year: 2009

Finite objects and more specifically finite games are formalized using induction, whereas infinite objects are formalized using coinduction. In this article, after an introduction to the concept of coinduction, we revisit on infinite (discrete) extensive games the basic notions of game theory. Among others, we introduce a definition of Nash equilibrium and a notion of subgame perfect equilibrium for infinite games. We use those concepts to analyze well known infinite games, like the dollar auction game and the centipede game and we show that human behaviors that are often considered as illogic are perfectly rational, if one admits that human agents reason coinductively.
Internet: Romania vs. Europe
Venue: arXiv cs.OH 2009
Year: 2009

This paper presents various access ways to Internet for home users, both for those who are low consumers (consumed time online or traffic monthly value), or large consumers (unlimited connection). The main purpose of the work consists in making a comparison between the situation of the Internet in Romania and other countries in Europe such as Hungary (more western than Romania, so a little more developed, still an Eastern country comparing to the more developed countries in Western Europe and others well developed such as England, Italy, France, and to those in development such as Poland, and at the periphery of Europe such as Ukraine.
Termination of Linear Programs with Nonlinear Constraints
Venue: arXiv cs.LO 2009
Year: 2009

Tiwari proved that termination of linear programs (loops with linear loop conditions and updates) over the reals is decidable through Jordan forms and eigenvectors computation. Braverman proved that it is also decidable over the integers. In this paper, we consider the termination of loops with polynomial loop conditions and linear updates over the reals and integers. First, we prove that the termination of such loops over the integers is undecidable. Second, with an assumption, we provide an complete algorithm to decide the termination of a class of such programs over the reals. Our method is similar to that of Tiwari in spirit but uses different techniques. Finally, we conjecture that the termination of linear programs with polynomial loop conditions over the reals is undecidable in general by %constructing a loop and reducing the problem to another decision problem related to number theory and ergodic theory, which we guess undecidable.
Collaborative systems and multiagent systems
Venue: arXiv cs.MA 2009
Year: 2009

This paper presents some basic elements regarding the domain of the collaborative systems, a domain of maximum actuality and also the multiagent systems, developed as a result of a sound study on the one-agent systems.
The Multimedia Product - between Design and Information, Design and Utility and Design and Entertainment
Venue: arXiv cs.MM 2009
Year: 2009

The paper investigates the possible coherent and effective alternatives to solve the problems related to the communication needs of any multimedia product. In essence, the presentation will focus on identifying the issues and principles governing three types of the design - in fact, the multimedia design in a broader sense - namely the information design - precisely aiming at ways of organization and presentation of information in a useful and significant form, the graphical user interface design, whose sub-domain consists of the information displayed on the monitor screen and of interactivity between user, computer and electronic devices, meaning, in fact, everything the user sees, touches, hears and all the elements with which he interacts, the graphic design, whose main concern is to create an aesthetic layout arrangement (from the visual and perceptive) information.
Semantic Linkage of Control Systems
Venue: arXiv cs.SE 2009
Year: 2009

Control systems are sets of interconnected hardware and software components which regulate the behaviour of processes. The software of modern control systems rises for some years by requirements regarding the flexibility and functionality. Thus the force of innovation grows on enterprises, since ever newer products in ever shorter time intervals must be made available. Associated hereby is the crucial shortening of the product life cycle, whose effects show up in reduced care of the software and the spares inventory. The aim, the concept presented here and developed in a modeling environment, is proved and ensures a minimum functionality of software components. Replacing software components of a control system verified for functionality by a framework at run-time and if necessary the software conditions will become adapted. Quintessential point of this implementation is the usage of an abstract syntax tree. Within its hierarchical structure meta information is attached to nodes and processed by the framework. With the development of the concept for semantic proving of software components the lifetime of software-based products is increased.
Semantic Social Network Analysis
Venue: arXiv cs.AI 2009
Year: 2009

Social Network Analysis (SNA) tries to understand and exploit the key features of social networks in order to manage their life cycle and predict their evolution. Increasingly popular web 2.0 sites are forming huge social network. Classical methods from social network analysis (SNA) have been applied to such online networks. In this paper, we propose leveraging semantic web technologies to merge and exploit the best features of each domain. We present how to facilitate and enhance the analysis of online social networks, exploiting the power of semantic social network analysis.
The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
Venue: arXiv cs.DS 2009
Year: 2009

We describe a data structure that maintains the number of triangles in a dynamic undirected graph, subject to insertions and deletions of edges and of degree-zero vertices. More generally it can be used to maintain the number of copies of each possible three-vertex subgraph in time O(h) per update, where h is the h-index of the graph, the maximum number such that the graph contains $h$ vertices of degree at least h. We also show how to maintain the h-index itself, and a collection of h high-degree vertices in the graph, in constant time per update. Our data structure has applications in social network analysis using the exponential random graph model (ERGM); its bound of O(h) time per edge is never worse than the Theta(sqrt m) time per edge necessary to list all triangles in a static graph, and is strictly better for graphs obeying a power law degree distribution. In order to better understand the behavior of the h-index statistic and its implications for the performance of our algorithms, we also study the behavior of the h-index on a set of 136 real-world networks.
Refutation of Aslam's Proof that NP = P
Venue: arXiv cs.CC 2009
Year: 2009

Aslam presents an algorithm he claims will count the number of perfect matchings in any incomplete bipartite graph with an algorithm in the function-computing version of NC, which is itself a subset of FP. Counting perfect matchings is known to be #P-complete; therefore if Aslam's algorithm is correct, then NP=P. However, we show that Aslam's algorithm does not correctly count the number of perfect matchings and offer an incomplete bipartite graph as a concrete counter-example.
Representating groups on graphs
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we formulate and study the problem of representing groups on graphs. We show that with respect to polynomial time turing reducibility, both abelian and solvable group representability are all equivalent to graph isomorphism, even when the group is presented as a permutation group via generators. On the other hand, the representability problem for general groups on trees is equivalent to checking, given a group $G$ and $n$, whether a nontrivial homomorphism from $G$ to $S_n$ exists. There does not seem to be a polynomial time algorithm for this problem, in spite of the fact that tree isomorphism has polynomial time algorithm.
Un protocole de routage à basse consommation d'énergie pour les MANETs
Venue: arXiv cs.NI 2009
Year: 2009

Maximizing network lifetime is a very challenging issue in routing protocol design for Mobile Ad-hoc NETworks (MANETs), since mobile nodes are powered by limited-capacity batteries. Furthermore, replacing or recharging batteries is often impossible in critical environments (e.g. battlefields, disaster areas, etc.). Energy consumption was considered for a long time equivalent to bandwidth consumption. However, recent works have shown that "energy" and "bandwidth" are substantially different metrics. Moreover, it was found that traditional routing policies such as "the shortest path" one can have a negative impact on energy consumption balance. Therefore, several new approaches have been proposed addressing energy efficiency explicitly. Our work is related to energy efficient routing for MANETs' problem. The proposed MEA-DSR (Multipath Energy-Aware on Demand Source Routing) protocol is based on a load sharing strategy between mobile nodes in order to maximize network lifetime. To achieve this goal, we used multipath routing; nodes' residual energies and paths length were also considered when making routing decisions. Simulation results have shown the efficiency of the proposed protocol under difficult scenarios characterised by high mobility, high density and important traffic load.
Two-Way Unary Temporal Logic over Trees
Venue: arXiv cs.LO 2009
Year: 2009

We consider a temporal logic EF+F^-1 for unranked, unordered finite trees. The logic has two operators: EFϕ, which says "in some proper descendant ϕholds", and F^-1ϕ, which says "in some proper ancestor ϕholds". We present an algorithm for deciding if a regular language of unranked finite trees can be expressed in EF+F^-1. The algorithm uses a characterization expressed in terms of forest algebras.
Parallel Random Apollonian Networks
Venue: arXiv cs.DM 2009
Year: 2009

We present and study in this paper a simple algorithm that produces so called growing Parallel Random Apollonian Networks (P-RAN) in any dimension d. Analytical derivations show that these networks still exhibit small-word and scale-free characteristics. To characterize further the structure of P-RAN, we introduce new parameters that we refer to as the parallel degree and the parallel coefficient, that determine locally and in average the number of vertices inside the (d+1)-cliques composing the network. We provide analytical derivations for the computation of the degree and parallel degree distributions, parallel and clustering coefficients. We give an upper bound for the average path lengths for P-RAN and finally show that our derivations are in very good agreement with our simulations.
Orientation-Constrained Rectangular Layouts
Venue: arXiv cs.CG 2009
Year: 2009

We construct partitions of rectangles into smaller rectangles from an input consisting of a planar dual graph of the layout together with restrictions on the orientations of edges and junctions of the layout. Such an orientation-constrained layout, if it exists, may be constructed in polynomial time, and all orientation-constrained layouts may be listed in polynomial time per layout.
On the Achievability of Interference Alignment in the K-User Constant MIMO Interference Channel
Venue: arXiv cs.IT 2009
Year: 2009

Interference alignment in the K-user MIMO interference channel with constant channel coefficients is considered. A novel constructive method for finding the interference alignment solution is proposed for the case where the number of transmit antennas equals the number of receive antennas (NT = NR = N), the number of transmitter-receiver pairs equals K = N + 1, and all interference alignment multiplexing gains are one. The core of the method consists of solving an eigenvalue problem that incorporates the channel matrices of all interfering links. This procedure provides insight into the feasibility of signal vector spaces alignment schemes in finite dimensional MIMO interference channels.
Number of Measurements in Sparse Signal Recovery
Venue: arXiv cs.IT 2009
Year: 2009

We analyze the asymptotic performance of sparse signal recovery from noisy measurements. In particular, we generalize some of the existing results for the Gaussian case to subgaussian and other ensembles. An achievable result is presented for the linear sparsity regime. A converse on the number of required measurements in the sub-linear regime is also presented, which cover many of the widely used measurement ensembles. Our converse idea makes use of a correspondence between compressed sensing ideas and compound channels in information theory.
Limits of Learning about a Categorical Latent Variable under Prior Near-Ignorance
Venue: arXiv cs.LG 2009
Year: 2009

In this paper, we consider the coherent theory of (epistemic) uncertainty of Walley, in which beliefs are represented through sets of probability distributions, and we focus on the problem of modeling prior ignorance about a categorical random variable. In this setting, it is a known result that a state of prior ignorance is not compatible with learning. To overcome this problem, another state of beliefs, called \emph{near-ignorance}, has been proposed. Near-ignorance resembles ignorance very closely, by satisfying some principles that can arguably be regarded as necessary in a state of ignorance, and allows learning to take place. What this paper does, is to provide new and substantial evidence that also near-ignorance cannot be really regarded as a way out of the problem of starting statistical inference in conditions of very weak beliefs. The key to this result is focusing on a setting characterized by a variable of interest that is \emph{latent}. We argue that such a setting is by far the most common case in practice, and we provide, for the case of categorical latent variables (and general \emph{manifest} variables) a condition that, if satisfied, prevents learning to take place under prior near-ignorance. This condition is shown to be easily satisfied even in the most common statistical problems. We regard these results as a strong form of evidence against the possibility to adopt a condition of prior near-ignorance in real statistical problems.
Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
Venue: arXiv cs.DS 2009
Year: 2009

This paper studies a discrepancy-sensitive approach to dynamic fractional cascading. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the plane, which in turn leads to an efficient dynamic data structure that can answer queries for nearest neighbors using any Minkowski metric. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the plane, which in turn leads to an efficient dynamic data structure that can answer queries for nearest neighbors using any Minkowski metric.
Belief-Propagation Decoding of Lattices Using Gaussian Mixtures
Venue: arXiv cs.IT 2009
Year: 2009

A belief-propagation decoder for low-density lattice codes is given which represents messages explicitly as a mixture of Gaussians functions. The key component is an algorithm for approximating a mixture of several Gaussians with another mixture with a smaller number of Gaussians. This Gaussian mixture reduction algorithm iteratively reduces the number of Gaussians by minimizing the distance between the original mixture and an approximation with one fewer Gaussians. Error rates and noise thresholds of this decoder are compared with those for the previously-proposed decoder which discretely quantizes the messages. The error rates are indistinguishable for dimension 1000 and 10000 lattices, and the Gaussian-mixture decoder has a 0.2 dB loss for dimension 100 lattices. The Gaussian-mixture decoder has a loss of about 0.03 dB in the noise threshold, which is evaluated via Monte Carlo density evolution. Further, the Gaussian-mixture decoder uses far less storage for the messages.
Simulating reachability using first-order logic with applications to verification of linked data structures
Venue: arXiv cs.LO 2009
Year: 2009

This paper shows how to harness existing theorem provers for first-order logic to automatically verify safety properties of imperative programs that perform dynamic storage allocation and destructive updating of pointer-valued structure fields. One of the main obstacles is specifying and proving the (absence) of reachability properties among dynamically allocated cells. The main technical contributions are methods for simulating reachability in a conservative way using first-order formulas--the formulas describe a superset of the set of program states that would be specified if one had a precise way to express reachability. These methods are employed for semi-automatic program verification (i.e., using programmer-supplied loop invariants) on programs such as mark-and-sweep garbage collection and destructive reversal of a singly linked list. (The mark-and-sweep example has been previously reported as being beyond the capabilities of ESC/Java.)