OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Objective Genetic Programming Projection Pursuit for Exploratory Data Modeling
Venue: arXiv cs.LG 2010
Year: 2010

For classification problems, feature extraction is a crucial process which aims to find a suitable data representation that increases the performance of the machine learning algorithm. According to the curse of dimensionality theorem, the number of samples needed for a classification task increases exponentially as the number of dimensions (variables, features) increases. On the other hand, it is costly to collect, store and process data. Moreover, irrelevant and redundant features might hinder classifier performance. In exploratory analysis settings, high dimensionality prevents the users from exploring the data visually. Feature extraction is a two-step process: feature construction and feature selection. Feature construction creates new features based on the original features and feature selection is the process of selecting the best features as in filter, wrapper and embedded methods. In this work, we focus on feature construction methods that aim to decrease data dimensionality for visualization tasks. Various linear (such as principal components analysis (PCA), multiple discriminants analysis (MDA), exploratory projection pursuit) and non-linear (such as multidimensional scaling (MDS), manifold learning, kernel PCA/LDA, evolutionary constructive induction) techniques have been proposed for dimensionality reduction. Our algorithm is an adaptive feature extraction method which consists of evolutionary constructive induction for feature construction and a hybrid filter/wrapper method for feature selection.
Detecting Simultaneous Integer Relations for Several Real Vectors
Venue: arXiv cs.SC 2010
Year: 2010

An algorithm which either finds an nonzero integer vector ${\mathbf m}$ for given $t$ real $n$-dimensional vectors ${\mathbf x}_1,...,{\mathbf x}_t$ such that ${\mathbf x}_i^T{\mathbf m}=0$ or proves that no such integer vector with norm less than a given bound exists is presented in this paper. The cost of the algorithm is at most ${\mathcal O}(n^4 + n^3 \log λ(X))$ exact arithmetic operations in dimension $n$ and the least Euclidean norm $λ(X)$ of such integer vectors. It matches the best complexity upper bound known for this problem. Experimental data show that the algorithm is better than an already existing algorithm in the literature. In application, the algorithm is used to get a complete method for finding the minimal polynomial of an unknown complex algebraic number from its approximation, which runs even faster than the corresponding \emph{Maple} built-in function.
Relay Strategies Based on Cross-Determinism for the Broadcast Relay Channel
Venue: arXiv cs.IT 2010
Year: 2010

We consider a two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with a common multiple-antenna relay, and a shared digital (noiseless) link between the relay and the two destinations. For this channel, this paper introduces an asymptotically sum-capacity-achieving quantize-and-forward (QF) relay strategy. Our technique to design an asymptotically optimal relay quantizer is based on identifying a cross-deterministic relation between the relay observation, the source signal, and the destination observation. In a relay channel, an approximate cross deterministic relation corresponds to an approximately deterministic relation, where the relay observation is to some extent a deterministic function of the source and destination signals. We show that cross determinism can serve as a measure for quantization penalty. By identifying an analogy between a deterministic broadcast relay channel and a Gaussian MIMO relay channel, we propose a three-stage dirty paper coding strategy, along with receiver beamforming and quantization at the relay, to asymptotically achieve an extended achievable rate region for the MIMO broadcast channel with a common multiple-antenna relay.
On Finding Frequent Patterns in Event Sequences
Venue: arXiv cs.DS 2010
Year: 2010

Given a directed acyclic graph with labeled vertices, we consider the problem of finding the most common label sequences ("traces") among all paths in the graph (of some maximum length m). Since the number of paths can be huge, we propose novel algorithms whose time complexity depends only on the size of the graph, and on the frequency epsilon of the most frequent traces. In addition, we apply techniques from streaming algorithms to achieve space usage that depends only on epsilon, and not on the number of distinct traces. The abstract problem considered models a variety of tasks concerning finding frequent patterns in event sequences. Our motivation comes from working with a data set of 2 million RFID readings from baggage trolleys at Copenhagen Airport. The question of finding frequent passenger movement patterns is mapped to the above problem. We report on experimental findings for this data set.
Lattice Problems and Their Reductions(Russian)
Venue: arXiv cs.CR 2010
Year: 2010

This article presets a review of lattice problems. Paper contains the main eighteen problems with their reductions and referents to his cryptography application. As an example of reduction, we detail analyze connection between SVP and CVP. Moreover, we give an Ajtai theorem and demonstrate its role in lattice based cryptography.
Learning Taxonomy for Text Segmentation by Formal Concept Analysis
Venue: arXiv cs.CL 2010
Year: 2010

In this paper the problems of deriving a taxonomy from a text and concept-oriented text segmentation are approached. Formal Concept Analysis (FCA) method is applied to solve both of these linguistic problems. The proposed segmentation method offers a conceptual view for text segmentation, using a context-driven clustering of sentences. The Concept-oriented Clustering Segmentation algorithm (COCS) is based on k-means linear clustering of the sentences. Experimental results obtained using COCS algorithm are presented.
Capacity of 1-to-K Broadcast Packet Erasure Channels with Channel Output Feedback (Full Version)
Venue: arXiv cs.IT 2010
Year: 2010

This paper focuses on the 1-to-K broadcast packet erasure channel (PEC), which is a generalization of the broadcast binary erasure channel from the binary symbol to that of arbitrary finite fields GF(q) with sufficiently large q. We consider the setting in which the source node has instant feedback of the channel outputs of the K receivers after each transmission. The capacity region of the 1-to-K PEC with COF was previously known only for the case K=2. Such a setting directly models network coded packet transmission in the downlink direction with integrated feedback mechanisms (such as Automatic Repeat reQuest (ARQ)). The main results of this paper are: (i) The capacity region for general 1-to-3 broadcast PECs, and (ii) The capacity region for two types of 1-to-$K$ broadcast PECs: the symmetric PECs, and the spatially independent PECs with one-sided fairness constraints. This paper also develops (iii) A pair of outer and inner bounds of the capacity region for arbitrary 1-to-K broadcast PECs, which can be easily evaluated by any linear programming solver. The proposed inner bound is proven by a new class of intersession network coding schemes, termed the packet evolution schemes, which is based on the concept of code alignment in GF(q) that is in parallel with the interference alignment techniques for the Euclidean space. Extensive numerical experiments show that the outer and inner bounds meet for almost all broadcast PECs encountered in practical scenarios and thus effectively bracket the capacity of general 1-to-K broadcast PECs with COF.
Conservation Law of Utility and Equilibria in Non-Zero Sum Games
Venue: arXiv cs.GT 2010
Year: 2010

This short note demonstrates how one can define a transformation of a non-zero sum game into a zero sum, so that the optimal mixed strategy achieving equilibrium always exists. The transformation is equivalent to introduction of a passive player into a game (a player with a singleton set of pure strategies), whose payoff depends on the actions of the active players, and it is justified by the law of conservation of utility in a game. In a transformed game, each participant plays against all other players, including the passive player. The advantage of this approach is that the transformed game is zero-sum and has an equilibrium solution. The optimal strategy and the value of the new game, however, can be different from strategies that are rational in the original game. We demonstrate the principle using the Prisoner's Dilemma example.
Flat Zipper-Unfolding Pairs for Platonic Solids
Venue: arXiv cs.CG 2010
Year: 2010

We show that four of the five Platonic solids' surfaces may be cut open with a Hamiltonian path along edges and unfolded to a polygonal net each of which can "zipper-refold" to a flat doubly covered parallelogram, forming a rather compact representation of the surface. Thus these regular polyhedra have particular flat "zipper pairs." No such zipper pair exists for a dodecahedron, whose Hamiltonian unfoldings are "zip-rigid." This report is primarily an inventory of the possibilities, and raises more questions than it answers.
Surface Curvature Effects on Reflectance from Translucent Materials
Venue: arXiv cs.GR 2010
Year: 2010

Most of the physically based techniques for rendering translucent objects use the diffusion theory of light scattering in turbid media. The widely used dipole diffusion model (Jensen et al. 2001) applies the diffusion-theory formula derived for a planar interface to objects of arbitrary shapes. This paper presents first results of our investigation of how surface curvature affects the diffuse reflectance from translucent materials.
Privacy-Compatibility For General Utility Metrics
Venue: arXiv cs.CR 2010
Year: 2010

In this note, we present a complete characterization of the utility metrics that allow for non-trivial differential privacy guarantees.
Optimum Power and Rate Allocation for Coded V-BLAST: Average Optimization
Venue: arXiv cs.IT 2010
Year: 2010

An analytical framework for performance analysis and optimization of coded V-BLAST is developed. Average power and/or rate allocations to minimize the outage probability as well as their robustness and dual problems are investigated. Compact, closed-form expressions for the optimum allocations and corresponding system performance are given. The uniform power allocation is shown to be near optimum in the low outage regime in combination with the optimum rate allocation. The average rate allocation provides the largest performance improvement (extra diversity gain), and the average power allocation offers a modest SNR gain limited by the number of transmit antennas but does not increase the diversity gain. The dual problems are shown to have the same solutions as the primal ones. All these allocation strategies are shown to be robust. The reported results also apply to coded multiuser detection and channel equalization systems relying on successive interference cancelation.
Contract Aware Components, 10 years after
Venue: arXiv cs.SE 2010
Year: 2010

The notion of contract aware components has been published roughly ten years ago and is now becoming mainstream in several fields where the usage of software components is seen as critical. The goal of this paper is to survey domains such as Embedded Systems or Service Oriented Architecture where the notion of contract aware components has been influential. For each of these domains we briefly describe what has been done with this idea and we discuss the remaining challenges.
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time \tilde{O}(mn^{1/3} ε^{-11/3}). A dual version of our approach computes a (1+ε)-approximately minimum s-t cut in time \tilde{O}(m+n^{4/3}\eps^{-8/3}), which is the fastest known algorithm for this problem as well. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time \tilde{O}(m\sqrt{n}ε^{-1}), and approximately minimum s-t cuts in time \tilde{O}(m+n^{3/2}ε^{-3}).
Simplification of cross-field topology
Venue: arXiv cs.CG 2010
Year: 2010

We present an innovative algorithm that simplifies the topology of a cross-field. Our algorithm works through macro-operations that allow us editing the graph of separatrices, which is extracted from a cross-field, while maintaining it topologically consistent. We present preliminary results of our implementation.
Interval total colorings of graphs
Venue: arXiv cs.DM 2010
Year: 2010

A total coloring of a graph $G$ is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An \emph{interval total $t$-coloring} of a graph $G$ is a total coloring of $G$ with colors $1,2,\...,t$ such that at least one vertex or edge of $G$ is colored by $i$, $i=1,2,\...,t$, and the edges incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$ consecutive colors, where $d_{G}(v)$ is the degree of the vertex $v$ in $G$. In this paper we investigate some properties of interval total colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some classes of graphs.
Parallel Sorted Neighborhood Blocking with MapReduce
Venue: arXiv cs.DC 2010
Year: 2010

Cloud infrastructures enable the efficient parallel execution of data-intensive tasks such as entity resolution on large datasets. We investigate challenges and possible solutions of using the MapReduce programming model for parallel entity resolution. In particular, we propose and evaluate two MapReduce-based implementations for Sorted Neighborhood blocking that either use multiple MapReduce jobs or apply a tailored data replication.
The Digital Signature Scheme MQQ-SIG
Venue: arXiv cs.CR 2010
Year: 2010

This document contains the Intellectual Property Statement and the technical description of the MQQ-SIG - a new public key digital signature scheme. The complete scientific publication covering the design rationale and the security analysis will be given in a separate publication. MQQ-SIG consists of $n - \frac{n}{4}$ quadratic polynomials with $n$ Boolean variables where n=160, 196, 224 or 256.
Introduction to the iDian
Venue: arXiv cs.AI 2010
Year: 2010

The iDian (previously named as the Operation Agent System) is a framework designed to enable computer users to operate software in natural language. Distinct from current speech-recognition systems, our solution supports format-free combinations of orders, and is open to both developers and customers. We used a multi-layer structure to build the entire framework, approached rule-based natural language processing, and implemented demos narrowing down to Windows, text-editing and a few other applications. This essay will firstly give an overview of the entire system, and then scrutinize the functions and structure of the system, and finally discuss the prospective de-velopment, esp. on-line interaction functions.
QoS-Aware Joint Policies in Cognitive Radio Networks
Venue: arXiv cs.GT 2010
Year: 2010

One of the most challenging problems in Opportunistic Spectrum Access (OSA) is to design channel sensing-based protocol in multi secondary users (SUs) network. Quality of Service (QoS) requirements for SUs have significant implications on this protocol design. In this paper, we propose a new method to find joint policies for SUs which not only guarantees QoS requirements but also maximizes network throughput. We use Decentralized Partially Observable Markov Decision Process (Dec-POMDP) to formulate interactions between SUs. Meanwhile, a tractable approach for Dec-POMDP is utilized to extract sub-optimum joint policies for large horizons. Among these policies, the joint policy which guarantees QoS requirements is selected as the joint sensing strategy for SUs. To show the efficiency of the proposed method, we consider two SUs trying to access two-channel primary users (PUs) network modeled by discrete Markov chains. Simulations demonstrate three interesting findings: 1- Optimum joint policies for large horizons can be obtained using the proposed method. 2- There exists a joint policy for the assumed QoS constraints. 3- Our method outperforms other related works in terms of network throughput.
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Venue: arXiv cs.LG 2010
Year: 2010

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in $\R^n \times \{-1,1\}.$ We prove that for any constants $d\geq 1, \eps > 0$, {itemize} Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a degree-$d$ PTF that is consistent with a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a degree-$d$ PTF that is consistent with a $1-\eps$ fraction of the examples. It is $\NP$-hard to find a degree-2 PTF that is consistent with a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a halfspace (degree-1 PTF) that is consistent with a $1 - \eps$ fraction of the examples. {itemize} These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-$d$ PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e. degree-1 PTFs) under arbitrary distributions.
High-Throughput Random Access via Codes on Graphs
Venue: arXiv cs.IT 2010
Year: 2010

Recently, contention resolution diversity slotted ALOHA (CRDSA) has been introduced as a simple but effective improvement to slotted ALOHA. It relies on MAC burst repetitions and on interference cancellation to increase the normalized throughput of a classic slotted ALOHA access scheme. CRDSA allows achieving a larger throughput than slotted ALOHA, at the price of an increased average transmitted power. A way to trade-off the increment of the average transmitted power and the improvement of the throughput is presented in this paper. Specifically, it is proposed to divide each MAC burst in k sub-bursts, and to encode them via a (n,k) erasure correcting code. The n encoded sub-bursts are transmitted over the MAC channel, according to specific time/frequency-hopping patterns. Whenever n-e>=k sub-bursts (of the same burst) are received without collisions, erasure decoding allows recovering the remaining e sub-bursts (which were lost due to collisions). An interference cancellation process can then take place, removing in e slots the interference caused by the e recovered sub-bursts, possibly allowing the correct decoding of sub-bursts related to other bursts. The process is thus iterated as for the CRDSA case.
The set of realizations of a max-plus linear sequence is semi-polyhedral
Venue: arXiv cs.DS 2010
Year: 2010

We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.
Game Theoretical Power Control for Open-Loop Overlaid Network MIMO Systems with Partial Cooperation
Venue: arXiv cs.IT 2010
Year: 2010

Network MIMO is considered to be a key solution for the next generation wireless systems in breaking the interference bottleneck in cellular systems. In the MIMO systems, open-loop transmission scheme is used to support mobile stations (MSs) with high mobilities because the base stations (BSs) do not need to track the fast varying channel fading. In this paper, we consider an open-loop network MIMO system with $K$ BSs serving K private MSs and $M^c$ common MS based on a novel partial cooperation overlaying scheme. Exploiting the heterogeneous path gains between the private MSs and the common MSs, each of the $K$ BSs serves a private MS non-cooperatively and the $K$ BSs also serve the $M^c$ common MSs cooperatively. The proposed scheme does not require closed loop instantaneous channel state information feedback, which is highly desirable for high mobility users. Furthermore, we formulate the long-term distributive power allocation problem between the private MSs and the common MSs at each of the $K$ BSs using a partial cooperative game. We show that the long-term power allocation game has a unique Nash Equilibrium (NE) but standard best response update may not always converge to the NE. As a result, we propose a low-complexity distributive long-term power allocation algorithm which only relies on the local long-term channel statistics and has provable convergence property. Through numerical simulations, we show that the proposed open-loop SDMA scheme with long-term distributive power allocation can achieve significant performance advantages over the other reference baseline schemes.
A New Non Linear, Time Stamped & Feed Back Model Based Encryption Mechanism with Acknowledgement Support
Venue: arXiv cs.CR 2010
Year: 2010

In this work a model is going to be used which develops data distributed over a identified value which is used as nonce (IV). The model considers an equilibrium equation which is a function of non linear relationships, time variant and nonce variant values and takes the feed back of earlier round as input to the present round. The process is repeated for different timings which are used as time stamps in the encryption mechanism. Thus this model generates a distributed sequence which is used as sub key. This model supports very important parameters in symmetric data encryption schemes like non linear relationships between different values used in the model, variable key length, timeliness of encryption mechanism and also acknowledgement between the participating parties. It also supports feed back mode which provides necessary strength against crypto analysis.