OpenRaiser/Intern-Atlas huggingface dataset:
A performance analysis framework for SOCP algorithms in noisy compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

Solving under-determined systems of linear equations with sparse solutions attracted enormous amount of attention in recent years, above all, due to work of \cite{CRT,CanRomTao06,DonohoPol}. In \cite{CRT,CanRomTao06,DonohoPol} it was rigorously shown for the first time that in a statistical and large dimensional context a linear sparsity can be recovered from an under-determined system via a simple polynomial $\ell_1$-optimization algorithm. \cite{CanRomTao06} went even further and established that in \emph{noisy} systems for any linear level of under-determinedness there is again a linear sparsity that can be \emph{approximately} recovered through an SOCP (second order cone programming) noisy equivalent to $\ell_1$. Moreover, the approximate solution is (in an $\ell_2$-norm sense) guaranteed to be no further from the sparse unknown vector than a constant times the noise. In this paper we will also consider solving \emph{noisy} linear systems and present an alternative statistical framework that can be used for their analysis. To demonstrate how the framework works we will show how one can use it to precisely characterize the approximation error of a wide class of SOCP algorithms. We will also show that our theoretical predictions are in a solid agrement with the results one can get through numerical simulations.
Using Memory-Protection to Simplify Zero-copy Operations
Venue: arXiv cs.DC 2013
Year: 2013

High performance networks (e.g. Infiniband) rely on zero-copy operations for performance. Zero-copy operations, as the name implies, avoid copying buffers for sending and receiving data. Instead, hardware devices directly read and write to application specified areas of memory. Since these networks can send and receive at nearly the same speed as the memory bus inside machines, zero-copy operations are necessary to achieve peak performance for many applications. Unfortunately, programming with zero-copy APIs is a *giant pain*. Users must carefully avoid using buffers that may be accessed by a device. Typically this either results in spaghetti code (where every access to a buffer is checked before usage), or blocking operations (which pretty much defeat the whole point of zero-copy). We show that by abusing memory protection hardware, we can offer the best of both worlds: a simple zero-copy mechanism which allows for non-blocking send and receives while protecting against incorrect accesses.
Joint Transmit Beamforming and Receive Power Splitting for MISO SWIPT Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies a multi-user multiple-input single-output (MISO) downlink system for simultaneous wireless information and power transfer (SWIPT), in which a set of single-antenna mobile stations (MSs) receive information and energy simultaneously via power splitting (PS) from the signal sent by a multi-antenna base station (BS). We aim to minimize the total transmission power at BS by jointly designing transmit beamforming vectors and receive PS ratios for all MSs under their given signal-to-interference-plus-noise ratio (SINR) constraints for information decoding and harvested power constraints for energy harvesting. First, we derive the sufficient and necessary condition for the feasibility of our formulated problem. Next, we solve this non-convex problem by applying the technique of semidefinite relaxation (SDR). We prove that SDR is indeed tight for our problem and thus achieves its global optimum. Finally, we propose two suboptimal solutions of lower complexity than the optimal solution based on the principle of separating the optimization of transmit beamforming and receive PS, where the zero-forcing (ZF) and the SINR-optimal based transmit beamforming schemes are applied, respectively.
An Approach to Secure Mobile Enterprise Architectures
Venue: arXiv cs.NI 2013
Year: 2013

Due to increased security awareness of enterprises for mobile applications operating with sensitive or personal data as well as extended regulations form legislative (the principle of proportionality) various approaches, how to implement (extended) two-factor authentication, multi-factor authentication or virtual private network within enterprise mobile environments to ensure delivery of secure applications, have been developed. Within mobile applications it will not be sufficient to rely on security measures of the individual components or interested parties, an overall concept of a security solution has to be established which requires the interaction of several technologies, standards and system components. These include the physical fuses on the device itself as well as on the network layer (such as integrated security components), security measures (such as employee agreements, contract clauses), insurance coverage, but also software technical protection at the application level (e.g. password protection, encryption, secure container). The purpose of this paper is to summarize the challenges and practical successes, providing best practices to fulfill appropriate risk coverage of mobile applications. I present a use case, in order to proof the concept in actual work settings, and to demonstrate the adaptability of the approach.
Entanglement Zoo I: Foundational and Structural Aspects
Venue: arXiv cs.AI 2013
Year: 2013

We put forward a general classification for a structural description of the entanglement present in compound entities experimentally violating Bell's inequalities, making use of a new entanglement scheme that we developed recently. Our scheme, although different from the traditional one, is completely compatible with standard quantum theory, and enables quantum modeling in complex Hilbert space for different types of situations. Namely, situations where entangled states and product measurements appear ('customary quantum modeling'), and situations where states and measurements and evolutions between measurements are entangled ('nonlocal box modeling', 'nonlocal non-marginal box modeling'). The role played by Tsirelson's bound and marginal distribution law is emphasized. Specific quantum models are worked out in detail in complex Hilbert space within this new entanglement scheme.
A Signal Constellation for Pilotless Communications Over Wiener Phase Noise Channels
Venue: arXiv cs.IT 2013
Year: 2013

Many satellite communication systems operating today employ low cost upconverters or downconverters which create phase noise. This noise can severely limit the information rate of the system and pose a serious challenge for the detection systems. Moreover, simple solutions for phase noise tracking such as PLL either require low phase noise or otherwise require many pilot symbols which reduce the effective data rate. In order to increase the effective information rate, we propose a signal constellation which does not require pilots, at all, in order to converge in the decoding process. In this contribution, we will present a signal constellation which does not require pilot sequences, but we require a signal that does not present rotational symmetry. For example a simple MPSK cannot be used.Moreover, we will provide a method to analyze the proposed constellations and provide a figure of merit for their performance when iterative decoding algorithms are used.
Towards LP Modeling for Maximizing Throughput and Minimizing Routing Delay in Proactive Protocols in Wireless Multi-hop Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Multi-hop Networks (WMhNs) provide users with the facility to communicate while moving with whatever the node speed, the node density and the number of traffic flows they want, without any unwanted delay and/or disruption. This paper contributes Linear Programming models (LP_models) for WMhNs. In WMhNs, different routing protocols are used to facilitate users demand(s). To practically examine constraints of respective LP_models over different routing techniques, we select three proactive routing protocols; Destination Sequence Distance Vector (DSDV), Fish-eye State Routing (FSR) and Optimized Link State Routing (OLSR). These protocols are simulated in two important scenarios regarding to user demands; mobilities and different network flows. To evaluate the performance, we further relate the protocols strategy effects on respective constraints in selected network scenarios.
Incidence coloring game and arboricity of graphs
Venue: arXiv cs.DM 2013
Year: 2013

An incidence of a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge incident to $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent whenever $v = w$, or $e = f$, or $vw = e$ or $f$. The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980-1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number $i_g(G)$ of a graph $G$ is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on $G$. Andres proved that %$\lceil 3/2 Δ(G)\rceil \le $i_g(G) \le 2Δ(G) + 4k - 2$ for every $k$-degenerate graph $G$. %The arboricity $a(G)$ of a graph $G$ is the minimum number of forests into which its set of edges can be partitioned. %If $G$ is $k$-degenerate, then $a(G) \le k \le 2a(G) - 1$. We show in this paper that $i_g(G) \le \lfloor\frac{3Δ(G) - a(G)}{2}\rfloor + 8a(G) - 2$ for every graph $G$, where $a(G)$ stands for the arboricity of $G$, thus improving the bound given by Andres since $a(G) \le k$ for every $k$-degenerate graph $G$. Since there exists graphs with $i_g(G) \ge \lceil\frac{3Δ(G)}{2}\rceil$, the multiplicative constant of our bound is best possible.
Effective Capacity of Delay Constrained Cognitive Radio Links Exploiting Primary Feedback
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we analyze the performance of a secondary link in a cognitive radio (CR) system operating under statistical quality of service (QoS) delay constraints. In particular, we quantify analytically the performance improvement for the secondary user (SU) when applying a feedback based sensing scheme under the "SINR Interference" model. We leverage the concept of effective capacity (EC) introduced earlier in the literature to quantify the wireless link performance under delay constraints, in an attempt to opportunistically support real-time applications. Towards this objective, we study a two-link network, a single secondary link and a primary network abstracted to a single primary link, with and without primary feedback exploitation. We analytically prove that exploiting primary feedback at the secondary transmitter improves the EC of the secondary user and decreases the secondary user average transmitted power. Finally, we present numerical results that support our analytical results.
Virtual learning: possibilities and realization
Venue: arXiv cs.CY 2013
Year: 2013

The virtual learning in University Education is the learning which is presented by set of integrated information and pedagogical technologies, in a process of interaction between subjects and objects as the virtual educational resources. This interaction characterize as the set of dialectically interconnected fields of human activity (intellectual, emotional and figurative, cultural, social). The virtual educational resources, possibility of their adaptation to student subjectivity, and realization in the conditions of University education are the main issues of this article.
Polar Decomposition of Mutual Information over Complex-Valued Channels
Venue: arXiv cs.IT 2013
Year: 2013

A polar decomposition of mutual information between a complex-valued channel's input and output is proposed for a input whose amplitude and phase are independent of each other. The mutual information is symmetrically decomposed into three terms: an amplitude term, a phase term, and a cross term, whereby the cross term is negligible at high signal-to-noise ratio. Theoretical bounds of the amplitude and phase terms are derived for additive white Gaussian noise channels with Gaussian inputs. This decomposition is then applied to the recently proposed amplitude phase shift keying with product constellation (product-APSK) inputs. It shows from an information theoretical perspective that coded modulation schemes using product-APSK are able to outperform those using conventional quadrature amplitude modulation (QAM), meanwhile maintain a low complexity.
Improving Lower Bounds for the Quadratic Assignment Problem by applying a Distributed Dual Ascent Algorithm
Venue: arXiv cs.DC 2013
Year: 2013

The application of the Reformulation Linearization Technique (RLT) to the Quadratic Assignment Problem (QAP) leads to a tight linear relaxation with huge dimensions that is hard to solve. Previous works found in the literature show that these relaxations combined with branch-and-bound algorithms belong to the state-of-the-art of exact methods for the QAP. For the level 3 RLT (RLT3), using this relaxation is prohibitive in conventional machines for instances with more than 22 locations due to memory limitations. This paper presents a distributed version of a dual ascent algorithm for the RLT3 QAP relaxation that approximately solves it for instances with up to 30 locations for the first time. Although, basically, the distributed algorithm has been implemented on top of its sequential conterpart, some changes, which improved not only the parallel performance but also the quality of solutions, were proposed here. When compared to other lower bounding methods found in the literature, our algorithm generates the best known lower bounds for 26 out of the 28 tested instances, reaching the optimal solution in 18 of them.
On the Structure of Boolean Functions with Small Spectral Norm
Venue: arXiv cs.CC 2013
Year: 2013

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is $\|\hat{f}\|_1=\sum_α|\hat{f}(α)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n \to \{0,1\}$ with $\|\hat{f}\|_1=A$. 1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant. 2. f can be computed by a parity decision tree of size $2^{A^2}n^{2A}$. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) 3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth $A^2 \log s$. 4. For every $0<ε$ there is a parity decision tree of depth $O(A^2 + \log(1/ε))$ and size $2^{O(A^2)} \cdot \min\{1/ε^2,O(\log(1/ε))^{2A}\}$ that ε-approximates f. Furthermore, this tree can be learned, with probability $1-δ$, using $\poly(n,\exp(A^2),1/ε,\log(1/δ))$ membership queries. All the results above also hold (with a slight change in parameters) to functions $f:Z_p^n\to \{0,1\}$.
Fully Dynamic $(1+ε)$-Approximate Matchings
Venue: arXiv cs.DS 2013
Year: 2013

We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sublinear time per update. Our main result is a data structure that maintains a $(1+ε)$ approximation of maximum matching under edge insertions/deletions in worst case $O(\sqrt{m}ε^{-2})$ time per update. This improves the 3/2 approximation given in [Neiman,Solomon,STOC 2013] which runs in similar time. The result is based on two ideas. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible. We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant $ε$ and for graphs with edge weights between 1 and N, we design an algorithm that maintains an $(1+ε)$-approximate maximum weighted matching in $O(\sqrt{m} \log N)$ time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4.9108, and was shown in [Anand,Baswana,Gupta,Sen, FSTTCS 2012, arXiv 2012].
An Efficient Bilinear Pairing-Free Certificateless Two-Party Authenticated Key Agreement Protocol in the eCK Model
Venue: arXiv cs.CR 2013
Year: 2013

Recent study on certificateless authenticated key agreement focuses on bilinear pairing-free certificateless authenticated key agreement protocol. Yet it has got limitations in the aspect of computational amount. So it is important to reduce the number of the scalar multiplication over elliptic curve group in bilinear pairing-free protocols. This paper proposed a new bilinear pairing-free certificateless two-party authenticated key agreement protocol, providing more efficiency among related work and proof under the random oracle model.
OESPA:A Theory of Programming that Support Software Engineering
Venue: arXiv cs.PL 2013
Year: 2013

A new theory of programming is proposed. The theory consists of OE (Operation Expression), SP (Semantic Predicate) and A (Axiom), abbreviated as OESPA. OE is for programming: its syntax is given by BNF formulas and its semantics is defined by axioms on these formulas. Similar to predicates in logic, SP is for describing properties of OE (i.e. programs) and for program property analysis. But SP is different from predicates, it directly relates the final values of variables upon termination of a given OE with initial values of these variables before the same OE. As such, it is feasible to prove or disprove whether a given SP is a property of a given OE by computation based on A (Axioms). SP calculus is proposed for program specification and specification analysis, that is missing in software engineering.
HEER: Hybrid Energy Efficient Reactive Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Sensor Networks (WSNs) consist of numerous sensors which send sensed data to base station. Energy conservation is an important issue for sensor nodes as they have limited power.Many routing protocols have been proposed earlier for energy efficiency of both homogeneous and heterogeneous environments. We can prolong our stability and network lifetime by reducing our energy consumption. In this research paper, we propose a protocol designed for the characteristics of a reactive homogeneous WSNs, HEER (Hybrid Energy Efficient Reactive) protocol. In HEER, Cluster Head(CH) selection is based on the ratio of residual energy of node and average energy of network. Moreover, to conserve more energy, we introduce Hard Threshold (HT) and Soft Threshold (ST). Finally, simulations show that our protocol has not only prolonged the network lifetime but also significantly increased stability period.
ACH: Away Cluster Heads Scheme for Energy Efficient Clustering Protocols in WSNs
Venue: arXiv cs.NI 2013
Year: 2013

This paper deals with the routing protocols for distributed wireless sensor networks. The conventional protocols for WSNs like Low Energy adaptive Clustering Hierarchy (LEACH), Stable Election Protocol (SEP), Threshold Sensitive Energy Efficient Network (TEEN), Distributed Energy Efficient Clustering Protocol (DEEC) may not be optimal. We propose a scheme called Away Cluster Head (ACH) which effectively increases the efficiency of conventional clustering based protocols in terms of stability period and number of packets sent to base station (BS). We have implemented ACH scheme on LEACH, SEP, TEEN and DEEC. Simulation results show that LEACHACH, SEP-ACH, TEEN-ACH and DEEC-ACH performs better than LEACH, SEP, TEEN and DEEC respectively in terms of stability period and number of packets sent to BS. The stability period of the existing protocols prolongs by implementing ACH on them.
Quantified Data Automata on Skinny Trees: an Abstract Domain for Lists
Venue: arXiv cs.PL 2013
Year: 2013

We propose a new approach to heap analysis through an abstract domain of automata, called automatic shapes. The abstract domain uses a particular kind of automata, called quantified data automata on skinny trees (QSDAs), that allows to define universally quantified properties of singly-linked lists. To ensure convergence of the abstract fixed-point computation, we introduce a sub-class of QSDAs called elastic QSDAs, which also form an abstract domain. We evaluate our approach on several list manipulating programs and we show that the proposed domain is powerful enough to prove a large class of these programs correct.
Represent MOD function by low degree polynomial with unbounded one-sided error
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we prove tight lower bounds on the smallest degree of a nonzero polynomial in the ideal generated by $MOD_q$ or $\neg MOD_q$ in the polynomial ring $F_p[x_1, \ldots, x_n]/(x_1^2 = x_1, \ldots, x_n^2 = x_n)$, $p,q$ are coprime, which is called \emph{immunity} over $F_p$. The immunity of $MOD_q$ is lower bounded by $\lfloor (n+1)/2 \rfloor$, which is achievable when $n$ is a multiple of $2q$; the immunity of $\neg MOD_q$ is exactly $\lfloor (n+q-1)/q \rfloor$ for every $q$ and $n$. Our result improves the previous bound $\lfloor \frac{n}{2(q-1)} \rfloor$ by Green. We observe how immunity over $F_p$ is related to $\acc$ circuit lower bound. For example, if the immunity of $f$ over $F_p$ is lower bounded by $n/2 - o(\sqrt{n})$, and $|1_f| = Ω(2^n)$, then $f$ requires $\acc$ circuit of exponential size to compute.
Evolution to 200G Passive Optical Network
Venue: arXiv cs.NI 2013
Year: 2013

New generation passive optical network aims at providing more than 100 Gb/s capacity. Thanks to recent progress enabling a variety of optical transceivers up to 40 Gb/s, many evolution possibilities to 200G PONs (passive optical network) could be investigated. This work proposes two directly deployable cases of evolution to 200G PON based on the combination of these improved optical transceivers and WDM (wavelength division multiplexing). The physical layer of the optical network has been simulated with OptiSystem software to show the communication links performances behavior when considering key components parameters in order to achieve good network design for a given area. The complexity of the proposed architectures and financial cost comparisons are also discussed.
Closed-Form Rate Outage Probability for OFDMA Multi-Hop Broadband Wireless Networks under Nakagami-m Channels
Venue: arXiv cs.NI 2013
Year: 2013

Rate outage probability is an important performance metric to measure the level of quality of service (QoS) in the 4th Generation (4G) broadband access networks. Thus, in this paper, we calculate a closed form expression of the rate outage probability for a given user in a down-link multi-hop OFDMA-based system encountered as a result of links channel variations. The channel random behavior on different subcarriers allocated to a given user is assumed to follow independent non-identical Nakagami-m distributions. Besides the rate outage probability formulas for single hop and multi-hop networks, we also derive a novel closed form formulas for the moment generating function, probability distribution function (pdf), and the cumulative distribution function (cdf) of a product of independent non-identical Gamma distributed random variables (RVs). These RVs are functions of the attainable signal-to-noise power ratio (SNR) on the allocated group of subcarriers. For single-hop scenario, inspired by the rate outage probability closed formula, we formulate an optimization problem in which we allocate subcarriers to users such that the total transmission rate is maximized while catering for fairness for all users. In the proposed formulation, fairness is considered by guaranteeing a minimum rate outage probability for each admitted user