OpenRaiser/Intern-Atlas huggingface dataset:
Mining Spatial Gene Expression Data Using Negative Association Rules
Venue: arXiv cs.DB 2010
Year: 2010

Over the years, data mining has attracted most of the attention from the research community. The researchers attempt to develop faster, more scalable algorithms to navigate over the ever increasing volumes of spatial gene expression data in search of meaningful patterns. Association rules are a data mining technique that tries to identify intrinsic patterns in spatial gene expression data. It has been widely used in different applications, a lot of algorithms introduced to discover these rules. However Priori like algorithms has been used to find positive association rules. In contrast to positive rules, negative rules encapsulate relationship between the occurrences of one set of items with absence of the other set of items. In this paper, an algorithm for mining negative association rules from spatial gene expression data is introduced. The algorithm intends to discover the negative association rules which are complementary to the association rules often generated by Priori like algorithm. Our study shows that negative association rules can be discovered efficiently from spatial gene expression data.
Scheduling in Wireless Networks under Uncertainties: A Greedy Primal-Dual Approach
Venue: arXiv cs.IT 2010
Year: 2010

This paper proposes a dynamic primal-dual type algorithm to solve the optimal scheduling problem in wireless networks subject to uncertain parameters, which are generated by stochastic network processes such as random packet arrivals, channel fading, and node mobilities. The algorithm is a generalization of the well-known max-weight scheduling algorithm proposed by Tassiulas et al., where only queue length information is used for computing the schedules when the arrival rates are uncertain. Using the technique of fluid limits, sample path convergence of the algorithm to an arbitrarily close to optimal solution is proved, under the assumption that the Strong Law of Large Numbers (SLLN) applies to the random processes which generate the uncertain parameters. The performance of the algorithm is further verified by simulation results. The method may potentially be applied to other applications where dynamic algorithms for convex problems with uncertain parameters are needed.
Multishot Codes for Network Coding using Rank-Metric Codes
Venue: arXiv cs.IT 2010
Year: 2010

The multiplicative-additive finite-field matrix channel arises as an adequate model for linear network coding systems when links are subject to errors and erasures, and both the network topology and the network code are unknown. In a previous work we proposed a general construction of multishot codes for this channel based on the multilevel coding theory. Herein we apply this construction to the rank-metric space, obtaining multishot rank-metric codes which, by lifting, can be converted to codes for the aforementioned channel. We also adapt well-known encoding and decoding algorithms to the considered situation.
Refined rate of channel polarization
Venue: arXiv cs.IT 2010
Year: 2010

A rate-dependent upper bound of the best achievable block error probability of polar codes with successive-cancellation decoding is derived.
An Extension for Combination of Duty Constraints in Role-Based Access Control
Venue: arXiv cs.CR 2010
Year: 2010

Among access control models, Role Based Access Control (RBAC) is very useful and is used in many computer systems. Static Combination of Duty (SCD) and Dynamic Combination of Duty (DCD) constraints have been introduced recently for this model to handle dependent roles. These roles must be used together and can be considered as a contrary point of conflicting roles. In this paper, we propose several new types of SCD and DCD constraints. Also, we introduce strong dependent roles and define new groups of SCD constraints for these types of roles as SCD with common items and SCD with union items. In addition, we present an extension for SCD constraints in the presence of hierarchy.
Harvesting Collective Intelligence: Temporal Behavior in Yahoo Answers
Venue: arXiv cs.CY 2010
Year: 2010

When harvesting collective intelligence, a user wishes to maximize the accuracy and value of the acquired information without spending too much time collecting it. We empirically study how people behave when facing these conflicting objectives using data from Yahoo Answers, a community driven question-and-answer site. We take two complementary approaches. We first study how users behave when trying to maximize the amount of the acquired information, while minimizing the waiting time. We identify and quantify how question authors at Yahoo Answers trade off the number of answers they receive and the cost of waiting. We find that users are willing to wait more to obtain an additional answer when they have only received a small number of answers; this implies decreasing marginal returns in the amount of collected information. We also estimate the user's utility function from the data. Our second approach focuses on how users assess the qualities of the individual answers without explicitly considering the cost of waiting. We assume that users make a sequence of decisions, deciding to wait for an additional answer as long as the quality of the current answer exceeds some threshold. Under this model, the probability distribution for the number of answers that a question gets is an inverse Gaussian, which is a Zipf-like distribution. We use the data to validate this conclusion.
On Zero-Error Source Coding with Feedback
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of zero error source coding with limited feedback when side information is present at the receiver. First, we derive an achievable rate region for arbitrary joint distributions on the source and the side information. When all source pairs of source and side information symbols are observable with non-zero probability, we show that this characterization gives the entire rate region. Next, we demonstrate a class of sources for which asymptotically zero feedback suffices to achieve zero-error coding at the rate promised by the Slepian-Wolf bound for asymptotically lossless coding. Finally, we illustrate these results with the aid of three simple examples.
Multiple Access Network Information-flow And Correction codes
Venue: arXiv cs.NI 2010
Year: 2010

The network communication scenario where one or more receivers request all the information transmitted by different sources is considered. We introduce distributed polynomial-time network codes in the presence of malicious nodes. Our codes can achieve any point inside the rate region of multiple-source multicast transmission scenarios both in the cases of coherent and non-coherent network coding. For both cases the encoding and decoding algorithm runs in poly(|E|)exp(s) time, where poly(|E|) is a polynomial function of the number of edges |E| in the network and exp(s) is an exponential function of the number of sources s. Our codes are fully distributed and different sources require no knowledge of the data transmitted by their peers. Our codes are "end-to-end", that is, all nodes apart from the sources and the receivers are oblivious to the adversaries present in the network and simply implement random linear network coding.
On the Model Transform in Stochastic Network Calculus
Venue: arXiv cs.PF 2010
Year: 2010

Stochastic network calculus requires special care in the search of proper stochastic traffic arrival models and stochastic service models. Tradeoff must be considered between the feasibility for the analysis of performance bounds, the usefulness of performance bounds, and the ease of their numerical calculation. In theory, transform between different traffic arrival models and transform between different service models are possible. Nevertheless, the impact of the model transform on performance bounds has not been thoroughly investigated. This paper is to investigate the effect of the model transform and to provide practical guidance in the model selection in stochastic network calculus.
Kernel machines with two layers and multiple kernel learning
Venue: arXiv cs.LG 2010
Year: 2010

In this paper, the framework of kernel machines with two layers is introduced, generalizing classical kernel methods. The new learning methodology provide a formal connection between computational architectures with multiple layers and the theme of kernel learning in standard regularization methods. First, a representer theorem for two-layer networks is presented, showing that finite linear combinations of kernels on each layer are optimal architectures whenever the corresponding functions solve suitable variational problems in reproducing kernel Hilbert spaces (RKHS). The input-output map expressed by these architectures turns out to be equivalent to a suitable single-layer kernel machines in which the kernel function is also learned from the data. Recently, the so-called multiple kernel learning methods have attracted considerable attention in the machine learning literature. In this paper, multiple kernel learning methods are shown to be specific cases of kernel machines with two layers in which the second layer is linear. Finally, a simple and effective multiple kernel learning method called RLS2 (regularized least squares with two layers) is introduced, and his performances on several learning problems are extensively analyzed. An open source MATLAB toolbox to train and validate RLS2 models with a Graphic User Interface is available.
Interaction Strictly Improves the Wyner-Ziv Rate-distortion function
Venue: arXiv cs.IT 2010
Year: 2010

In 1985 Kaspi provided a single-letter characterization of the sum-rate-distortion function for a two-way lossy source coding problem in which two terminals send multiple messages back and forth with the goal of reproducing each other's sources. Yet, the question remained whether more messages can strictly improve the sum-rate-distortion function. Viewing the sum-rate as a functional of the distortions and the joint source distribution and leveraging its convex-geometric properties, we construct an example which shows that two messages can strictly improve the one-message (Wyner-Ziv) rate-distortion function. The example also shows that the ratio of the one-message rate to the two-message sum-rate can be arbitrarily large and simultaneously the ratio of the backward rate to the forward rate in the two-message sum-rate can be arbitrarily small.
Grammatical Aspects for Language Descriptions
Venue: arXiv cs.PL 2010
Year: 2010

For the purposes of tool development, computer languages are usually described using context-free grammars with annotations such as semantic actions or pretty-printing instructions. These descriptions are processed by generators which automatically build software, e.g., parsers, pretty-printers and editing support. In many cases the annotations make grammars unreadable, and when generating code for several tools supporting the same language, one usually needs to duplicate the grammar in order to provide different annotations for different generators. We present an approach to describing languages which improves readability of grammars and reduces the duplication. To achieve this we use Aspect-Oriented Programming principles. This approach has been implemented in an open-source tool named Grammatic. We show how it can be used to generate pretty-printers and syntax highlighters.
Pi/2-Angle Yao Graphs are Spanners
Venue: arXiv cs.CG 2010
Year: 2010

We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 8(29+23sqrt(2)). Enroute to this, we also show that the Yao graph Y4 in the Linf metric is a planar spanner with stretch factor 8.
Proof of a Conjecture about Rotation Symmetric Functions
Venue: arXiv cs.CR 2010
Year: 2010

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. In this paper, the Conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed by Cusik and Stănică is proved. As a result, the nonlinearity of such kind of functions is determined.
Asymptotic Learning Curve and Renormalizable Condition in Statistical Learning Theory
Venue: arXiv cs.LG 2010
Year: 2010

Bayes statistics and statistical physics have the common mathematical structure, where the log likelihood function corresponds to the random Hamiltonian. Recently, it was discovered that the asymptotic learning curves in Bayes estimation are subject to a universal law, even if the log likelihood function can not be approximated by any quadratic form. However, it is left unknown what mathematical property ensures such a universal law. In this paper, we define a renormalizable condition of the statistical estimation problem, and show that, under such a condition, the asymptotic learning curves are ensured to be subject to the universal law, even if the true distribution is unrealizable and singular for a statistical model. Also we study a nonrenormalizable case, in which the learning curves have the different asymptotic behaviors from the universal law.
Improved code-based identification scheme
Venue: arXiv cs.CR 2010
Year: 2010

We revisit the 3-pass code-based identification scheme proposed by Stern at Crypto'93, and give a new 5-pass protocol for which the probability of the cheater is 1/2 (instead of 2/3 in the original Stern's proposal). Furthermore, we propose to use quasi-cyclic construction in order to dramatically reduce the size of the public key. The proposed scheme is zero-knowledge and relies on an NP-complete problem coming from coding theory (namely the q-ary Syndrome Decoding problem). Taking into account a recent study of a generalization of Stern's information-set-decoding algorithm for decoding linear codes over arbitrary finite fields Fq we suggest parameters so that the public key be 34Kbits while those of Stern's scheme is about 66Kbits. This provides a very practical identification (and possibly signature) scheme which is mostly attractive for light-weight cryptography
A performance analysis of multi-hop ad hoc networks with adaptive antenna array systems
Venue: arXiv cs.IT 2010
Year: 2010

Based on a stochastic geometry framework, we establish an analysis of the multi-hop spatial reuse aloha protocol (MSR-Aloha) in ad hoc networks. We compare MSR-Aloha to a simple routing strategy, where a node selects the next relay of the treated packet as to be its nearest receiver with a forward progress toward the final destination (NFP). In addition, performance gains achieved by employing adaptive antenna array systems are quantified in this paper. We derive a tight upper bound on the spatial density of progress of MSR-Aloha. Our analytical results demonstrate that the spatial density of progress scales as the square root of the density of users, and the optimal contention density (that maximizes the spatial density of progress) is independent of the density of users. These two facts are consistent with the observations of Baccelli et al., established through an analytical lower bound and through simulations.
Dynamic Resource Allocation in Cognitive Radio Networks: A Convex Optimization Perspective
Venue: arXiv cs.IT 2010
Year: 2010

This article provides an overview of the state-of-art results on communication resource allocation over space, time, and frequency for emerging cognitive radio (CR) wireless networks. Focusing on the interference-power/interference-temperature (IT) constraint approach for CRs to protect primary radio transmissions, many new and challenging problems regarding the design of CR systems are formulated, and some of the corresponding solutions are shown to be obtainable by restructuring some classic results known for traditional (non-CR) wireless networks. It is demonstrated that convex optimization plays an essential role in solving these problems, in a both rigorous and efficient way. Promising research directions on interference management for CR and other related multiuser communication systems are discussed.
Sécurité des systèmes critiques et cybercriminalité : vers une sécurité globale ?
Venue: arXiv cs.CR 2010
Year: 2010

For modern critical systems, it is necessary to consider their ability to avoid catastrophic behavior following fortuitous events such as internal failures in hardware components, environmental disturbances or even involuntary human error in the design and operation, but also non fortuitous events such as malicious attacks. Unfortunately, in French the same word "sécurité" is used to cover two different problematics, what in English is expressed in two different words : safety and security. The interconnected modern information systems, such as rail traffic signalling systems point out the need to deal in an overall way with both safety and security
A finiteness structure on resource terms
Venue: arXiv cs.LO 2010
Year: 2010

In our paper "Uniformity and the Taylor expansion of ordinary lambda-terms" (with Laurent Regnier), we studied a translation of lambda-terms as infinite linear combinations of resource lambda-terms, from a calculus similar to Boudol's lambda-calculus with resources and based on ideas coming from differential linear logic and differential lambda-calculus. The good properties of this translation wrt. beta-reduction were guaranteed by a coherence relation on resource terms: normalization is "linear and stable" (in the sense of the coherence space semantics of linear logic) wrt. this coherence relation. Such coherence properties are lost when one considers non-deterministic or algebraic extensions of the lambda-calculus (the algebraic lambda-calculus is an extension of the lambda-calculus where terms can be linearly combined). We introduce a "finiteness structure" on resource terms which induces a linearly topologized vector space structure on terms and prevents the appearance of infinite coefficients during reduction, in typed settings.
The Recognition of Tolerance and Bounded Tolerance Graphs
Venue: arXiv cs.CC 2010
Year: 2010

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs - namely, the problem of deciding whether a given graph is a tolerance graph - as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs \cite{GolTol04}) since their introduction in 1982 \cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs \cite{MC-Trapezoid}.
Gaussian MIMO Broadcast Channels with Common and Confidential Messages
Venue: arXiv cs.IT 2010
Year: 2010

We study the two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and confidential messages. In this channel, the transmitter sends a common message to both users, and a confidential message to each user which is kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between the capacity region we obtained for the Gaussian MIMO broadcast channel with common and confidential messages and the capacity region of its non-confidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private messages, which is not known completely.
Posynomial Geometric Programming Problems with Multiple Parameters
Venue: arXiv cs.DS 2010
Year: 2010

Geometric programming problem is a powerful tool for solving some special type non-linear programming problems. It has a wide range of applications in optimization and engineering for solving some complex optimization problems. Many applications of geometric programming are on engineering design problems where parameters are estimated using geometric programming. When the parameters in the problems are imprecise, the calculated objective value should be imprecise as well. In this paper we have developed a method to solve geometric programming problems where the exponent of the variables in the objective function, cost coefficients and right hand side are multiple parameters. The equivalent mathematical programming problems are formulated to find their corresponding value of the objective function based on the duality theorem. By applying a variable separable technique the multi-choice mathematical programming problem is transformed into multiple one level geometric programming problem which produces multiple objective values that helps engineers to handle more realistic engineering design problems.
Mathematical Modeling to Study the Dynamics of A Diatomic Molecule N2 in Water
Venue: arXiv cs.CE 2010
Year: 2010

In the present work an attempt has been made to study the dynamics of a diatomic molecule N2 in water. The proposed model consists of Langevin stochastic differential equation whose solution is obtained through Euler's method. The proposed work has been concluded by studying the behavior of statistical parameters like variance in position, variance in velocity and covariance between position and velocity. This model incorporates the important parameters like acceleration, intermolecular force, frictional force and random force.
Farthest-Polygon Voronoi Diagrams
Venue: arXiv cs.CG 2010
Year: 2010

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log^3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region.
Network Codes Resilient to Jamming and Eavesdropping
Venue: arXiv cs.NI 2010
Year: 2010

We consider the problem of communicating information over a network secretly and reliably in the presence of a hidden adversary who can eavesdrop and inject malicious errors. We provide polynomial-time, rate-optimal distributed network codes for this scenario, improving on the rates achievable in previous work. Our main contribution shows that as long as the sum of the adversary's jamming rate Zo and his eavesdropping rate Zi is less than the network capacity C, (i.e., Zo+Zi<C), our codes can communicate (with vanishingly small error probability) a single bit correctly and without leaking any information to the adversary. We then use this to design codes that allow communication at the optimal source rate of C-Zo-Zi, while keeping the communicated message secret from the adversary. Interior nodes are oblivious to the presence of adversaries and perform random linear network coding; only the source and destination need to be tweaked. In proving our results we correct an error in prior work by a subset of the authors in this work.