OpenRaiser/Intern-Atlas huggingface dataset:
Achieving the Capacity of any DMC using only Polar Codes
Venue: arXiv cs.IT 2012
Year: 2012

We construct a channel coding scheme to achieve the capacity of any discrete memoryless channel based solely on the techniques of polar coding. In particular, we show how source polarization and randomness extraction via polarization can be employed to "shape" uniformly-distributed i.i.d. random variables into approximate i.i.d. random variables distributed ac- cording to the capacity-achieving distribution. We then combine this shaper with a variant of polar channel coding, constructed by the duality with source coding, to achieve the channel capacity. Our scheme inherits the low complexity encoder and decoder of polar coding. It differs conceptually from Gallager's method for achieving capacity, and we discuss the advantages and disadvantages of the two schemes. An application to the AWGN channel is discussed.
Necessity as justified truth
Venue: arXiv cs.LO 2012
Year: 2012

We present a logic for the reasoning about necessity and justifications which is independent from relational semantics. We choose the concept of justification -- coming from a class of "Justification Logics" (Artemov 2008, Fitting 2009) -- as the primitive notion on which the concept of necessity is based. Our axiomatization extends Suszko's non-Fregean logic SCI (Brown, Suszko 1972) by basic axioms from Justification Logic, axioms for quantification over propositions and over justifications, and some further principles. The core axiom is: $φ$ is necessarily true iff there is a justification for $φ$. That is, necessity is first-order definable by means of justifications. Instead of defining purely algebraic models in the style of (Brown, Suszko 1972) we extend the semantics investigated in (Lewitzka 2012) by some algebraic structure for dealing with justifications and prove soundness and completeness of our deductive system. Moreover, we are able to restore the modal logic principle of Necessitation if we add the axiom schema $\squareφ\to \square\squareφ$ and a rule of Axiom Necessitation to our system. As a main result, we show that the modal logics S4 and S5 can be captured by our semantics if we impose the corresponding modal logic principles as additional semantic constraints. This will follow from proof-theoretic considerations and from our completeness theorems. For the system S4 we present also a purely model-theoretic proof.
A Method for the Characterisation of Observer Effects and its Application to OML
Venue: arXiv cs.PF 2012
Year: 2012

In all measurement campaigns, one needs to assert that the instrumentation tools do not significantly impact the system being monitored. This is critical to future claims based on the collected data and is sometimes overseen in experimental studies. We propose a method to evaluate the potential "observer effect" of an instrumentation system, and apply it to the OMF Measurement Library (OML). OML allows the instrumentation of almost any software to collect any type of measurements. As it is increasingly being used in networking research, it is important to characterise possible biases it may introduce in the collected metrics. Thus, we study its effect on multiple types of reports from various applications commonly used in wireless research. To this end, we designed experiments comparing OML-instrumented software with their original flavours. Our analyses of the results from these experiments show that, with an appropriate reporting setup, OML has no significant impact on the instrumented applications, and may even improve some of their performances in specifics cases. We discuss our methodology and the implication of using OML, and provide guidelines on instrumenting off-the-shelf software.
Machine Recognition of Hand Written Characters using Neural Networks
Venue: arXiv cs.AI 2012
Year: 2012

Even today in Twenty First Century Handwritten communication has its own stand and most of the times, in daily life it is globally using as means of communication and recording the information like to be shared with others. Challenges in handwritten characters recognition wholly lie in the variation and distortion of handwritten characters, since different people may use different style of handwriting, and direction to draw the same shape of the characters of their known script. This paper demonstrates the nature of handwritten characters, conversion of handwritten data into electronic data, and the neural network approach to make machine capable of recognizing hand written characters.
The permanent, graph gadgets and counting solutions for certain types of planar formulas
Venue: arXiv cs.CC 2012
Year: 2012

In this paper, we build on the idea of Valiant \cite{Val79a} and Ben-Dor/Halevi \cite{Ben93}, that is, to count the number of satisfying solutions of a boolean formula via computing the permanent of a specially constructed matrix. We show that the Desnanot-Jacobi identity ($\dji$) prevents Valiant's original approach to achieve a parsimonious reduction to the permanent over a field of characteristic two. As the next step, since the computation of the permanent is $#\classP$-complete, we make use of the equality of the permanent and the number of perfect matchings in an unweighted graph's bipartite double cover. Whenever this bipartite double cover (BDC) is planar, the number of perfect matchings can be counted in polynomial time using Kasteleyn's algorithm \cite{Kas67}. To enforce planarity of the BDC, we replace Valiant's original gadgets with new gadgets and describe what properties these gadgets must have. We show that the property of \textit{circular planarity} plays a crucial role to find the correct gadgets for a counting problem. To circumvent the $\dji$-barrier, we switch over to fields $\mathbb{Z}/p\mathbb{Z}$, for a prime $p > 2$. With this approach we are able to count the number of solutions for $\forestdreisat$ formulas in randomized polynomial time. Finally, we present a conjecture that states which kind of generalized gadgets can not be found, since otherwise one could prove $\classRP = \classNP$. The conjecture establishes a relationship between the determinants of the minors of a graph $\grG$'s adjacency matrix and the \textit{circular planar} structure of $\grG$'s BDC regarding a given set of nodes.
The weakening relationship between the Impact Factor and papers' citations in the digital age
Venue: arXiv cs.DL 2012
Year: 2012

Historically, papers have been physically bound to the journal in which they were published but in the electronic age papers are available individually, no longer tied to their respective journals. Hence, papers now can be read and cited based on their own merits, independently of the journal's physical availability, reputation, or Impact Factor. We compare the strength of the relationship between journals' Impact Factors and the actual citations received by their respective papers from 1902 to 2009. Throughout most of the 20th century, papers' citation rates were increasingly linked to their respective journals' Impact Factors. However, since 1990, the advent of the digital age, the strength of the relation between Impact Factors and paper citations has been decreasing. This decrease began sooner in physics, a field that was quicker to make the transition into the electronic domain. Furthermore, since 1990, the proportion of highly cited papers coming from highly cited journals has been decreasing, and accordingly, the proportion of highly cited papers not coming from highly cited journals has also been increasing. Should this pattern continue, it might bring an end to the use of the Impact Factor as a way to evaluate the quality of journals, papers and researchers.
New Analysis and Algorithm for Learning with Drifting Distributions
Venue: arXiv cs.LG 2012
Year: 2012

We present a new analysis of the problem of learning with drifting distributions in the batch setting using the notion of discrepancy. We prove learning bounds based on the Rademacher complexity of the hypothesis set and the discrepancy of distributions both for a drifting PAC scenario and a tracking scenario. Our bounds are always tighter and in some cases substantially improve upon previous ones based on the $L_1$ distance. We also present a generalization of the standard on-line to batch conversion to the drifting scenario in terms of the discrepancy and arbitrary convex combinations of hypotheses. We introduce a new algorithm exploiting these learning guarantees, which we show can be formulated as a simple QP. Finally, we report the results of preliminary experiments demonstrating the benefits of this algorithm.
CDMA Based Interconnect Mechanism for SOPC
Venue: arXiv cs.ET 2012
Year: 2012

The Network-on-chip (NoC) designs consisting of large pack of Intellectual Property (IP) blocks (cores) on the same silicon die is becoming technically possible nowadays. But, the communication between the IP Cores is the main issue in recent years. This paper presents the design of a Code Division Multiple Access (CDMA) based wrapper interconnect as a component of System on programmable chip (SOPC) builder to communicate between IP cores. In the proposal, only bus lines that carry address and data signals are CDMA coded. CDMA technology has better data integrity, channel continuity, channel isolation, and also mainly it reduces the no.of lines in the bus architecture for transmitting the data from master to slave.
Sparse Signal Separation in Redundant Dictionaries
Venue: arXiv cs.IT 2012
Year: 2012

We formulate a unified framework for the separation of signals that are sparse in "morphologically" different redundant dictionaries. This formulation incorporates the so-called "analysis" and "synthesis" approaches as special cases and contains novel hybrid setups. We find corresponding coherence-based recovery guarantees for an l1-norm based separation algorithm. Our results recover those reported in Studer and Baraniuk, ACHA, submitted, for the synthesis setting, provide new recovery guarantees for the analysis setting, and form a basis for comparing performance in the analysis and synthesis settings. As an aside our findings complement the D-RIP recovery results reported in Candès et al., ACHA, 2011, for the "analysis" signal recovery problem: minimize_x ||Ψx||_1 subject to ||y - Ax||_2 \leq ε, by delivering corresponding coherence-based recovery results.
Observer Design for Takagi-Sugeno Descriptor System with Lipschitz Constraints
Venue: arXiv cs.SY 2012
Year: 2012

This paper investigates the design problem of observers for nonlinear descriptor systems described by Takagi-Sugeno (TS) system; Depending on the available knowledge on the premise variables two cases are considered. First a TS descriptor system with measurables premises variables are proposed. Second, an observer design which satisfying the Lipschitz condition is proposed when the premises variables are unmeasurables. The convergence of the state estimation error is studied using the Lyapunov theory and the stability conditions are given in terms of Linear Matrix Inequalities (LMIs). Examples are included to illustrate those methods.
The View-Update Problem for Indefinite Databases
Venue: arXiv cs.DB 2012
Year: 2012

This paper introduces and studies a declarative framework for updating views over indefinite databases. An indefinite database is a database with null values that are represented, following the standard database approach, by a single null constant. The paper formalizes views over such databases as indefinite deductive databases, and defines for them several classes of database repairs that realize view-update requests. Most notable is the class of constrained repairs. Constrained repairs change the database "minimally" and avoid making arbitrary commitments. They narrow down the space of alternative ways to fulfill the view-update request to those that are grounded, in a certain strong sense, in the database, the view and the view-update request.
An Achievable Rate Region for Three-Pair Interference Channels with Noise
Venue: arXiv cs.IT 2012
Year: 2012

An achievable rate region for certain noisy three-user-pair interference channels is proposed. The channel class under consideration generalizes the three-pair deterministic interference channel (3-DIC) in the same way as the Telatar-Tse noisy two-pair interference channel generalizes the El Gamal-Costa injective channel. Specifically, arbitrary noise is introduced that acts on the combined interference signal before it affects the desired signal. This class of channels includes the Gaussian case. The rate region includes the best-known inner bound on the 3-DIC capacity region, dominates treating interference as noise, and subsumes the Han-Kobayashi region for the two-pair case.
Translating the Cantor set by a random
Venue: arXiv cs.CC 2012
Year: 2012

We determine the constructive dimension of points in random translates of the Cantor set. The Cantor set "cancels randomness" in the sense that some of its members, when added to Martin-Lof random reals, identify a point with lower constructive dimension than the random itself. In particular, we find the Hausdorff dimension of the set of points in a Cantor set translate with a given constructive dimension.
Perfect Secrecy Systems Immune to Spoofing Attacks
Venue: arXiv cs.CR 2012
Year: 2012

We present novel perfect secrecy systems that provide immunity to spoofing attacks under equiprobable source probability distributions. On the theoretical side, relying on an existence result for $t$-designs by Teirlinck, our construction method constructively generates systems that can reach an arbitrary high level of security. On the practical side, we obtain, via cyclic difference families, very efficient constructions of new optimal systems that are onefold secure against spoofing. Moreover, we construct, by means of $t$-designs for large values of $t$, the first near-optimal systems that are 5- and 6-fold secure as well as further systems with a feasible number of keys that are 7-fold secure against spoofing. We apply our results furthermore to a recently extended authentication model, where the opponent has access to a verification oracle. We obtain this way novel perfect secrecy systems with immunity to spoofing in the verification oracle model.
Clustering is difficult only when it does not matter
Venue: arXiv cs.LG 2012
Year: 2012

Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clustered well}. More generally, despite the ubiquity and the great importance of clustering, we still do not have a satisfactory mathematical theory of clustering. In order to properly understand clustering, it is clearly necessary to develop a solid theoretical basis for the area. For example, from the perspective of computational complexity theory the clustering problem seems very hard. Numerous papers introduce various criteria and numerical measures to quantify the quality of a given clustering. The resulting conclusions are pessimistic, since it is computationally difficult to find an optimal clustering of a given data set, if we go by any of these popular criteria. In contrast, the practitioners' perspective is much more optimistic. Our explanation for this disparity of opinions is that complexity theory concentrates on the worst case, whereas in reality we only care for data sets that can be clustered well. We introduce a theoretical framework of clustering in metric spaces that revolves around a notion of "good clustering". We show that if a good clustering exists, then in many cases it can be efficiently found. Our conclusion is that contrary to popular belief, clustering should not be considered a hard task.
Investigating Warp Size Impact in GPUs
Venue: arXiv cs.AR 2012
Year: 2012

There are a number of design decisions that impact a GPU's performance. Among such decisions deciding the right warp size can deeply influence the rest of the design. Small warps reduce the performance penalty associated with branch divergence at the expense of a reduction in memory coalescing. Large warps enhance memory coalescing significantly but also increase branch divergence. This leaves designers with two choices: use a small warps and invest in finding new solutions to enhance coalescing or use large warps and address branch divergence employing effective control-flow solutions. In this work our goal is to investigate the answer to this question. We analyze warp size impact on memory coalescing and branch divergence. We use our findings to study two machines: a GPU using small warps but equipped with excellent memory coalescing (SW+) and a GPU using large warps but employing an MIMD engine immune from control-flow costs (LW+). Our evaluations show that building coalescing-enhanced small warp GPUs is a better approach compared to pursuing a control-flow enhanced large warp GPU.
SubGraD- An Approach for Subgraph Detection
Venue: arXiv cs.DS 2012
Year: 2012

A new approach of graph matching is introduced in this paper, which efficiently solves the problem of graph isomorphism and subgraph isomorphism. In this paper we are introducing a new approach called SubGraD, for query graph detection in source graph. Firstly consider the model graph (query graph) and make the possible sets called model sets starting from the chosen initial node or starter. Similarly, for the source graph (reference graph), all the possible sets called reference sets could be made. Our aim is to make the reference set on the basis of the model set. If it is possible to make the reference set, then it is said that query graph has been detected in the source graph.
Ber analysis of iterative turbo encoded miso wireless communication system under implementation of q-ostbc scheme
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a comprehensive study has been made to evaluate the performance of a MISO wireless communication system. The 4-by-1 spatially multiplexed Turbo encoded system under investigation incorporates Quasi-orthogonal space-time block coding (Q-STBC) and ML signal detection schemes under QPSK, QAM, 16PSK and 16QAM digital modulations. The simulation results elucidate that a significant improvement of system performance is achieved in QAM modulation. The results are also indicative of noticeable system performance enhancement with increasing number of iterations in Turbo encoding/decoding scheme.
Security of Patched DNS
Venue: arXiv cs.CR 2012
Year: 2012

In spite of the availability of DNSSEC, which protects against cache poisoning even by MitM attackers, many caching DNS resolvers still rely for their security against poisoning on merely validating that DNS responses contain some 'unpredictable' values, copied from the re- quest. These values include the 16 bit identifier field, and other fields, randomised and validated by different 'patches' to DNS. We investigate the prominent patches, and show how attackers can circumvent all of them, namely: - We show how attackers can circumvent source port randomisation, in the (common) case where the resolver connects to the Internet via different NAT devices. - We show how attackers can circumvent IP address randomisation, using some (standard-conforming) resolvers. - We show how attackers can circumvent query randomisation, including both randomisation by prepending a random nonce and case randomisation (0x20 encoding). We present countermeasures preventing our attacks; however, we believe that our attacks provide additional motivation for adoption of DNSSEC (or other MitM-secure defenses).
Joint Channel Estimation and Data Detection for Multihop OFDM Relaying System under Unknown Channel Orders and Doppler Frequencies
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, channel estimation and data detection for multihop relaying orthogonal frequency division multiplexing (OFDM) system is investigated under time-varying channel. Different from previous works, which highly depend on the statistical information of the doubly-selective channel (DSC) and noise to deliver accurate channel estimation and data detection results, we focus on more practical scenarios with unknown channel orders and Doppler frequencies. Firstly, we integrate the multilink, multihop channel matrices into one composite channel matrix. Then, we formulate the unknown channel using generalized complex exponential basis expansion model (GCE-BEM) with a large oversampling factor to introduce channel sparsity on delay-Doppler domain. To enable the identification of nonzero entries, sparsity enhancing Gaussian distributions with Gamma hyperpriors are adopted. An iterative algorithm is developed under variational inference (VI) framework. The proposed algorithm iteratively estimate the channel, recover the unknown data using Viterbi algorithm and learn the channel and noise statistical information, using only limited number of pilot subcarrier in one OFDM symbol. Simulation results show that, without any statistical information, the performance of the proposed algorithm is very close to that of the optimal channel estimation and data detection algorithm, which requires specific information on system structure, channel tap positions, channel lengths, Doppler shifts as well as noise powers.
FASTSUBS: An Efficient and Exact Procedure for Finding the Most Likely Lexical Substitutes Based on an N-gram Language Model
Venue: arXiv cs.CL 2012
Year: 2012

Lexical substitutes have found use in areas such as paraphrasing, text simplification, machine translation, word sense disambiguation, and part of speech induction. However the computational complexity of accurately identifying the most likely substitutes for a word has made large scale experiments difficult. In this paper I introduce a new search algorithm, FASTSUBS, that is guaranteed to find the K most likely lexical substitutes for a given word in a sentence based on an n-gram language model. The computation is sub-linear in both K and the vocabulary size V. An implementation of the algorithm and a dataset with the top 100 substitutes of each token in the WSJ section of the Penn Treebank are available at http://goo.gl/jzKH0.
Improved Implementation of Point Location in General Two-Dimensional Subdivisions
Venue: arXiv cs.CG 2012
Year: 2012

We present a major revamp of the point-location data structure for general two-dimensional subdivisions via randomized incremental construction, implemented in CGAL, the Computational Geometry Algorithms Library. We can now guarantee that the constructed directed acyclic graph G is of linear size and provides logarithmic query time. Via the construction of the Voronoi diagram for a given point set S of size n, this also enables nearest-neighbor queries in guaranteed O(log n) time. Another major innovation is the support of general unbounded subdivisions as well as subdivisions of two-dimensional parametric surfaces such as spheres, tori, cylinders. The implementation is exact, complete, and general, i.e., it can also handle non-linear subdivisions. Like the previous version, the data structure supports modifications of the subdivision, such as insertions and deletions of edges, after the initial preprocessing. A major challenge is to retain the expected O(n log n) preprocessing time while providing the above (deterministic) space and query-time guarantees. We describe an efficient preprocessing algorithm, which explicitly verifies the length L of the longest query path in O(n log n) time. However, instead of using L, our implementation is based on the depth D of G. Although we prove that the worst case ratio of D and L is Theta(n/log n), we conjecture, based on our experimental results, that this solution achieves expected O(n log n) preprocessing time.
Isometry and Automorphisms of Constant Dimension Codes
Venue: arXiv cs.IT 2012
Year: 2012

We define linear and semilinear isometry for general subspace codes, used for random network coding. Furthermore, some results on isometry classes and automorphism groups of known constant dimension code constructions are derived.