OpenRaiser/Intern-Atlas huggingface dataset:
Information Capacity of Energy Harvesting Sensor Nodes
Venue: arXiv cs.IT 2011
Year: 2011

Sensor nodes with energy harvesting sources are gaining popularity due to their ability to improve the network life time and are becoming a preferred choice supporting `green communication'. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over an AWGN channel and show that the capacity achieving energy management policies are related to the throughput optimal policies. We also obtain the capacity when energy conserving sleep-wake modes are supported and an achievable rate for the system with inefficiencies in energy storage.
A secure email login system using virtual password
Venue: arXiv cs.CR 2011
Year: 2011

In today's world password compromise by some adversaries is common for different purpose. In ICC 2008 Lei et al. proposed a new user authentication system based on the virtual password system. In virtual password system they have used linear randomized function to be secure against identity theft attacks, phishing attacks, keylogging attack and shoulder surfing system. In ICC 2010 Li's given a security attack on the Lei's work. This paper gives modification on Lei's work to prevent the Li's attack with reducing the server overhead. This paper also discussed the problems with current password recovery system and gives the better approach.
The E8 Lattice and Error Correction in Multi-Level Flash Memory
Venue: arXiv cs.IT 2011
Year: 2011

A construction using the E8 lattice and Reed-Solomon codes for error-correction in flash memory is given. Since E8 lattice decoding errors are bursty, a Reed-Solomon code over GF($2^8$) is well suited. This is a type of coded modulation, where the Euclidean distance of the lattice, which is an eight-dimensional signal constellation, is combined with the Hamming distance of the code. This system is compared with the conventional technique for flash memories, BCH codes using Gray-coded PAM. The described construction has a performance advantage of 1.6 to 1.8 dB at a probability of word error of $10^{-6}$. Evaluation is at high data rates of 2.9 bits/cell for flash memory cells that have an uncoded data density of 3 bits/cell.
On the Optimal Compressions in the Compress-and-Forward Relay Schemes
Venue: arXiv cs.IT 2011
Year: 2011

..... joint decoding provides more freedom in choosing the compression at the relay. However, the question remains whether this freedom of selecting the compression necessarily improves the achievable rate of the original message. It has been shown in (El Gamal and Kim, 2010) that the answer is negative in the single-relay case. In this paper, it is further demonstrated that in the case of multiple relays, there is no improvement on the achievable rate by joint decoding either. More interestingly, it is discovered that any compressions not supporting successive decoding will actually lead to strictly lower achievable rates for the original message. Therefore, to maximize the achievable rate for the original message, the compressions should always be chosen to support successive decoding. Furthermore, it is shown that any compressions not completely decodable even with joint decoding will not provide any contribution to the decoding of the original message. The above phenomenon is also shown to exist under the repetitive encoding framework recently proposed by (Lim, Kim, El Gamal, and Chung, 2010), which improved the achievable rate in the case of multiple relays. Here, another interesting discovery is that the improvement is not a result of repetitive encoding, but the benefit of delayed decoding after all the blocks have been finished. The same rate is shown to be achievable with the simpler classical encoding process of (Cover and El Gamal, 1979) with a block-by-block backward decoding process.
Multilevel Coding Schemes for Compute-and-Forward
Venue: arXiv cs.IT 2011
Year: 2011

We investigate techniques for designing modulation/coding schemes for the wireless two-way relaying channel. The relay is assumed to have perfect channel state information, but the transmitters are assumed to have no channel state information. We consider physical layer network coding based on multilevel coding techniques. Our multilevel coding framework is inspired by the compute-and-forward relaying protocol. Indeed, we show that the framework developed here naturally facilitates decoding of linear combinations of codewords for forwarding by the relay node. We develop our framework with general modulation formats in mind, but numerical results are presented for the case where each node transmits using the QPSK constellation with gray labeling. We focus our discussion on the rates at which the relay may reliably decode linear combinations of codewords transmitted from the end nodes.
Algorithms for nonnegative matrix factorization with the beta-divergence
Venue: arXiv cs.LG 2011
Year: 2011

This paper describes algorithms for nonnegative matrix factorization (NMF) with the beta-divergence (beta-NMF). The beta-divergence is a family of cost functions parametrized by a single shape parameter beta that takes the Euclidean distance, the Kullback-Leibler divergence and the Itakura-Saito divergence as special cases (beta = 2,1,0, respectively). The proposed algorithms are based on a surrogate auxiliary function (a local majorization of the criterion function). We first describe a majorization-minimization (MM) algorithm that leads to multiplicative updates, which differ from standard heuristic multiplicative updates by a beta-dependent power exponent. The monotonicity of the heuristic algorithm can however be proven for beta in (0,1) using the proposed auxiliary function. Then we introduce the concept of majorization-equalization (ME) algorithm which produces updates that move along constant level sets of the auxiliary function and lead to larger steps than MM. Simulations on synthetic and real data illustrate the faster convergence of the ME approach. The paper also describes how the proposed algorithms can be adapted to two common variants of NMF : penalized NMF (i.e., when a penalty function of the factors is added to the criterion function) and convex-NMF (when the dictionary is assumed to belong to a known subspace).
For the Grid and Through the Grid: The Role of Power Line Communications in the Smart Grid
Venue: arXiv cs.NI 2011
Year: 2011

Is Power Line Communications (PLC) a good candidate for Smart Grid applications? The objective of this paper is to address this important question. To do so we provide an overview of what PLC can deliver today by surveying its history and describing the most recent technological advances in the area. We then address Smart Grid applications as instances of sensor networking and network control problems and discuss the main conclusion one can draw from the literature on these subjects. The application scenario of PLC within the Smart Grid is then analyzed in detail. Since a necessary ingredient of network planning is modeling, we also discuss two aspects of engineering modeling that relate to our question. The first aspect is modeling the PLC channel through fading models. The second aspect we review is the Smart Grid control and traffic modeling problem which allows us to achieve a better understanding of the communications requirements. Finally, this paper reports recent studies on the electrical and topological properties of a sample power distribution network. Power grid topological studies are very important for PLC networking as the power grid is not only the information source \textit{but also} the information delivery system - a unique feature when PLC is used for the Smart Grid.
On the Scaling Law for Compressive Sensing and its Applications
Venue: arXiv cs.IT 2011
Year: 2011

$\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity (the size of the support set), under which with high probability a sparse signal can be recovered from i.i.d. Gaussian measurements, have been computed and are referred to as "weak thresholds" \cite{D}. It was also known that there is a tradeoff between the sparsity and the $\ell_1$ minimization recovery stability. In this paper, we give a \emph{closed-form} characterization for this tradeoff which we call the scaling law for compressive sensing recovery stability. In a nutshell, we are able to show that as the sparsity backs off $\varpi$ ($0<\varpi<1$) from the weak threshold of $\ell_1$ recovery, the parameter for the recovery stability will scale as $\frac{1}{\sqrt{1-\varpi}}$. Our result is based on a careful analysis through the Grassmann angle framework for the Gaussian measurement matrix. We will further discuss how this scaling law helps in analyzing the iterative reweighted $\ell_1$ minimization algorithms. If the nonzero elements over the signal support follow an amplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative $f^{t}(0) \neq 0$ for some integer $t \geq 0$, then a certain iterative reweighted $\ell_1$ minimization algorithm can be analytically shown to lift the phase transition thresholds (weak thresholds) of the plain $\ell_1$ minimization algorithm.
Indexing Finite Language Representation of Population Genotypes
Venue: arXiv cs.DS 2011
Year: 2011

With the recent advances in DNA sequencing, it is now possible to have complete genomes of individuals sequenced and assembled. This rich and focused genotype information can be used to do different population-wide studies, now first time directly on whole genome level. We propose a way to index population genotype information together with the complete genome sequence, so that one can use the index to efficiently align a given sequence to the genome with all plausible genotype recombinations taken into account. This is achieved through converting a multiple alignment of individual genomes into a finite automaton recognizing all strings that can be read from the alignment by switching the sequence at any time. The finite automaton is indexed with an extension of Burrows-Wheeler transform to allow pattern search inside the plausible recombinant sequences. The size of the index stays limited, because of the high similarity of individual genomes. The index finds applications in variation calling and in primer design. On a variation calling experiment, we found about 1.0% of matches to novel recombinants just with exact matching, and up to 2.4% with approximate matching.
Collaboration in computer science: a network science approach. Part I
Venue: arXiv cs.SI 2011
Year: 2011

Co-authorship in publications within a discipline uncovers interesting properties of the analysed field. We represent collaboration in academic papers of computer science in terms of differently grained networks, including those sub-networks that emerge from conference and journal co-authorship only. We take advantage of the network science paraphernalia to take a picture of computer science collaboration including all papers published in the field since 1936. We investigate typical bibliometric properties like scientific productivity of authors and collaboration level in papers, as well as large-scale network properties like reachability and average separation distance among scholars, distribution of the number of scholar collaborators, network resilience and dependence on star collaborators, network clustering, and network assortativity by number of collaborators.
On variables with few occurrences in conjunctive normal forms
Venue: arXiv cs.DM 2011
Year: 2011

We consider the question of the existence of variables with few occurrences in boolean conjunctive normal forms (clause-sets). Let mvd(F) for a clause-set F denote the minimal variable-degree, the minimum of the number of occurrences of variables. Our main result is an upper bound mvd(F) <= nM(surp(F)) <= surp(F) + 1 + log_2(surp(F)) for lean clause-sets F in dependency on the surplus surp(F). - Lean clause-sets, defined as having no non-trivial autarkies, generalise minimally unsatisfiable clause-sets. - For the surplus we have surp(F) <= delta(F) = c(F) - n(F), using the deficiency delta(F) of clause-sets, the difference between the number of clauses and the number of variables. - nM(k) is the k-th "non-Mersenne" number, skipping in the sequence of natural numbers all numbers of the form 2^n - 1. We conjecture that this bound is nearly precise for minimally unsatisfiable clause-sets. As an application of the upper bound we obtain that (arbitrary!) clause-sets F with mvd(F) > nM(surp(F)) must have a non-trivial autarky (so clauses can be removed satisfiability-equivalently by an assignment satisfying some clauses and not touching the other clauses). It is open whether such an autarky can be found in polynomial time. As a future application we discuss the classification of minimally unsatisfiable clause-sets depending on the deficiency.
An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity
Venue: arXiv cs.DS 2011
Year: 2011

We study the problem of learning to rank from pairwise preferences, and solve a long-standing open problem that has led to development of many heuristics but no provable results for our particular problem. Given a set $V$ of $n$ elements, we wish to linearly order them given pairwise preference labels. A pairwise preference label is obtained as a response, typically from a human, to the question "which if preferred, u or v?$ for two elements $u,v\in V$. We assume possible non-transitivity paradoxes which may arise naturally due to human mistakes or irrationality. The goal is to linearly order the elements from the most preferred to the least preferred, while disagreeing with as few pairwise preference labels as possible. Our performance is measured by two parameters: The loss and the query complexity (number of pairwise preference labels we obtain). This is a typical learning problem, with the exception that the space from which the pairwise preferences is drawn is finite, consisting of ${n\choose 2}$ possibilities only. We present an active learning algorithm for this problem, with query bounds significantly beating general (non active) bounds for the same error guarantee, while almost achieving the information theoretical lower bound. Our main construct is a decomposition of the input s.t. (i) each block incurs high loss at optimum, and (ii) the optimal solution respecting the decomposition is not much worse than the true opt. The decomposition is done by adapting a recent result by Kenyon and Schudy for a related combinatorial optimization problem to the query efficient setting. We thus settle an open problem posed by learning-to-rank theoreticians and practitioners: What is a provably correct way to sample preference labels? To further show the power and practicality of our solution, we show how to use it in concert with an SVM relaxation.
On Three Alternative Characterizations of Combined Traces
Venue: arXiv cs.FL 2011
Year: 2011

The combined trace (i.e., comtrace) notion was introduced by Janicki and Koutny in 1995 as a generalization of the Mazurkiewicz trace notion. Comtraces are congruence classes of step sequences, where the congruence relation is defined from two relations simultaneity and serializability on events. They also showed that comtraces correspond to some class of labeled stratified order structures, but left open the question of what class of labeled stratified orders represents comtraces. In this work, we proposed a class of labeled stratified order structures that captures exactly the comtrace notion. Our main technical contributions are representation theorems showing that comtrace quotient monoid, combined dependency graph (Kleijn and Koutny 2008) and our labeled stratified order structure characterization are three different and yet equivalent ways to represent comtraces. This paper is a revised and expanded version of Lê (in Proceedings of PETRI NETS 2010, LNCS 6128, pp. 104-124).
Reciprocating Preferences Stablize Matching: College Admissions Revisited
Venue: arXiv cs.GT 2011
Year: 2011

In considering the college admissions problem, almost fifty years ago, Gale and Shapley came up with a simple abstraction based on preferences of students and colleges. They introduced the concept of stability and optimality; and proposed the deferred acceptance (DA) algorithm that is proven to lead to a stable and optimal solution. This algorithm is simple and computationally efficient. Furthermore, in subsequent studies it is shown that the DA algorithm is also strategy-proof, which means, when the algorithm is played out as a mechanism for matching two sides (e.g. colleges and students), the parties (colleges or students) have no incentives to act other than according to their true preferences. Yet, in practical college admission systems, the DA algorithm is often not adopted. Instead, an algorithm known as the Boston Mechanism (BM) or its variants are widely adopted. In BM, colleges accept students without deferral (considering other colleges' decisions), which is exactly the opposite of Gale-Shapley's DA algorithm. To explain and rationalize this reality, we introduce the notion of reciprocating preference to capture the influence of a student's interest on a college's decision. This model is inspired by the actual mechanism used to match students to universities in Hong Kong. The notion of reciprocating preference defines a class of matching algorithms, allowing different degrees of reciprocating preferences by the students and colleges. DA and BM are but two extreme cases (with zero and a hundred percent reciprocation) of this set. This model extends the notion of stability and optimality as well. As in Gale-Shapley's original paper, we discuss how the analogy can be carried over to the stable marriage problem, thus demonstrating the model's general applicability.
Santa Claus Schedules Jobs on Unrelated Machines
Venue: arXiv cs.DS 2011
Year: 2011

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p_{ij} if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form p_{ij} in {p_j, \infty}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + ε\approx 1.9412 + ε, where ε> 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.
Privately Releasing Conjunctions and the Statistical Query Barrier
Venue: arXiv cs.DS 2011
Year: 2011

Suppose we would like to know all answers to a set of statistical queries C on a data set up to small error, but we can only access the data itself using statistical queries. A trivial solution is to exhaustively ask all queries in C. Can we do any better? + We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of C in Kearns' statistical query (SQ) model. This gives a complete answer to the question when running time is not a concern. + We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to C can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. While interesting from a learning theoretic point of view, our main applications are in privacy-preserving data analysis: Here, our second result leads to the first algorithm that efficiently releases differentially private answers to of all Boolean conjunctions with 1% average error. This presents significant progress on a key open problem in privacy-preserving data analysis. Our first result on the other hand gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non-privacy-preserving) implementation using only statistical queries. Not only our algorithms, but also most known private algorithms can be implemented using only statistical queries, and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ-model as a new barrier in the design of differentially private algorithms.
Data Fusion Based Interference Matrix Generation for Cellular System Frequency Planning
Venue: arXiv cs.NI 2011
Year: 2011

Interference matrix (IM) has been widely used in frequency planning/optimization of cellular systems because it describes the interaction between any two cells. IM is generated from the source data gathered from the cellular system, either mobile measurement reports (MMRs) or drive test (DT) records. IM accuracy is not satisfactory since neither MMRs nor DT records contain complete information on interference and traffic distribution. In this paper, two IM generation algorithms based on source data fusion are proposed. Data fusion in one algorithm is to reinforce MMRs data, using the frequency-domain information of DT data from the same region. Data fusion in another algorithm is to reshape DT data, using the traffic distribution information extracted from MMRs from the same region. The fused data contains more complete information so that more accurate IM can be obtained. Simulation results have validated this conclusion.
Distributed Verification and Hardness of Distributed Approximation
Venue: arXiv cs.DC 2011
Year: 2011

We study the {\em verification} problem in distributed networks, stated as follows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knows which edges incident on it are in $H$. We would like to verify whether $H$ has some properties, e.g., if it is a tree or if it is connected. We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification, and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and $s-t$ cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the {\em hardness of distributed approximation} for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Moreover, our unconditional lower bound of approximating minimum spanning tree (MST) subsumes and improves upon the previous hardness of approximation bound of Elkin [STOC 2004] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [FOCS 1999]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm, for {\em any} approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems.