OpenRaiser/Intern-Atlas huggingface dataset:
Reversible Logic Based Concurrent Error Detection Methodology For Emerging Nanocircuits
Venue: arXiv cs.AR 2011
Year: 2011

Reversible logic has promising applications in emerging nanotechnologies, such as quantum computing, quantum dot cellular automata and optical computing, etc. Faults in reversible logic circuits that result in multi-bit error at the outputs are very tough to detect, and thus in literature, researchers have only addressed the problem of online testing of faults that result single-bit error at the outputs based on parity preserving logic. In this work, we propose a methodology for the concurrent error detection in reversible logic circuits to detect faults that can result in multi-bit error at the outputs. The methodology is based on the inverse property of reversible logic and is termed as 'inverse and compare' method. By using the inverse property of reversible logic, all the inputs can be regenerated at the outputs. Thus, by comparing the original inputs with the regenerated inputs, the faults in reversible circuits can be detected. Minimizing the garbage outputs is one of the main goals in reversible logic design and synthesis. We show that the proposed methodology results in 'garbageless' reversible circuits. A design of reversible full adder that can be concurrently tested for multi-bit error at the outputs is illustrated as the application of the proposed scheme. Finally, we showed the application of the proposed scheme of concurrent error detection towards fault detection in quantum dot cellular automata (QCA) emerging nanotechnology.
Degree and connectivity of the Internet's scale-free topology
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we theoretically and empirically study the degree and connectivity of the Internet's scale-free topology at the autonomous system (AS) level. The basic features of the scale-free network have influence on the normalization constant of the degree distribution p(k). We develop a mathematics model of the Internet's scale-free topology. On this model we theoretically get the formulas of the average degree, the ratios of the kmin-degree (minimum degree) nodes and the kmax-degree (maximum degree) nodes, the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. We find the average degree is larger for smaller power-law exponent λ and larger minimum or maximum degree. The ratio of the kmin-degree nodes is larger for larger λ and smaller kmin or kmax. The ratio of the kmax-degree ones is larger for smaller λ and kmax or larger kmin. The richer nodes hold most of the total degrees of the AS-level Internet topology. In addition, we reveal the ratio of the kmin-degree nodes or the rate of the increase of the average degree has power-law decay with the increase of the kmin. The ratio of the kmax-degree nodes has power-law decay with the increase of the kmax, and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the '73/27 rule'). At last, we empirically calculate, based on empirical data extracted from BGP, the average degree and the ratio and fraction using our method and other methods, and find that our method is rigorous and effective for the AS-level Internet topology.
Peak Reduction and Clipping Mitigation by Compressive Sensing
Venue: arXiv cs.IT 2011
Year: 2011

This work establishes the design, analysis, and fine-tuning of a Peak-to-Average-Power-Ratio (PAPR) reducing system, based on compressed sensing at the receiver of a peak-reducing sparse clipper applied to an OFDM signal at the transmitter. By exploiting the sparsity of the OFDM signal in the time domain relative to a pre-defined clipping threshold, the method depends on partially observing the frequency content of extremely simple sparse clippers to recover the locations, magnitudes, and phases of the clipped coefficients of the peak-reduced signal. We claim that in the absence of optimization algorithms at the transmitter that confine the frequency support of clippers to a predefined set of reserved-tones, no other tone-reservation method can reliably recover the original OFDM signal with such low complexity. Afterwards we focus on designing different clipping signals that can embed a priori information regarding the support and phase of the peak-reducing signal to the receiver, followed by modified compressive sensing techniques for enhanced recovery. This includes data-based weighted {\ell} 1 minimization for enhanced support recovery and phase-augmention for homogeneous clippers followed by Bayesian techniques. We show that using such techniques for a typical OFDM signal of 256 subcarriers and 20% reserved tones, the PAPR can be reduced by approximately 4.5 dB with a significant increase in capacity compared to a system which uses all its tones for data transmission and clips to such levels. The design is hence appealing from both capacity and PAPR reduction aspects.
Existential witness extraction in classical realizability and via a negative translation
Venue: arXiv cs.LO 2011
Year: 2011

We show how to extract existential witnesses from classical proofs using Krivine's classical realizability---where classical proofs are interpreted as lambda-terms with the call/cc control operator. We first recall the basic framework of classical realizability (in classical second-order arithmetic) and show how to extend it with primitive numerals for faster computations. Then we show how to perform witness extraction in this framework, by discussing several techniques depending on the shape of the existential formula. In particular, we show that in the Sigma01-case, Krivine's witness extraction method reduces to Friedman's through a well-suited negative translation to intuitionistic second-order arithmetic. Finally we discuss the advantages of using call/cc rather than a negative translation, especially from the point of view of an implementation.
Relating Church-Style and Curry-Style Subtyping
Venue: arXiv cs.LO 2011
Year: 2011

Type theories with higher-order subtyping or singleton types are examples of systems where computation rules for variables are affected by type information in the context. A complication for these systems is that bounds declared in the context do not interact well with the logical relation proof of completeness or termination. This paper proposes a natural modification to the type syntax for F-Omega-Sub, adding variable's bound to the variable type constructor, thereby separating the computational behavior of the variable from the context. The algorithm for subtyping in F-Omega-Sub can then be given on types without context or kind information. As a consequence, the metatheory follows the general approach for type systems without computational information in the context, including a simple logical relation definition without Kripke-style indexing by context. This new presentation of the system is shown to be equivalent to the traditional presentation without bounds on the variable type constructor.
High-Confidence Predictions under Adversarial Uncertainty
Venue: arXiv cs.DS 2011
Year: 2011

We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x. First, we study the problem of successfully predicting a single 0 from among the bits of x. In our model we have only one chance to make a prediction, but may do so at a time of our choosing. We describe and motivate this as the problem of a frog who wants to cross a road safely. Letting N_t denote the number of 1s among the first t bits of x, we say that x is "eps-weakly sparse" if lim inf (N_t/t) <= eps. Our main result is a randomized algorithm that, given any eps-weakly sparse sequence x, predicts a 0 of x with success probability as close as desired to 1 - \eps. Thus we can perform this task with essentially the same success probability as under the much stronger assumption that each bit of x takes the value 1 independently with probability eps. We apply this result to show how to successfully predict a bit (0 or 1) under a broad class of possible assumptions on the sequence x. The assumptions are stated in terms of the behavior of a finite automaton M reading the bits of x. We also propose and solve a variant of the well-studied "ignorant forecasting" problem. For every eps > 0, we give a randomized forecasting algorithm S_eps that, given sequential access to a binary sequence x, makes a prediction of the form: "A p fraction of the next N bits will be 1s." (The algorithm gets to choose p, N, and the time of the prediction.) For any fixed sequence x, the forecast fraction p is accurate to within +-eps with probability 1 - eps.
Applications of Stochastic Ordering to Wireless Communications
Venue: arXiv cs.IT 2011
Year: 2011

Stochastic orders are binary relations defined on probability distributions which capture intuitive notions like being larger or being more variable. This paper introduces stochastic ordering of instantaneous SNRs of fading channels as a tool to compare the performance of communication systems over different channels. Stochastic orders unify existing performance metrics such as ergodic capacity, and metrics based on error rate functions for commonly used modulation schemes through their relation with convex, and completely monotonic (c.m.) functions. Toward this goal, performance metrics such as instantaneous error rates of M-QAM and M-PSK modulations are shown to be c.m. functions of the instantaneous SNR, while metrics such as the instantaneous capacity are seen to have a completely monotonic derivative (c.m.d.). It is shown that the commonly used parametric fading distributions for modeling line of sight (LoS), exhibit a monotonicity in the LoS parameter with respect to the stochastic Laplace transform order. Using stochastic orders, average performance of systems involving multiple random variables are compared over different channels, even when closed form expressions for such averages are not tractable. These include diversity combining schemes, relay networks, and signal detection over fading channels with non-Gaussian additive noise, which are investigated herein. Simulations are also provided to corroborate our results.
Design and Implementation of a Secure Web-Based File Exchange Server: Specification Design Document
Venue: arXiv cs.CR 2011
Year: 2011

We report on the software engineering design and implementation of an web- and LDAP-based secure file exchange system with bi-directional authentication of all parties involved in the process that is the user's browsers and the application server mutually authenticate, and the application and database servers authenticate using certificates, credentials, etcs. with the directory service provided by LDAP using open-source technologies.
An Algebra of Synchronous Scheduling Interfaces
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we propose an algebra of synchronous scheduling interfaces which combines the expressiveness of Boolean algebra for logical and functional behaviour with the min-max-plus arithmetic for quantifying the non-functional aspects of synchronous interfaces. The interface theory arises from a realisability interpretation of intuitionistic modal logic (also known as Curry-Howard-Isomorphism or propositions-as-types principle). The resulting algebra of interface types aims to provide a general setting for specifying type-directed and compositional analyses of worst-case scheduling bounds. It covers synchronous control flow under concurrent, multi-processing or multi-threading execution and permits precise statements about exactness and coverage of the analyses supporting a variety of abstractions. The paper illustrates the expressiveness of the algebra by way of some examples taken from network flow problems, shortest-path, task scheduling and worst-case reaction times in synchronous programming.
A Few Considerations on Structural and Logical Composition in Specification Theories
Venue: arXiv cs.LO 2011
Year: 2011

Over the last 20 years a large number of automata-based specification theories have been proposed for modeling of discrete,real-time and probabilistic systems. We have observed a lot of shared algebraic structure between these formalisms. In this short abstract, we collect results of our work in progress on describing and systematizing the algebraic assumptions in specification theories.
Mobility Control for Machine-to-Machine LTE Systems
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we propose an efficient mobility control algorithm for the downlink multi-cell orthogonal frequency division multiplexing access (OFDMA) system for co-channel interference reduction. It divides each cell into several areas. The mobile nodes in each area find their own optimal position according to their present location. Both the signal to interference plus noise ratio (SINR) and the capacity for each node are increased by the proposed mobility control algorithm. Simulation results say that, even the frequency reuse factor (FRF) is equal to 1, the average capacity is improved after applying the mobility control algorithm, compared to existing partial frequency reuse (PFR) scheme.
Source Optimization in MISO Relaying with Channel Mean Feedback: A Stochastic Ordering Approach
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the optimum source transmission strategy to maximize the capacity of a multiple-input single-output (MISO) amplify-and-forward relay channel, assuming source-relay channel mean feedback at the source. The challenge here is that relaying introduces a nonconvex structure in the objective function, thereby excluding the possible use of previous methods dealing with mean feedback that generally rely on the concavity of the objective function. A novel method is employed, which divides the feasible set into two subsets and establishes the optimum from one of them by comparison. As such, the optimization is transformed into the comparison of two nonnegative random variables in the Laplace transform order, which is one of the important stochastic orders. It turns out that the optimum transmission strategy is to transmit along the known channel mean and its orthogonal eigenchannels. The condition for rank-one precoding (beamforming) to achieve capacity is also determined. Our results subsume those for traditional MISO precoding with mean feedback.
A zero-one SUBEXP-dimension law for BPP
Venue: arXiv cs.CC 2011
Year: 2011

We show that BPP has either SUBEXP-dimension zero (randomness is easy) or BPP=EXP (randomness is intractable).
Opportunistic Buffered Decode-Wait-and-Forward (OBDWF) Protocol for Mobile Wireless Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose an opportunistic buffered decode-wait-and-forward (OBDWF) protocol to exploit both relay buffering and relay mobility to enhance the system throughput and the end-to-end packet delay under bursty arrivals. We consider a point-to-point communication link assisted by K mobile relays. We illustrate that the OBDWF protocol could achieve a better throughput and delay performance compared with existing baseline systems such as the conventional dynamic decode-and-forward (DDF) and amplified-and-forward (AF) protocol. In addition to simulation performance, we also derived closed-form asymptotic throughput and delay expressions of the OBDWF protocol. Specifically, the proposed OBDWF protocol achieves an asymptotic throughput O(logK) with O(1) total transmit power in the relay network. This is a significant gain compared with the best known performance in conventional protocols (O(logK) throughput with O(K) total transmit power). With bursty arrivals, we show that both the stability region and average delay of the proposed OBDWF protocol can achieve order-wise performance gain O(K) compared with conventional DDF protocol.
Compressive Sensing Using the Entropy Functional
Venue: arXiv cs.IT 2011
Year: 2011

In most compressive sensing problems l1 norm is used during the signal reconstruction process. In this article the use of entropy functional is proposed to approximate the l1 norm. A modified version of the entropy functional is continuous, differentiable and convex. Therefore, it is possible to construct globally convergent iterative algorithms using Bregman's row action D-projection method for compressive sensing applications. Simulation examples are presented.
Cooperative Regenerating Codes for Distributed Storage Systems
Venue: arXiv cs.IT 2011
Year: 2011

When there are multiple node failures in a distributed storage system, regenerating the failed storage nodes individually in a one-by-one manner is suboptimal as far as repair-bandwidth minimization is concerned. If data exchange among the newcomers is enabled, we can get a better tradeoff between repair bandwidth and the storage per node. An explicit and optimal construction of cooperative regenerating code is illustrated.
Parsimonious Flooding in Geometric Random-Walks
Venue: arXiv cs.SI 2011
Year: 2011

We study the information spreading yielded by the \emph{(Parsimonious) $1$-Flooding Protocol} in geometric Mobile Ad-Hoc Networks. We consider $n$ agents on a convex plane region of diameter $D$ performing independent random walks with move radius $ρ$. At any time step, every active agent $v$ informs every non-informed agent which is within distance $R$ from $v$ ($R>0$ is the transmission radius). An agent is only active at the time step immediately after the one in which has been informed and, after that, she is removed. At the initial time step, a source agent is informed and we look at the \emph{completion time} of the protocol, i.e., the first time step (if any) in which all agents are informed. This random process is equivalent to the well-known \emph{Susceptible-Infective-Removed ($SIR$}) infection process in Mathematical Epidemiology. No analytical results are available for this random process over any explicit mobility model. The presence of removed agents makes this process much more complex than the (standard) flooding. We prove optimal bounds on the completion time depending on the parameters $n$, $D$, $R$, and $ρ$. The obtained bounds hold with high probability. We remark that our method of analysis provides a clear picture of the dynamic shape of the information spreading (or infection wave) over the time.
Efficient Algorithms for Searching Optimal Shortened Cyclic Single-Burst-Correcting Codes
Venue: arXiv cs.DM 2011
Year: 2011

In a previous work it was shown that the best measure for the efficiency of a single burst-correcting code is obtained using the Gallager bound as opposed to the Reiger bound. In this paper, an efficient algorithm that searches for the best (shortened) cyclic burst-correcting codes is presented. Using this algorithm, extensive tables that either tie existing constructions or improve them are obtained for burst lengths up to b=10.
Relating Sequent Calculi for Bi-intuitionistic Propositional Logic
Venue: arXiv cs.LO 2011
Year: 2011

Bi-intuitionistic logic is the conservative extension of intuitionistic logic with a connective dual to implication. It is sometimes presented as a symmetric constructive subsystem of classical logic. In this paper, we compare three sequent calculi for bi-intuitionistic propositional logic: (1) a basic standard-style sequent calculus that restricts the premises of implication-right and exclusion-left inferences to be single-conclusion resp. single-assumption and is incomplete without the cut rule, (2) the calculus with nested sequents by Gore et al., where a complete class of cuts is encapsulated into special "unnest" rules and (3) a cut-free labelled sequent calculus derived from the Kripke semantics of the logic. We show that these calculi can be translated into each other and discuss the ineliminable cuts of the standard-style sequent calculus.
Compressed String Dictionaries
Venue: arXiv cs.DS 2011
Year: 2011

The problem of storing a set of strings --- a string dictionary --- in compact form appears naturally in many cases. While classically it has represented a small part of the whole data to be processed (e.g., for Natural Language processing or for indexing text collections), more recent applications in Web engines, Web mining, RDF graphs, Internet routing, Bioinformatics, and many others, make use of very large string dictionaries, whose size is a significant fraction of the whole data. Thus novel approaches to compress them efficiently are necessary. In this paper we experimentally compare time and space performance of some existing alternatives, as well as new ones we propose. We show that space reductions of up to 20% of the original size of the strings is possible while supporting fast dictionary searches.
Reduce to the Max: A Simple Approach for Massive-Scale Privacy-Preserving Collaborative Network Measurements (Extended Version)
Venue: arXiv cs.NI 2011
Year: 2011

Privacy-preserving techniques for distributed computation have been proposed recently as a promising framework in collaborative inter-domain network monitoring. Several different approaches exist to solve such class of problems, e.g., Homomorphic Encryption (HE) and Secure Multiparty Computation (SMC) based on Shamir's Secret Sharing algorithm (SSS). Such techniques are complete from a computation-theoretic perspective: given a set of private inputs, it is possible to perform arbitrary computation tasks without revealing any of the intermediate results. In fact, HE and SSS can operate also on secret inputs and/or provide secret outputs. However, they are computationally expensive and do not scale well in the number of players and/or in the rate of computation tasks. In this paper we advocate the use of "elementary" (as opposite to "complete") Secure Multiparty Computation (E-SMC) procedures for traffic monitoring. E-SMC supports only simple computations with private input and public output, i.e., it can not handle secret input nor secret (intermediate) output. Such a simplification brings a dramatic reduction in complexity and enables massive-scale implementation with acceptable delay and overhead. Notwithstanding its simplicity, we claim that an E-SMC scheme is sufficient to perform a great variety of computation tasks of practical relevance to collaborative network monitoring, including, e.g., anonymous publishing and set operations. This is achieved by combining a E-SMC scheme with data structures like Bloom Filters and bitmap strings.
An Overview of the Security Concerns in Enterprise Cloud Computing
Venue: arXiv cs.CR 2011
Year: 2011

Deploying cloud computing in an enterprise infrastructure bring significant security concerns. Successful implementation of cloud computing in an enterprise requires proper planning and understanding of emerging risks, threats, vulnerabilities, and possible countermeasures. We believe enterprise should analyze the company/organization security risks, threats, and available countermeasures before adopting this technology. In this paper, we have discussed security risks and concerns in cloud computing and enlightened steps that an enterprise can take to reduce security risks and protect their resources. We have also explained cloud computing strengths/benefits, weaknesses, and applicable areas in information risk management.
Geometric Models with Co-occurrence Groups
Venue: arXiv cs.CV 2011
Year: 2011

A geometric model of sparse signal representations is introduced for classes of signals. It is computed by optimizing co-occurrence groups with a maximum likelihood estimate calculated with a Bernoulli mixture model. Applications to face image compression and MNIST digit classification illustrate the applicability of this model.