OpenRaiser/Intern-Atlas huggingface dataset:
Globally Optimal Distributed Power Control for Nonconcave Utility Maximization
Venue: arXiv cs.NI 2011
Year: 2011

Transmit power control in wireless networks has long been recognized as an effective mechanism to mitigate co-channel interference. Due to the highly non-convex nature, optimal power control is known to be difficult to achieve if a system utility is to be maximized. To date, there does not yet exist a distributed power control algorithm that maximizes any form of system utility, despite the importance of distributed implementation for the wireless infrastructureless networks such as ad hoc and sensor networks. This paper fills this gap by developing a Gibbs Sampling based Asynchronous distributed power control algorithm (referred to as GLAD). The proposed algorithm quickly converges to the global optimal solution regardless of the concavity, continuity, differentiability and monotonicity of the utility function. Same as other existing distributed power control algorithms, GLAD requires extensive message passing among all users in the network, which leads to high signaling overhead and high processing complexity. To address this issue, this paper further proposes a variant of the GLAD algorithm, referred to as I-GLAD, where the prefix "I" stands for infrequent message passing. The convergence of I-GLAD can be proved regardless of the reduction in the message passing rate. To further reduce the processing complexity at each transmitter, we develop an enhanced version of I-GLAD, referred to as NI-GLAD, where only the control messages from the neighboring links are processed. Our simulation results show that I-GLAD approximately converges to the global optimal solution regardless of the type of the system utility function. Meanwhile, the optimality of the solution obtained by NI-GLAD depends on the selection of the neighborhood size.
An Adaptive Quantum-inspired Differential Evolution Algorithm for 0-1 Knapsack Problem
Venue: arXiv cs.NE 2011
Year: 2011

Differential evolution (DE) is a population based evolutionary algorithm widely used for solving multidimensional global optimization problems over continuous spaces. However, the design of its operators makes it unsuitable for many real-life constrained combinatorial optimization problems which operate on binary space. On the other hand, the quantum inspired evolutionary algorithm (QEA) is very well suitable for handling such problems by applying several quantum computing techniques such as Q-bit representation and rotation gate operator, etc. This paper extends the concept of differential operators with adaptive parameter control to the quantum paradigm and proposes the adaptive quantum-inspired differential evolution algorithm (AQDE). The performance of AQDE is found to be significantly superior as compared to QEA and a discrete version of DE on the standard 0-1 knapsack problem for all the considered test cases.
The Identity Crisis. Security, Privacy and Usability Issues in Identity Management
Venue: arXiv cs.CR 2011
Year: 2011

This paper studies the current "identity crisis" caused by the substantial security, privacy and usability shortcomings encountered in existing systems for identity management. Some of these issues are well known, while others are much less understood. This paper brings them together in a single, comprehensive study and proposes recommendations to resolve or to mitigate the problems. Some of these problems cannot be solved without substantial research and development effort.
Buffer Sizing for 802.11 Based Networks
Venue: arXiv cs.NI 2011
Year: 2011

We consider the sizing of network buffers in 802.11 based networks. Wireless networks face a number of fundamental issues that do not arise in wired networks. We demonstrate that the use of fixed size buffers in 802.11 networks inevitably leads to either undesirable channel under-utilization or unnecessary high delays. We present two novel dynamic buffer sizing algorithms that achieve high throughput while maintaining low delay across a wide range of network conditions. Experimental measurements demonstrate the utility of the proposed algorithms in a production WLAN and a lab testbed.
A note on outer bounds for broadcast channel
Venue: arXiv cs.IT 2011
Year: 2011

In this note we establish two facts concerning the so-called {\em New-Jersey} outer bound. We show that this outer bound is equivalent to a much simpler {\em computable} region; and secondly we show that in the absence of private information this bound is exactly same as the $UV$-outerbound.
Computer Simulation Center in Internet
Venue: arXiv cs.DC 2011
Year: 2011

The general description of infrastructure and content of SciShop.ru computer simulation center is given. This resource is a new form of knowledge generation and remote education using modern Cloud Computing technologies.
Information Retrieval of Jumbled Words
Venue: arXiv cs.IR 2011
Year: 2011

It is known that humans can easily read words where the letters have been jumbled in a certain way. This paper examines this problem by associating a distance measure with the jumbling process. Modifications to text were generated according to the Damerau-Levenshtein distance and it was checked if the users are able to read it. Graphical representations of the results are provided.
The Accelerating Growth of Online Tagging Systems
Venue: arXiv cs.IR 2011
Year: 2011

Research on the growth of online tagging systems not only is interesting in its own right, but also yields insights for website management and semantic web analysis. Traditional models that describing the growth of online systems can be divided between linear and nonlinear versions. Linear models, including the BA model (Brabasi and Albert, 1999), assume that the average activity of users is a constant independent of population. Hence the total activity is a linear function of population. On the contrary, nonlinear models suggest that the average activity is affected by the size of the population and the total activity is a nonlinear function of population. In the current study, supporting evidences for the nonlinear growth assumption are obtained from data on Internet users' tagging behavior. A power law relationship between the number of new tags (F) and the population (P), which can be expressed as F ~ P ^ gamma (gamma > 1), is found. I call this pattern accelerating growth and find it relates the to time-invariant heterogeneity in individual activities. I also show how a greater heterogeneity leads to a faster growth.
Time-Out Lattice Sequential Decoding for the MIMO ARQ Channel
Venue: arXiv cs.IT 2011
Year: 2011

The optimal diversity-multiplexing-delay tradeoff for the multi-input multi-output (MIMO) automatic repeat request (ARQ) channel can be achieved using incremental redundancy lattice space-time codes coupled with a list decoder for joint error detection and correction. Such a decoder is based on the minimum mean-square error lattice decoding principle which is implemented using sphere decoding algorithms. However, sphere decoders suffer from high computational complexity for low-to-moderate signal-to-noise ratios, especially for large signal dimensions. In this paper, we would like to construct a more efficient decoder that is capable of achieving the optimal tradeoff with much lower complexity. In particular, we will study the throughput-performance-complexity tradeoffs in sequential decoding algorithms and the effect of preprocessing and termination strategies. We show, analytically and via simulation, that using the \textit{lattice sequential decoder} that implements a time-out algorithm for joint error detection and correction, the optimal tradeoff of the MIMO ARQ channel can be achieved with significant reduction in decoding complexity.
Applying Science Models for Search
Venue: arXiv cs.IR 2011
Year: 2011

The paper proposes three different kinds of science models as value-added services that are integrated in the retrieval process to enhance retrieval quality. The paper discusses the approaches Search Term Recommendation, Bradfordizing and Author Centrality on a general level and addresses implementation issues of the models within a real-life retrieval environment.
Approaches to Formal Verification of Security Protocols
Venue: arXiv cs.CR 2011
Year: 2011

In recent times, many protocols have been proposed to provide security for various information and communication systems. Such protocols must be tested for their functional correctness before they are used in practice. Application of formal methods for verification of security protocols would enhance their reliability thereby, increasing the usability of systems that employ them. Thus, formal verification of security protocols has become a key issue in computer and communications security. In this paper we present, analyze and compare some prevalent approaches towards verification of secure systems. We follow the notion of - same goal through different approaches - as we formally analyze the Needham Schroeder Public Key protocol for Lowe's attack using each of our presented approaches.
Determinization of $ω$-automata unified
Venue: arXiv cs.FL 2011
Year: 2011

We describe a uniform construction for converting $ω$-automata with arbitrary acceptance conditions (based on the notion of infinity sets i.e. the set of states visited infinitely often in a run of the automaton) to equivalent deterministic parity automata (DPW). Given a non-deterministic automaton with $n$ states, our construction gives a DPW with at most $2^{O(n^2 \log n)}$ states and $O(n^2)$ parity indices. The corresponding bounds when the original automaton is deterministic are O(n!) and O(n), respectively. Our algorithm gives better asymptotic bounds on the number of states and parity indices vis-a-vis the best known technique when determinizing Rabin or Streett automata with $Ω{(2^n)}$ acceptance pairs, where $n > 1$. We demonstrate this by describing a family of Streett (and Rabin) automata with $2^{n}$ non-redundant acceptance pairs, for which the best known determinization technique gives a DPW with at least $Ω{(2^{(n^3)})}$ states, while our construction constructs a DRW/DPW with $2^{O(n^2\log n)}$ states. An easy corollary of our construction is that an $ω$-language with Rabin index $k$ cannot be recognized by any $ω$-automaton (deterministic or non-deterministic) with fewer than $O(\sqrt{k})$ states.
Superposition Coding-Based Bounds and Capacity for the Cognitive Z-Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the cognitive interference channel (CIC) with two transmitters and two receivers, in which the cognitive transmitter non-causally knows the message and codeword of the primary transmitter. We first introduce a discrete memoryless more capable CIC, which is an extension to the more capable broadcast channel (BC). Using superposition coding, we propose an inner bound and an outer bound on its capacity region. The outer bound is also valid when the primary user is under strong interference. For the Gaussian CIC, this outer bound applies for $|a| \geq 1 $, where $a$ is the gain of interference link from secondary user to primary receiver. These capacity inner and outer bounds are then applied to the Gaussian cognitive Z-interference channel (GCZIC) where only the primary receiver suffers interference. Upon showing that jointly Gaussian input maximizes these bounds for the GCZIC, we evaluate the bounds for this channel. The new outer bound is strictly tighter than other outer bounds on the capacity of the GCZIC at strong interference ($a^2 \geq 1 $). Especially, the outer bound coincides with the inner bound for $|a| \geq \sqrt{1 + P_1}$ and thus, establishes the capacity of the GCZIC at this range. For such a large $a$, superposition encoding at the cognitive transmitter and successive decoding at the primary receiver are capacity-achieving.
Efficient tilings of de Bruijn and Kautz graphs
Venue: arXiv cs.DC 2011
Year: 2011

Kautz and de Bruijn graphs have a high degree of connectivity which makes them ideal candidates for massively parallel computer network topologies. In order to realize a practical computer architecture based on these graphs, it is useful to have a means of constructing a large-scale system from smaller, simpler modules. In this paper we consider the mathematical problem of uniformly tiling a de Bruijn or Kautz graph. This can be viewed as a generalization of the graph bisection problem. We focus on the problem of graph tilings by a set of identical subgraphs. Tiles should contain a maximal number of internal edges so as to minimize the number of edges connecting distinct tiles. We find necessary and sufficient conditions for the construction of tilings. We derive a simple lower bound on the number of edges which must leave each tile, and construct a class of tilings whose number of edges leaving each tile agrees asymptotically in form with the lower bound to within a constant factor. These tilings make possible the construction of large-scale computing systems based on de Bruijn and Kautz graph topologies.
Automatic segmentation of HeLa cell images
Venue: arXiv cs.CV 2011
Year: 2011

In this work, the possibilities for segmentation of cells from their background and each other in digital image were tested, combined and improoved. Lot of images with young, adult and mixture cells were able to prove the quality of described algorithms. Proper segmentation is one of the main task of image analysis and steps order differ from work to work, depending on input images. Reply for biologicaly given question was looking for in this work, including filtration, details emphasizing, segmentation and sphericity computing. Order of algorithms and way to searching for them was also described. Some questions and ideas for further work were mentioned in the conclusion part.
Capacity Region of Finite State Multiple-Access Channel with Delayed State Information at the Transmitters
Venue: arXiv cs.IT 2011
Year: 2011

A single-letter characterization is provided for the capacity region of finite-state multiple access channels. The channel state is a Markov process, the transmitters have access to delayed state information, and channel state information is available at the receiver. The delays of the channel state information are assumed to be asymmetric at the transmitters. We apply the result to obtain the capacity region for a finite-state Gaussian MAC, and for a finite-state multiple-access fading channel. We derive power control strategies that maximize the capacity region for these channels.
Improved Peak Cancellation for PAPR Reduction in OFDM Systems
Venue: arXiv cs.IT 2011
Year: 2011

This letter presents an improved peak cancellation (PC) scheme for peak-to-average power ratio (PAPR) reduction in orthogonal frequency division multiplexing (OFDM) systems. The main idea is based on a serial peak cancellation (SPC) mode for alleviating the peak regrowth of the conventional schemes. Based on the SPC mode, two particular algorithms are developed with different tradeoff between PAPR and computational complexity. Simulation shows that the proposed scheme has a better tradeoff among PAPR, complexity and signal distortion than the conventional schemes.
Maximum Rate of Unitary-Weight, Single-Symbol Decodable STBCs
Venue: arXiv cs.IT 2011
Year: 2011

It is well known that the Space-time Block Codes (STBCs) from Complex orthogonal designs (CODs) are single-symbol decodable/symbol-by-symbol decodable (SSD). The weight matrices of the square CODs are all unitary and obtainable from the unitary matrix representations of Clifford Algebras when the number of transmit antennas $n$ is a power of 2. The rate of the square CODs for $n = 2^a$ has been shown to be $\frac{a+1}{2^a}$ complex symbols per channel use. However, SSD codes having unitary-weight matrices need not be CODs, an example being the Minimum-Decoding-Complexity STBCs from Quasi-Orthogonal Designs. In this paper, an achievable upper bound on the rate of any unitary-weight SSD code is derived to be $\frac{a}{2^{a-1}}$ complex symbols per channel use for $2^a$ antennas, and this upper bound is larger than that of the CODs. By way of code construction, the interrelationship between the weight matrices of unitary-weight SSD codes is studied. Also, the coding gain of all unitary-weight SSD codes is proved to be the same for QAM constellations and conditions that are necessary for unitary-weight SSD codes to achieve full transmit diversity and optimum coding gain are presented.
An Efficient and User Privacy-Preserving Routing Protocol for Wireless Mesh Networks
Venue: arXiv cs.CR 2011
Year: 2011

Wireless mesh networks (WMNs) have emerged as a key technology for next generation wireless broadband networks showing rapid progress and inspiring numerous compelling applications. A WMN comprises of a set of mesh routers (MRs) and mesh clients (MCs), where MRs are connected to the Internet backbone through the Internet gateways (IGWs). The MCs are wireless devices and communicate among themselves over possibly multi-hop paths with or without the involvement of MRs. User privacy and security have been primary concerns in WMNs due to their peer-to-peer network topology, shared wireless medium, stringent resource constraints, and highly dynamic environment. Moreover, to support real-time applications, WMNs must also be equipped with robust, reliable and efficient routing protocols so as to minimize the end-to-end latency. Design of a secure and efficient routing protocol for WMNs, therefore, is of paramount importance. In this paper, we propose an efficient and reliable routing protocol that also provides user anonymity in WMNs. The protocol is based on an accurate estimation of the available bandwidth in the wireless links and a robust estimation of the end-to-end delay in a routing path, and minimization of control message overhead. The user anonymity, authentication and data privacy is achieved by application of a novel protocol that is based on Rivest's ring signature scheme. Simulations carried out on the proposed protocol demonstrate that it is more efficient than some of the existing routing protocols.
Powermonads and Tensors of Unranked Effects
Venue: arXiv cs.LO 2011
Year: 2011

In semantics and in programming practice, algebraic concepts such as monads or, essentially equivalently, (large) Lawvere theories are a well-established tool for modelling generic side-effects. An important issue in this context are combination mechanisms for such algebraic effects, which allow for the modular design of programming languages and verification logics. The most basic combination operators are sum and tensor: while the sum of effects is just their non-interacting union, the tensor imposes commutation of effects. However, for effects with unbounded arity, such as continuations or unbounded nondeterminism, it is not a priori clear whether these combinations actually exist in all cases. Here, we introduce the class of uniform effects, which includes unbounded nondeterminism and continuations, and prove that the tensor does always exist if one of the component effects is uniform, thus in particular improving on previous results on tensoring with continuations. We then treat the case of nondeterminism in more detail, and give an order-theoretic characterization of effects for which tensoring with nondeterminism is conservative, thus enabling nondeterministic arguments such as a generic version of the Fischer-Ladner encoding of control operators.
Dueling Algorithms
Venue: arXiv cs.GT 2011
Year: 2011

We revisit classic algorithmic search and optimization problems from the perspective of competition. Rather than a single optimizer minimizing expected cost, we consider a zero-sum game in which an optimization problem is presented to two players, whose only goal is to outperform the opponent. Such games are typically exponentially large zero-sum games, but they often have a rich combinatorial structure. We provide general techniques by which such structure can be leveraged to find minmax-optimal and approximate minmax-optimal strategies. We give examples of ranking, hiring, compression, and binary search duels, among others. We give bounds on how often one can beat the classic optimization algorithms in such duels.
Simulating Opinion Dynamics in Heterogeneous Communication
Venue: arXiv cs.SI 2011
Year: 2011

Since the information available is fundamental for our perceptions and opinions, we are interested in understanding the conditions allowing for a good information to be disseminated. This paper explores opinion dynamics by means of multi-agent based simulations when agents get informed by different sources of information. The scenario implemented includes three main streams of information acquisition, differing in both the contents and the perceived reliability of the messages spread. Agents' internal opinion is updated either by accessing one of the information sources, namely media and experts, or by exchanging information with one another. They are also endowed with cognitive mechanisms to accept, reject or partially consider the acquired information. We expect that peer-to--peer communication and reliable information sources are able both to reduce biased perceptions and to inhibit information cheating, possibly performed by the media as stated by the agenda-setting theory. In the paper, after having shortly presented both the hypotheses and the model, the simulation design will be specified and results will be discussed with respect to the hypotheses. Some considerations and ideas for future studies will conclude the paper.
Reactive Valuations
Venue: arXiv cs.LO 2011
Year: 2011

In sequential logic there is an order in which the atomic propositions in an expression are evaluated. This order allows the same atomic proposition to have different values depending on which atomic propositions have already been evaluated. In the sequential propositional logic discussed in this thesis, such valuations are called "reactive" valuations, in contrast to "static" valuations as are common in e.g. ordinary propositional logic. There are many classes of these reactive valuations e.g., we can define a class of reactive valuations such that the value for each atomic proposition remains the same until another atomic proposition is evaluated. This Master of Logic thesis consists of a study of some of the properties of this logic. We take a closer look at some of the classes of reactive valuations. We particularly focus on the relation between the axiomatization and the semantics. Consequently, the main part of this thesis focuses on proving soundness and completeness. Furthermore, we show that the axioms in the provided axiomatizations are independent i.e., there are no redundant axioms present. Finally, we show ω-completeness for two classes of reactive valuations.
A note on triangle-free graphs
Venue: arXiv cs.DM 2011
Year: 2011

We show that if $G$ is a simple triangle-free graph with $n\geq 3$ vertices, without a perfect matching, and having a minimum degree at least $\frac{n-1}{2}$, then $G$ is isomorphic either to $C_5$ or to $K_{\frac{n-1}{2},\frac{n+1}{2}}$.