OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Pricing in Networks with Externalities
Venue: arXiv cs.GT 2011
Year: 2011

We study the optimal pricing strategies of a monopolist selling a divisible good (service) to consumers that are embedded in a social network. A key feature of our model is that consumers experience a (positive) local network effect. In particular, each consumer's usage level depends directly on the usage of her neighbors in the social network structure. Thus, the monopolist's optimal pricing strategy may involve offering discounts to certain agents, who have a central position in the underlying network. First, we consider a setting where the monopolist can offer individualized prices and derive an explicit characterization of the optimal price for each consumer as a function of her network position. In particular, we show that it is optimal for the monopolist to charge each agent a price that is proportional to her Bonacich centrality in the social network. In the second part of the paper, we discuss the optimal strategy of a monopolist that can only choose a single uniform price for the good and derive an algorithm polynomial in the number of agents to compute such a price. Thirdly, we assume that the monopolist can offer the good in two prices, full and discounted, and study the problem of determining which set of consumers should be given the discount. We show that the problem is NP-hard, however we provide an explicit characterization of the set of agents that should be offered the discounted price. Next, we describe an approximation algorithm for finding the optimal set of agents. We show that if the profit is nonnegative under any feasible price allocation, the algorithm guarantees at least 88% of the optimal profit. Finally, we highlight the value of network information by comparing the profits of a monopolist that does not take into account the network effects when choosing her pricing policy to those of a monopolist that uses this information optimally.
On the Local Correctness of L^1 Minimization for Dictionary Learning
Venue: arXiv cs.IT 2011
Year: 2011

The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While this idea is appealing, the behavior of these algorithms is largely a mystery; although there is a body of empirical evidence suggesting they do learn very effective representations, there is little theory to guarantee when they will behave correctly, or when the learned dictionary can be expected to generalize. In this paper, we take a step towards such a theory. We show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the $\ell^1$ norm. Namely, if $\mb A \in \Re^{m \times n}$ is an incoherent (and possibly overcomplete) dictionary, and the coefficients $\mb X \in \Re^{n \times p}$ follow a random sparse model, then with high probability $(\mb A,\mb X)$ is a local minimum of the $\ell^1$ norm over the manifold of factorizations $(\mb A',\mb X')$ satisfying $\mb A' \mb X' = \mb Y$, provided the number of samples $p = Ω(n^3 k)$. For overcomplete $\mb A$, this is the first result showing that the dictionary learning problem is locally solvable. Our analysis draws on tools developed for the problem of completing a low-rank matrix from a small subset of its entries, which allow us to overcome a number of technical obstacles; in particular, the absence of the restricted isometry property.
Fault-Tolerant Spanners: Better and Simpler
Venue: arXiv cs.DS 2011
Year: 2011

A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults $r$, for all stretch bounds. For stretch $k \geq 3$ we design a simple transformation that converts every $k$-spanner construction with at most $f(n)$ edges into an $r$-fault-tolerant $k$-spanner construction with at most $O(r^3 \log n) \cdot f(2n/r)$ edges. Applying this to standard greedy spanner constructions gives $r$-fault tolerant $k$-spanners with $\tilde O(r^{2} n^{1+\frac{2}{k+1}})$ edges. The previous construction by Chechik, Langberg, Peleg, and Roddity [STOC 2009] depends similarly on $n$ but exponentially on $r$ (approximately like $k^r$). For the case $k=2$ and unit-length edges, an $O(r \log n)$-approximation algorithm is known from recent work of Dinitz and Krauthgamer [arXiv 2010], where several spanner results are obtained using a common approach of rounding a natural flow-based linear programming relaxation. Here we use a different (stronger) LP relaxation and improve the approximation ratio to $O(\log n)$, which is, notably, independent of the number of faults $r$. We further strengthen this bound in terms of the maximum degree by using the \Lovasz Local Lemma. Finally, we show that most of our constructions are inherently local by designing equivalent distributed algorithms in the LOCAL model of distributed computation.
2D Sparse Signal Recovery via 2D Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2011
Year: 2011

Recovery algorithms play a key role in compressive sampling (CS). Most of current CS recovery algorithms are originally designed for one-dimensional (1D) signal, while many practical signals are two-dimensional (2D). By utilizing 2D separable sampling, 2D signal recovery problem can be converted into 1D signal recovery problem so that ordinary 1D recovery algorithms, e.g. orthogonal matching pursuit (OMP), can be applied directly. However, even with 2D separable sampling, the memory usage and complexity at the decoder is still high. This paper develops a novel recovery algorithm called 2D-OMP, which is an extension of 1D-OMP. In the 2D-OMP, each atom in the dictionary is a matrix. At each iteration, the decoder projects the sample matrix onto 2D atoms to select the best matched atom, and then renews the weights for all the already selected atoms via the least squares. We show that 2D-OMP is in fact equivalent to 1D-OMP, but it reduces recovery complexity and memory usage significantly. What's more important, by utilizing the same methodology used in this paper, one can even obtain higher dimensional OMP (say 3D-OMP, etc.) with ease.
Simultaneous Code/Error-Trellis Reduction for Convolutional Codes Using Shifted Code/Error-Subsequences
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we show that the code-trellis and the error-trellis for a convolutional code can be reduced simultaneously, if reduction is possible. Assume that the error-trellis can be reduced using shifted error-subsequences. In this case, if the identical shifts occur in the subsequences of each code path, then the code-trellis can also be reduced. First, we obtain pairs of transformations which generate the identical shifts both in the subsequences of the code-path and in those of the error-path. Next, by applying these transformations to the generator matrix and the parity-check matrix, we show that reduction of these matrices is accomplished simultaneously, if it is possible. Moreover, it is shown that the two associated trellises are also reduced simultaneously.
Dialog interface for dynamic data models
Venue: arXiv cs.SE 2011
Year: 2011

In this paper, the new information system development methodology will be proposed. This methodology will enable the whole data model to be built and adjusted at the run time, without rebuilding the application. This will make the user much more powerful and independent on the manufacturer of the system. It will also cut the price and shorten the development time of the information systems dramatically, because common business logic will not have to be implemented for each individual table and the major part of the user interface will be generated automatically.
Hidden Tree Structure is a Key to the Emergence of Scaling in the World Wide Web
Venue: arXiv cs.SI 2011
Year: 2011

Preferential attachment is the most popular explanation for the emergence of scaling behavior in the World Wide Web, but this explanation has been challenged by the global information hypothesis, the existence of linear preference and the emergence of new big internet companies in the real world. We notice that most websites have an obvious feature that their pages are organized as a tree (namely hidden tree) and hence propose a new model that introduces a hidden tree structure into the Erdős-Ré}yi model by adding a new rule: when one node connects to another, it should also connect to all nodes in the path between these two nodes in the hidden tree. The experimental results show that the degree distribution of the generated graphs would obey power law distributions and have variable high clustering coefficients and variable small average lengths of shortest paths. The proposed model provides an alternative explanation to the emergence of scaling in the World Wide Web without the above-mentioned difficulties, and also explains the "preferential attachment" phenomenon.
Boolean network robotics: a proof of concept
Venue: arXiv cs.AI 2011
Year: 2011

Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. In this paper, we propose the use of Boolean networks for controlling robots' behaviour. The network is designed by means of an automatic procedure based on stochastic local search techniques. We show that this approach makes it possible to design a network which enables the robot to accomplish a task that requires the capability of navigating the space using a light stimulus, as well as the formation and use of an internal memory.
On the Zero-Error Capacity Threshold for Deletion Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider the zero-error capacity of deletion channels. Specifically, we consider the setting where we choose a codebook ${\cal C}$ consisting of strings of $n$ bits, and our model of the channel corresponds to an adversary who may delete up to $pn$ of these bits for a constant $p$. Our goal is to decode correctly without error regardless of the actions of the adversary. We consider what values of $p$ allow non-zero capacity in this setting. We suggest multiple approaches, one of which makes use of the natural connection between this problem and the problem of finding the expected length of the longest common subsequence of two random sequences.
Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings
Venue: arXiv cs.DS 2011
Year: 2011

A binary matrix satisfies the consecutive ones property (COP) if its columns can be permuted such that the ones in each row of the resulting matrix are consecutive. Equivalently, a family of sets F = {Q_1,..,Q_m}, where Q_i is subset of R for some universe R, satisfies the COP if the symbols in R can be permuted such that the elements of each set Q_i occur consecutively, as a contiguous segment of the permutation of R's symbols. We consider the COP version on multisets and prove that counting its solutions is difficult (#P-complete). We prove completeness results also for counting the frontiers of PQ-trees, which are typically used for testing the COP on sets, thus showing that a polynomial algorithm is unlikely to exist when dealing with multisets. We use a combinatorial approach based on parsimonious reductions from the Hamiltonian path problem, showing that the decisional version of our problems is therefore NP-complete.
Deployment and Evaluation of a 802.15.4 Heterogeneous Network
Venue: arXiv cs.DC 2011
Year: 2011

In this work we study the performance of a heterogeneous wireless sensor network which consists of 4 different hardware platforms (TelosB, SunSPOT, Arduino, iSense). All hardware platforms use 802.15.4 compliant radios. Due to partial implementation of the standard, they do not communicate out of the box. A first contribution of our work is a careful description of the necessary steps to make such a heterogeneous network interoperate. Our software code is available online. We deploy a heterogeneous network testbed and conduct a thorough evaluation of the performance. We examine various network performance metrics (e.g., transmission rate, receiving rate, packet loss, etc.), and assess the capabilities of each device and their intercommunication. We used different setups (e.g., distance between transmitters and receivers, etc.) to better understand the network limitations for each hardware platform.
Weak mu-equality is decidable
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we consider the set of mu-types, an extension of the set of simple types freely generated from a set of atomic types and the type constructor ->, by a new operator mu, to explicitly denote solutions of recursive equations like A = A -> beta. We show that this so-called weak mu-equality for mu-types is decidable by defining a derivation system for weak mu-equality based on standard reduction for mu-types such that the number of nodes in a derivation tree for A = B is bounded as a function of A, B. We give two proofs. One for decidability of = for alpha-equivalence classes of mu-types and one for = for mu-types theselves. Both proofs are straightforward and elementary.
Emergence through Selection: The Evolution of a Scientific Challenge
Venue: arXiv cs.SI 2011
Year: 2011

One of the most interesting scientific challenges nowadays deals with the analysis and the understanding of complex networks' dynamics and how their processes lead to emergence according to the interactions among their components. In this paper we approach the definition of new methodologies for the visualization and the exploration of the dynamics at play in real dynamic social networks. We present a recently introduced formalism called TVG (for time-varying graphs), which was initially developed to model and analyze highly-dynamic and infrastructure-less communication networks such as mobile ad-hoc networks, wireless sensor networks, or vehicular networks. We discuss its applicability to complex networks in general, and social networks in particular, by showing how it enables the specification and analysis of complex dynamic phenomena in terms of temporal interactions, and allows to easily switch the perspective between local and global dynamics. As an example, we chose the case of scientific communities by analyzing portion of the ArXiv repository (ten years of publications in physics) focusing on the social determinants (e.g. goals and potential interactions among individuals) behind the emergence and the resilience of scientific communities. We consider that scientific communities are at the same time communities of practice (through co-authorship) and that they exist also as representations in the scientists' mind, since references to other scientists' works is not merely an objective link to a relevant work, but it reveals social objects that one manipulates, select and refers to. In the paper we show the emergence/selection of a community as a goal-driven preferential attachment toward a set of authors among which there are some key scientists (Nobel prizes).
Classical and quantum computation with small space bounds (PhD thesis)
Venue: arXiv cs.CC 2011
Year: 2011

In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.
QOS based user driven scheduler for grid environment
Venue: arXiv cs.DC 2011
Year: 2011

As grids are in essence heterogeneous, dynamic, shared and distributed environments, managing these kinds of platforms efficiently is extremely complex. A promising scalable approach to deal with these intricacies is the design of self-managing of autonomic applications. Autonomic applications adapt their execution accordingly by considering knowledge about their own behaviour and environmental conditions.QoS based User Driven scheduling for grid that provides the self-optimizing ability in autonomic applications. Computational grids to provide a user to solve large scale problem by spreading a single large computation across multiple machines of physical location. QoS based User Driven scheduler for grid also provides reliability of the grid systems and increase the performance of the grid to reducing the execution time of job by applying scheduling policies defined by the user. The main aim of this paper is to distribute the computational load among the available grid nodes and to developed a QoS based scheduling algorithm for grid and making grid more reliable.Grid computing system is different from conventional distributed computing systems by its focus on large scale resource sharing, where processors and communication have significant inuence on Grid computing reliability. Reliability capabilities initiated by end users from within applications they submit to the grid for execution. Reliability of infrastructure and management services that perform essential functions necessary for grid systems to operate, such as resource allocation and scheduling.
Uncertainty Relations and Sparse Signal Recovery for Pairs of General Signal Sets
Venue: arXiv cs.IT 2011
Year: 2011

We present an uncertainty relation for the representation of signals in two different general (possibly redundant or incomplete) signal sets. This uncertainty relation is relevant for the analysis of signals containing two distinct features each of which can be described sparsely in a suitable general signal set. Furthermore, the new uncertainty relation is shown to lead to improved sparsity thresholds for recovery of signals that are sparse in general dictionaries. Specifically, our results improve on the well-known $(1+1/d)/2$-threshold for dictionaries with coherence $d$ by up to a factor of two. Furthermore, we provide probabilistic recovery guarantees for pairs of general dictionaries that also allow us to understand which parts of a general dictionary one needs to randomize over to "weed out" the sparsity patterns that prohibit breaking the square-root bottleneck.
A Study of IEEE 802.15.4 Security Framework for Wireless Body Area Network
Venue: arXiv cs.NI 2011
Year: 2011

A Wireless Body Area Network (WBAN) is a collection of low-power and lightweight wireless sensor nodes that are used to monitor the human body functions and the surrounding environment. It supports a number of innovative and interesting applications, including ubiquitous healthcare and Consumer Electronics (CE) applications. Since WBAN nodes are used to collect sensitive (life-critical) information and may operate in hostile environments, they require strict security mechanisms to prevent malicious interaction with the system. In this paper, we first highlight major security requirements and Denial of Service (DoS) attacks in WBAN at Physical, Medium Access Control (MAC), Network, and Transport layers. Then we discuss the IEEE 802.15.4 security framework and identify the security vulnerabilities and major attacks in the context of WBAN. Different types of attacks on the Contention Access Period (CAP) and Contention Free Period (CFP) parts of the superframe are analyzed and discussed. It is observed that a smart attacker can successfully corrupt an increasing number of GTS slots in the CFP period and can considerably affect the Quality of Service (QoS) in WBAN (since most of the data is carried in CFP period). As we increase the number of smart attackers the corrupted GTS slots are eventually increased, which prevents the legitimate nodes to utilize the bandwidth efficiently. This means that the direct adaptation of IEEE 802.15.4 security framework for WBAN is not totally secure for certain WBAN applications. New solutions are required to integrate high level security in WBAN.
A New Sum-Rate Outer Bound for Interference Channels with Three Source-Destination Pairs
Venue: arXiv cs.IT 2011
Year: 2011

This paper derives a novel sum-rate outer bound for the general memoryless interference channel with three users. The derivation is a generalization of the techniques developed by Kramer and by Etkin et al for the Gaussian two-user channel. For the three-user Gaussian channel the proposed sum-rate outer bound outperforms known bounds for certain channel parameters.
Computing Semi-algebraic Invariants for Polynomial Dynamical Systems
Venue: arXiv cs.SC 2011
Year: 2011

In this paper, we consider an extended concept of invariant for polynomial dynamical system (PDS) with domain and initial condition, and establish a sound and complete criterion for checking semi-algebraic invariants (SAI) for such PDSs. The main idea is encoding relevant dynamical properties as conditions on the high order Lie derivatives of polynomials occurring in the SAI. A direct consequence of this criterion is a relatively complete method of SAI generation based on template assumption and semi-algebraic constraint solving. Relative completeness means if there is an SAI in the form of a predefined template, then our method can indeed find one using this template.
Strategic Issues For A Successful E-Commerce
Venue: arXiv cs.CY 2011
Year: 2011

E-commerce is an emerging technology. Impact of this new technology is getting clearer with time and results are tangible to the user community. In this paper we have tried to focus some of its issues like paradigms, infrastructure integration, and security, which is considered to be the most important issue in E-Commerce. At first we have elaborated the paradigms of E-Commerce (Business-to-Business and Business-to-Consumer). Then comes the necessity of infrastructure integration with the legacy system. Security concerns comes next. Rest of the part contains conclusion and references.