OpenRaiser/Intern-Atlas huggingface dataset:
Market Equilibrium with Transaction Costs
Venue: arXiv cs.GT 2010
Year: 2010

Identical products being sold at different prices in different locations is a common phenomenon. Price differences might occur due to various reasons such as shipping costs, trade restrictions and price discrimination. To model such scenarios, we supplement the classical Fisher model of a market by introducing {\em transaction costs}. For every buyer $i$ and every good $j$, there is a transaction cost of $\cij$; if the price of good $j$ is $p_j$, then the cost to the buyer $i$ {\em per unit} of $j$ is $p_j + \cij$. This allows the same good to be sold at different (effective) prices to different buyers. We provide a combinatorial algorithm that computes $ε$-approximate equilibrium prices and allocations in $O\left(\frac{1}ε(n+\log{m})mn\log(B/ε)\right)$ operations - where $m$ is the number goods, $n$ is the number of buyers and $B$ is the sum of the budgets of all the buyers.
Stable Feature Selection for Biomarker Discovery
Venue: arXiv cs.CE 2010
Year: 2010

Feature selection techniques have been used as the workhorse in biomarker discovery applications for a long time. Surprisingly, the stability of feature selection with respect to sampling variations has long been under-considered. It is only until recently that this issue has received more and more attention. In this article, we review existing stable feature selection methods for biomarker discovery using a generic hierarchal framework. We have two objectives: (1) providing an overview on this new yet fast growing topic for a convenient reference; (2) categorizing existing methods under an expandable framework for future research and development.
An Empirical Evaluation of Four Algorithms for Multi-Class Classification: Mart, ABC-Mart, Robust LogitBoost, and ABC-LogitBoost
Venue: arXiv cs.LG 2010
Year: 2010

This empirical study is mainly devoted to comparing four tree-based boosting algorithms: mart, abc-mart, robust logitboost, and abc-logitboost, for multi-class classification on a variety of publicly available datasets. Some of those datasets have been thoroughly tested in prior studies using a broad range of classification algorithms including SVM, neural nets, and deep learning. In terms of the empirical classification errors, our experiment results demonstrate: 1. Abc-mart considerably improves mart. 2. Abc-logitboost considerably improves (robust) logitboost. 3. Robust) logitboost} considerably improves mart on most datasets. 4. Abc-logitboost considerably improves abc-mart on most datasets. 5. These four boosting algorithms (especially abc-logitboost) outperform SVM on many datasets. 6. Compared to the best deep learning methods, these four boosting algorithms (especially abc-logitboost) are competitive.
Process Algebra as Abstract Data Types
Venue: arXiv cs.PL 2010
Year: 2010

In this paper we introduced an algebraic semantics for process algebra in form of abstract data types. For that purpose, we developed a particular type of algebra, the seed algebra, which describes exactly the behavior of a process within a labeled transition system. We have shown the possibility of characterizing the bisimulation of two processes with the isomorphism of their corresponding seed algebras. We pointed out that the traditional concept of isomorphism of algebra does not apply here, because there is even no one-one correspondence between the elements of two seed algebras. The lack of this one-one correspondence comes from the non-deterministic choice of transitions of a process. We introduce a technique of hidden operations to mask unwanted details of elements of a seed algebra, which only reflect non-determinism or other implicit control mechanism of process transition. Elements of a seed algebra are considered as indistinguishable if they show the same behavior after these unwanted details are masked. Each class of indistinguishable elements is called a non-hidden closure. We proved that bisimulation of two processes is equivalent to isomorphism of non-hidden closures of two seed algebras representing these two processes. We call this kind of isomorphism a deep isomorphism. We get different models of seed algebra by specifying different axiom systems for the same signature. Each model corresponds to a different kind of bisimulation. By proving the relations between these models we also established relations between 10 different bisimulations, which form a acyclic directed graph.
Measuring Latent Causal Structure
Venue: arXiv cs.LG 2010
Year: 2010

Discovering latent representations of the observed world has become increasingly more relevant in data analysis. Much of the effort concentrates on building latent variables which can be used in prediction problems, such as classification and regression. A related goal of learning latent structure from data is that of identifying which hidden common causes generate the observations, such as in applications that require predicting the effect of policies. This will be the main problem tackled in our contribution: given a dataset of indicators assumed to be generated by unknown and unmeasured common causes, we wish to discover which hidden common causes are those, and how they generate our data. This is possible under the assumption that observed variables are linear functions of the latent causes with additive noise. Previous results in the literature present solutions for the case where each observed variable is a noisy function of a single latent variable. We show how to extend the existing results for some cases where observed variables measure more than one latent variable.
Matrix Extension with Symmetry and Its Application to Filter Banks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we completely solve the matrix extension problem with symmetry and provide a step-by-step algorithm to construct such a desired matrix $\mathsf{P}_e$ from a given matrix $\mathsf{P}$. Furthermore, using a cascade structure, we obtain a complete representation of any $r\times s$ paraunitary matrix $\mathsf{P}$ having compatible symmetry, which in turn leads to an algorithm for deriving a desired matrix $\mathsf{P}_e$ from a given matrix $\mathsf{P}$. Matrix extension plays an important role in many areas such as electronic engineering, system sciences, applied mathematics, and pure mathematics. As an application of our general results on matrix extension with symmetry, we obtain a satisfactory algorithm for constructing symmetric paraunitary filter banks and symmetric orthonormal multiwavelets by deriving high-pass filters with symmetry from any given low-pass filters with symmetry. Several examples are provided to illustrate the proposed algorithms and results in this paper.
Joint Scheduling and ARQ for MU-MIMO Downlink in the Presence of Inter-Cell Interference
Venue: arXiv cs.IT 2010
Year: 2010

User scheduling and multiuser multi-antenna (MU-MIMO) transmission are at the core of high rate data-oriented downlink schemes of the next-generation of cellular systems (e.g., LTE-Advanced). Scheduling selects groups of users according to their channels vector directions and SINR levels. However, when scheduling is applied independently in each cell, the inter-cell interference (ICI) power at each user receiver is not known in advance since it changes at each new scheduling slot depending on the scheduling decisions of all interfering base stations. In order to cope with this uncertainty, we consider the joint operation of scheduling, MU-MIMO beamforming and Automatic Repeat reQuest (ARQ). We develop a game-theoretic framework for this problem and build on stochastic optimization techniques in order to find optimal scheduling and ARQ schemes. Particularizing our framework to the case of "outage service rates", we obtain a scheme based on adaptive variable-rate coding at the physical layer, combined with ARQ at the Logical Link Control (ARQ-LLC). Then, we present a novel scheme based on incremental redundancy Hybrid ARQ (HARQ) that is able to achieve a throughput performance arbitrarily close to the "genie-aided service rates", with no need for a genie that provides non-causally the ICI power levels. The novel HARQ scheme is both easier to implement and superior in performance with respect to the conventional combination of adaptive variable-rate coding and ARQ-LLC.
Characterizing Internet Worm Infection Structure
Venue: arXiv cs.CR 2010
Year: 2010

Internet worm infection continues to be one of top security threats and has been widely used by botnets to recruit new bots. In this work, we attempt to quantify the infection ability of individual hosts and reveal the key characteristics of the underlying topology formed by worm infection, i.e., the number of children and the generation of the worm infection family tree. Specifically, we first apply probabilistic modeling methods and a sequential growth model to analyze the infection tree of a wide class of worms. We analytically and empirically find that the number of children has asymptotically a geometric distribution with parameter 0.5. As a result, on average half of infected hosts never compromise any vulnerable host, over 98% of infected hosts have no more than five children, and a small portion of infected hosts have a large number of children. We also discover that the generation follows closely a Poisson distribution and the average path length of the worm infection family tree increases approximately logarithmically with the total number of infected hosts. Next, we empirically study the infection structure of localized-scanning worms and surprisingly find that most of the above observations also apply to localized-scanning worms. Finally, we apply our findings to develop bot detection methods and study potential countermeasures for a botnet (e.g., Conficker C) that uses scan-based peer discovery to form a P2P-based botnet. Specifically, we demonstrate that targeted detection that focuses on the nodes with the largest number of children is an efficient way to expose bots. For example, our simulation shows that when 3.125% nodes are examined, targeted detection can reveal 22.36% bots. However, we also point out that future botnets may limit the maximum number of children to weaken targeted detection, without greatly slowing down the speed of worm infection.
Construction of wiretap codes from ordinary channel codes
Venue: arXiv cs.IT 2010
Year: 2010

From an arbitrary given channel code over a discrete or Gaussian memoryless channel, we construct a wiretap code with the strong security. Our construction can achieve the wiretap capacity under mild assumptions. The key tool is the new privacy amplification theorem bounding the eavesdropped information in terms of the Gallager function.
Il rapporto tra ICT e PMI italiane e le problematiche economico-organizzative dell'OS
Venue: arXiv cs.CY 2010
Year: 2010

This technical report summarizes the preliminary findings of a project that has been developed in 2007 by an Italian company (Datanet, based in Siracusa, Italy) togheter with two Italian research institutions: Universita' degli Studi di Milano and Universita' Bocconi. The main aim of the OS4E (Open Source for Enterprises) project, has been to investigate if and how open source solutions could be profitabily and effectively exploited by an IT company based in the South of Italy, whose core business is IT systems integration and which operates in the market of Italian SMEs (Small and Medium Enterprises). Beside this goal, the project also aimed at developing effective tools and methodologies to support decision making processes while evaluating different alternative software applications based on OSS (open source software).
Coded OFDM by Unique Word Prefix
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we propose a novel transmit signal structure and an adjusted and optimized receiver for OFDM (orthogonal frequency division multiplexing). Instead of the conventional cyclic prefix we use a deterministic sequence, which we call unique word (UW), as guard interval. We show how unique words, which are already well investigated for single carrier systems with frequency domain equalization (SC/FDE), can also be introduced in OFDM symbols. Since unique words represent known sequences, they can advantageously be used for synchronization and channel estimation purposes. Furthermore, the proposed approach introduces a complex number Reed-Solomon (RS-) code structure within the sequence of subcarriers. This allows for RS-decoding or to apply a highly efficient Wiener smoother succeeding a zero forcing stage at the receiver. We present simulation results in an indoor multipath environment to highlight the advantageous properties of the proposed scheme.
On the List-Decodability of Random Linear Codes
Venue: arXiv cs.IT 2010
Year: 2010

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $ε> 0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-ε)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/ε)$ codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of $O(1/ε)$ suffices to have rate within $ε$ of the "capacity" $1-H_q(p)$. Our result matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of $q^{O(1/ε)}$. The main technical ingredient in our proof is a strong upper bound on the probability that $\ell$ random vectors chosen from a Hamming ball centered at the origin have too many (more than $Θ(\ell)$) vectors from their linear span also belong to the ball.
Soft Decision Decoding of the Orthogonal Complex MIMO Codes for Three and Four Transmit Antennas
Venue: arXiv cs.IT 2010
Year: 2010

Orthogonality is a much desired property for MIMO coding. It enables symbol-wise decoding, where the errors in other symbol estimates do not affect the result, thus providing an optimality that is worth pursuing. Another beneficial property is a low complexity soft decision decoder, which for orthogonal complex MIMO codes is known for two transmit (Tx) antennas i.e. for the Alamouti code. We propose novel soft decision decoders for the orthogonal complex MIMO codes on three and four Tx antennas and extend the old result of maximal ratio combining (MRC) to cover all orthogonal codes up to four Tx antennas. As a rule, a sophisticated transmission scheme encompasses forward error correction (FEC) coding, and its performance is measured at the FEC decoder instead of at the MIMO decoder. We introduce the receiver structure that delivers the MIMO decoder's soft decisions to the demodulator, which in turn cranks out the logarithm of likelihood ratio (LLR) of each bit and delivers them to the FEC decoder. This makes a significant improvement on the receiver, where a maximum likelihood (ML) MIMO decoder makes hard decisions at a too early stage. Further, the additional gain is achieved with stunningly low complexity.
Augmented Lattice Reduction for MIMO decoding
Venue: arXiv cs.IT 2010
Year: 2010

Lattice reduction algorithms, such as the LLL algorithm, have been proposed as preprocessing tools in order to enhance the performance of suboptimal receivers in MIMO communications. In this paper we introduce a new kind of lattice reduction-aided decoding technique, called augmented lattice reduction, which recovers the transmitted vector directly from the change of basis matrix, and therefore doesn't entail the computation of the pseudo-inverse of the channel matrix or its QR decomposition. We prove that augmented lattice reduction attains the maximum receive diversity order of the channel; simulation results evidence that it significantly outperforms LLL-SIC detection without entailing any additional complexity. A theoretical bound on the complexity is also derived.
On the Pseudocodeword Redundancy
Venue: arXiv cs.IT 2010
Year: 2010

We define the AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance. We show that most codes do not have a finite pseudocodeword redundancy. We also provide bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs.
Designing a Truly Integrated (Onsite and Online) Conference: Concept, Processes, Solutions
Venue: arXiv cs.MM 2010
Year: 2010

Web conferencing tools have entered the mainstream of business applications. Using web conferencing for IEEE conferences has a good potential of adding value to both organizers and participants. Authors propose a concept of Truly Integrated Conference (TIC) according to which a multi-point worldwide-distributed network of conference online authors/participants will enhance the standard (centralized) IEEE conference model, which requires attendance of the participants in person at the main conference location. The concept entails seamless integration of the onsite and online conference systems, including data/presentation, video, audio channels. Benefits and challenges of the TIC concept are analyzed. Requirements to the web conferencing system capable of supporting the TIC conference are presented and reviewed against commercial web conferencing tools. Case study of the IEEE Toronto International Conference ? Science and Technology for Humanity, which was the first realization of TIC, is presented which analyzes various aspects (organizational, technological, and financial) of the integrated conference.
The capacity region of a class of broadcast channels with a sequence of less noisy receivers
Venue: arXiv cs.IT 2010
Year: 2010

The capacity region of a broadcast channel consisting of k-receivers that lie in a less noisy sequence is an open problem, when k >= 3. We solve this problem for the case k=3. We prove that superposition coding is optimal for a class of broadcast channels with a sequence of less noisy receivers. T
Reduced ML-Decoding Complexity, Full-Rate STBCs for 4 Transmit Antenna Systems
Venue: arXiv cs.IT 2010
Year: 2010

For an $n_t$ transmit, $n_r$ receive antenna system ($n_t \times n_r$ system), a {\it{full-rate}} space time block code (STBC) transmits $min(n_t,n_r)$ complex symbols per channel use. In this paper, a scheme to obtain a full-rate STBC for 4 transmit antennas and any $n_r$, with reduced ML-decoding complexity is presented. The weight matrices of the proposed STBC are obtained from the unitary matrix representations of Clifford Algebra. By puncturing the symbols of the STBC, full rate designs can be obtained for $n_r < 4$. For any value of $n_r$, the proposed design offers the least ML-decoding complexity among known codes. The proposed design is comparable in error performance to the well known perfect code for 4 transmit antennas while offering lower ML-decoding complexity. Further, when $n_r < 4$, the proposed design has higher ergodic capacity than the punctured Perfect code. Simulation results which corroborate these claims are presented.
How not to share a set of secrets
Venue: arXiv cs.CR 2010
Year: 2010

This note analyses one of the existing space efficient secret sharing schemes and suggests vulnerabilities in its design. We observe that the said algorithm fails for certain choices of the set of secrets and there is no reason for preferring this particular scheme over alternative schemes. The paper also elaborates the adoption of a scheme proposed by Hugo Krawczyk as an extension of Shamir's scheme, for a set of secrets. Such an implementation is space optimal and works for all choices of secrets. We also propose two new methods of attack which are valid under certain assumptions and observe that it is the elimination of random values that facilitates these kinds of attacks.
Collision Helps - Algebraic Collision Recovery for Wireless Erasure Networks
Venue: arXiv cs.IT 2010
Year: 2010

Current medium access control mechanisms are based on collision avoidance and collided packets are discarded. The recent work on ZigZag decoding departs from this approach by recovering the original packets from multiple collisions. In this paper, we present an algebraic representation of collisions which allows us to view each collision as a linear combination of the original packets. The transmitted, colliding packets may themselves be a coded version of the original packets. We propose a new acknowledgment (ACK) mechanism for collisions based on the idea that if a set of packets collide, the receiver can afford to ACK exactly one of them and still decode all the packets eventually. We analytically compare delay and throughput performance of such collision recovery schemes with other collision avoidance approaches in the context of a single hop wireless erasure network. In the multiple receiver case, the broadcast constraint calls for combining collision recovery methods with network coding across packets at the sender. From the delay perspective, our scheme, without any coordination, outperforms not only a ALOHA-type random access mechanisms, but also centralized scheduling. For the case of streaming arrivals, we propose a priority-based ACK mechanism and show that its stability region coincides with the cut-set bound of the packet erasure network.
A Topological derivative based image segmentation for sign language recognition system using isotropic filter
Venue: arXiv cs.CV 2010
Year: 2010

The need of sign language is increasing radically especially to hearing impaired community. Only few research groups try to automatically recognize sign language from video, colored gloves and etc. Their approach requires a valid segmentation of the data that is used for training and of the data that is used to be recognized. Recognition of a sign language image sequence is challenging because of the variety of hand shapes and hand motions. Here, this paper proposes to apply a combination of image segmentation with restoration using topological derivatives for achieving high recognition accuracy. Image quality measures are conceded here to differentiate the methods both subjectively as well as objectively. Experiments show that the additional use of the restoration before segmenting the postures significantly improves the correct rate of hand detection, and that the discrete derivatives yields a high rate of discrimination between different static hand postures as well as between hand postures and the scene background. Eventually, the research is to contribute to the implementation of automated sign language recognition system mainly established for the welfare purpose.
A Novel Trigon based Dual Authentication Protocol for Enhancing Security in Grid Environment
Venue: arXiv cs.CR 2010
Year: 2010

In recent times, a necessity has been raised in order to distribute computing applications often across grids. These applications are dependent on the services like data transfer or data portal services as well as submission of jobs. Security is of utmost importance in grid computing applications as grid resources are heterogeneous, dynamic, and multidomain. Authentication remains as the significant security challenge in grid environment. In traditional authentication protocol a single server stores the sensitive user credentials, like username and password. When such a server is compromised, a large number of user passwords, will be exposed. Our proposed approach uses a dual authentication protocol in order to improve the authentication service in grid environment. The protocol utilizes the fundamental concepts of trigon and based on the parameters of the trigon the user authentication will be performed. In the proposed protocol, the password is interpreted and alienated into more than one unit and these units are stored in two different servers, namely, Authentication Server and Backend Server. Only when the combined authentication scheme from both the servers authenticates the user, the privilege of accessing the requested resources is obtained by the user. The main advantage of utilizing the dual authentication protocol in grid computing is that an adversary user cannot attain the access privilege by compromising a single consolidated server because of the fact that the split password is stored in different servers.