OpenRaiser/Intern-Atlas huggingface dataset:
Phase-Quantized Block Noncoherent Communication
Venue: arXiv cs.IT 2011
Year: 2011

Analog-to-digital conversion (ADC) is a key bottleneck in scaling DSP-centric receiver architectures to multiGigabit/s speeds. Recent information-theoretic results, obtained under ideal channel conditions (perfect synchronization, no dispersion), indicate that low-precision ADC (1-4 bits) could be a suitable choice for designing such high speed systems. In this work, we study the impact of employing low-precision ADC in a {\it carrier asynchronous} system. Specifically, we consider transmission over the block noncoherent Additive White Gaussian Noise (AWGN) channel, and investigate the achievable performance under low-precision output quantization. We focus attention on an architecture in which the receiver quantizes {\it only the phase} of the received signal: this has the advantage of being implementable without automatic gain control, using multiple 1-bit ADCs preceded by analog multipliers. For standard uniform Phase Shift Keying (PSK) modulation, we study the structure of the transition density of the resulting phase-quantized block noncoherent channel. Several results, based on the symmetry inherent in the channel model, are provided to characterize this transition density. Low-complexity procedures for computing the channel capacity, and for block demodulation, are obtained using these results. Numerical computations are performed to compare the performance of quantized and unquantized systems, for different quantization precisions, and different block lengths. It is observed, for example, that with QPSK modulation, 8-bin phase quantization of the received signal recovers about 80-85% of the capacity attained with unquantized observations, while 12-bin phase quantization recovers more than 90% of the unquantized capacity. Dithering the constellation is shown to improve the performance in the face of drastic quantization.
A Unit Commitment Model with Demand Response for the Integration of Renewable Energies
Venue: arXiv cs.SY 2011
Year: 2011

The output of renewable energy fluctuates significantly depending on weather conditions. We develop a unit commitment model to analyze requirements of the forecast output and its error for renewable energies. Our model obtains the time series for the operational state of thermal power plants that would maximize the profits of an electric power utility by taking into account both the forecast of output its error for renewable energies and the demand response of consumers. We consider a power system consisting of thermal power plants, photovoltaic systems (PV), and wind farms and analyze the effect of the forecast error on the operation cost and reserves. We confirm that the operation cost was increases with the forecast error. The effect of a sudden decrease in wind power is also analyzed. More thermal power plants need to be operated to generate power to absorb this sudden decrease in wind power. The increase in the number of operating thermal power plants within a short period does not affect the total operation cost significantly; however the substitution of thermal power plants by wind farms or PV systems is not expected to be very high. Finally, the effects of the demand response in the case of a sudden decrease in wind power are analyzed. We confirm that the number of operating thermal power plants is reduced by the demand response. A power utility has to continue thermal power plants for ensuring supply-demand balance; some of these plants can be decommissioned after installing a large number of wind farms or PV systems, if the demand response is applied using an appropriate price structure.
A Study of CAPTCHAs for Securing Web Services
Venue: arXiv cs.CR 2011
Year: 2011

Atomizing various Web activities by replacing human to human interactions on the Internet has been made indispensable due to its enormous growth. However, bots also known as Web-bots which have a malicious intend and pretending to be humans pose a severe threat to various services on the Internet that implicitly assume a human interaction. Accordingly, Web service providers before allowing access to such services use various Human Interaction Proof's (HIPs) to authenticate that the user is a human and not a bot. Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA) is a class of HIPs tests and are based on Artificial Intelligence. These tests are easier for humans to qualify and tough for bots to simulate. Several Web services use CAPTCHAs as a defensive mechanism against automated Web-bots. In this paper, we review the existing CAPTCHA schemes that have been proposed or are being used to protect various Web services. We classify them in groups and compare them with each other in terms of security and usability. We present general method used to generate and break text-based and image-based CAPTCHAs. Further, we discuss various security and usability issues in CAPTCHA design and provide guidelines for improving their robustness and usability.
A Theoretical Analysis of Authentication, Privacy and Reusability Across Secure Biometric Systems
Venue: arXiv cs.IT 2011
Year: 2011

We present a theoretical framework for the analysis of privacy and security tradeoffs in secure biometric authentication systems. We use this framework to conduct a comparative information-theoretic analysis of two biometric systems that are based on linear error correction codes, namely fuzzy commitment and secure sketches. We derive upper bounds for the probability of false rejection ($P_{FR}$) and false acceptance ($P_{FA}$) for these systems. We use mutual information to quantify the information leaked about a user's biometric identity, in the scenario where one or multiple biometric enrollments of the user are fully or partially compromised. We also quantify the probability of successful attack ($P_{SA}$) based on the compromised information. Our analysis reveals that fuzzy commitment and secure sketch systems have identical $P_{FR}, P_{FA}, P_{SA}$ and information leakage, but secure sketch systems have lower storage requirements. We analyze both single-factor (keyless) and two-factor (key-based) variants of secure biometrics, and consider the most general scenarios in which a single user may provide noisy biometric enrollments at several access control devices, some of which may be subsequently compromised by an attacker. Our analysis highlights the revocability and reusability properties of key-based systems and exposes a subtle design tradeoff between reducing information leakage from compromised systems and preventing successful attacks on systems whose data have not been compromised.
Transferring Voice using SMS over GSM Network
Venue: arXiv cs.NI 2011
Year: 2011

The paper presents a methodology of transmitting voice in SMS (Short Message Service) over GSM network. Usually SMS contents are text based and limited to 140 bytes. It supports national and international roaming, but also supported by other telecommunication such as TDMA (Time Division Multiple Access), CDMA (Code Division Multiple Access) as well. It can sent/ receive simultaneously with other services. Such features make it favorable for this methodology. For this an application is developed using J2ME platform which is supported by all mobile phones in the world. This algorithm's test is conducted on N95 having Symbian Operating System (OS).
Secure Diversity-Multiplexing Tradeoff of Zero-Forcing Transmit Scheme at Finite-SNR
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we address the finite Signal-to-Noise Ratio (SNR) Diversity-Multiplexing Tradeoff (DMT) of the Multiple Input Multiple Output (MIMO) wiretap channel, where a Zero-Forcing (ZF) transmit scheme, that intends to send the secret information in the orthogonal space of the eavesdropper channel, is used. First, we introduce the secrecy multiplexing gain at finite-SNR that generalizes the definition at high-SNR. Then, we provide upper and lower bounds on the outage probability under secrecy constraint, from which secrecy diversity gain estimates of ZF are derived. Through asymptotic analysis, we show that the upper bound underestimates the secrecy diversity gain, whereas the lower bound is tight at high-SNR, and thus its related diversity gain estimate is equal to the actual asymptotic secrecy diversity gain of the MIMO wiretap channel.
A self-rendering digital image encoding
Venue: arXiv cs.GR 2011
Year: 2011

Without careful long-term preservation digital data may be lost to a number of factors, including physical media decay, lack of suitable decoding equipment, and the absence of software. When raw data can be read but lack suitable annotations as to provenance, the ability to interpret them is more straightforward if they can be assessed through simple visual techniques. In this regard digital images are a special case since their data have a natural representation on two-dimensional media surfaces. This paper presents a novel binary image pixel encoding that produces an approximate analog rendering of encoded images when the image bits are arranged spatially in an appropriate manner. This simultaneous digital and analog representation acts to inseparably annotate bits as image data, which may contribute to the longevity of so-encoded images.
Two-Manifold Problems
Venue: arXiv cs.LG 2011
Year: 2011

Recently, there has been much interest in spectral approaches to learning manifolds---so-called kernel eigenmap methods. These methods have had some successes, but their applicability is limited because they are not robust to noise. To address this limitation, we look at two-manifold problems, in which we simultaneously reconstruct two related manifolds, each representing a different view of the same data. By solving these interconnected learning problems together and allowing information to flow between them, two-manifold algorithms are able to succeed where a non-integrated approach would fail: each view allows us to suppress noise in the other, reducing bias in the same way that an instrumental variable allows us to remove bias in a {linear} dimensionality reduction problem. We propose a class of algorithms for two-manifold problems, based on spectral decomposition of cross-covariance operators in Hilbert space. Finally, we discuss situations where two-manifold problems are useful, and demonstrate that solving a two-manifold problem can aid in learning a nonlinear dynamical system from limited data.
Effects for Funargs
Venue: arXiv cs.PL 2011
Year: 2011

Stack allocation and first-class functions don't naturally mix together. In this paper we show that a type and effect system can be the detergent that helps these features form a nice emulsion. Our interest in this problem comes from our work on the Chapel language, but this problem is also relevant to lambda expressions in C++ and blocks in Objective C. The difficulty in mixing first-class functions and stack allocation is a tension between safety, efficiency, and simplicity. To preserve safety, one must worry about functions outliving the variables they reference: the classic upward funarg problem. There are systems which regain safety but lose programmer-predictable efficiency, and ones that provide both safety and efficiency, but give up simplicity by exposing regions to the programmer. In this paper we present a simple design that combines a type and effect system, for safety, with function-local storage, for control over efficiency.
Computing Cartograms with Optimal Complexity
Venue: arXiv cs.DM 2011
Year: 2011

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons and edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight of the corresponding vertex. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine the representation into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal rectangular layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs.
B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives
Venue: arXiv cs.DB 2011
Year: 2011

Previous research addressed the potential problems of the hard-disk oriented design of DBMSs of flashSSDs. In this paper, we focus on exploiting potential benefits of flashSSDs. First, we examine the internal parallelism issues of flashSSDs by conducting benchmarks to various flashSSDs. Then, we suggest algorithm-design principles in order to best benefit from the internal parallelism. We present a new I/O request concept, called psync I/O that can exploit the internal parallelism of flashSSDs in a single process. Based on these ideas, we introduce B+-tree optimization methods in order to utilize internal parallelism. By integrating the results of these methods, we present a B+-tree variant, PIO B-tree. We confirmed that each optimization method substantially enhances the index performance. Consequently, PIO B-tree enhanced B+-tree's insert performance by a factor of up to 16.3, while improving point-search performance by a factor of 1.2. The range search of PIO B-tree was up to 5 times faster than that of the B+-tree. Moreover, PIO B-tree outperformed other flash-aware indexes in various synthetic workloads. We also confirmed that PIO B-tree outperforms B+-tree in index traces collected inside the Postgresql DBMS with TPC-C benchmark.
Capturing Topology in Graph Pattern Matching
Venue: arXiv cs.DB 2011
Year: 2011

Graph pattern matching is often defined in terms of subgraph isomorphism, an NP-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow pattern matching to be conducted in cubic-time. However, they fall short of capturing the topology of data graphs, i.e., graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this paper proposes a notion of strong simulation, a revision of graph simulation, for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of simulation, by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation, which allows us to effectively conduct pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using real-life data and synthetic data.
Relational Approach for Shortest Path Discovery over Large Graphs
Venue: arXiv cs.DB 2011
Year: 2011

With the rapid growth of large graphs, we cannot assume that graphs can still be fully loaded into memory, thus the disk-based graph operation is inevitable. In this paper, we take the shortest path discovery as an example to investigate the technique issues when leveraging existing infrastructure of relational database (RDB) in the graph data management. Based on the observation that a variety of graph search queries can be implemented by iterative operations including selecting frontier nodes from visited nodes, making expansion from the selected frontier nodes, and merging the expanded nodes into the visited ones, we introduce a relational FEM framework with three corresponding operators to implement graph search tasks in the RDB context. We show new features such as window function and merge statement introduced by recent SQL standards can not only simplify the expression but also improve the performance of the FEM framework. In addition, we propose two optimization strategies specific to shortest path discovery inside the FEM framework. First, we take a bi-directional set Dijkstra's algorithm in the path finding. The bi-directional strategy can reduce the search space, and set Dijkstra's algorithm finds the shortest path in a set-at-a-time fashion. Second, we introduce an index named SegTable to preserve the local shortest segments, and exploit SegTable to further improve the performance. The final extensive experimental results illustrate our relational approach with the optimization strategies achieves high scalability and performance.
A Network Approach to the French System of Legal codes - Part I: Analysis of a Dense Network
Venue: arXiv cs.SI 2011
Year: 2011

We explore one aspect of the structure of a codified legal system at the national level using a new type of representation to understand the strong or weak dependencies between the various fields of law. In Part I of this study, we analyze the graph associated with the network in which each French legal code is a vertex and an edge is produced between two vertices when a code cites another code at least one time. We show that this network distinguishes from many other real networks from a high density, giving it a particular structure that we call concentrated world and that differentiates a national legal system (as considered with a resolution at the code level) from small-world graphs identified in many social networks. Our analysis then shows that a few communities (groups of highly wired vertices) of codes covering large domains of regulation are structuring the whole system. Indeed we mainly find a central group of influent codes, a group of codes related to social issues and a group of codes dealing with territories and natural resources. The study of this codified legal system is also of interest in the field of the analysis of real networks. In particular we examine the impact of the high density on the structural characteristics of the graph and on the ways communities are searched for. Finally we provide an original visualization of this graph on an hemicyle-like plot, this representation being based on a statistical reduction of dissimilarity measures between vertices. In Part II (a following paper) we show how the consideration of the weights attributed to each edge in the network in proportion to the number of citations between two vertices (codes) allows deepening the analysis of the French legal system.
Minutiae Extraction from Fingerprint Images - a Review
Venue: arXiv cs.CV 2011
Year: 2011

Fingerprints are the oldest and most widely used form of biometric identification. Everyone is known to have unique, immutable fingerprints. As most Automatic Fingerprint Recognition Systems are based on local ridge features known as minutiae, marking minutiae accurately and rejecting false ones is very important. However, fingerprint images get degraded and corrupted due to variations in skin and impression conditions. Thus, image enhancement techniques are employed prior to minutiae extraction. A critical step in automatic fingerprint matching is to reliably extract minutiae from the input fingerprint images. This paper presents a review of a large number of techniques present in the literature for extracting fingerprint minutiae. The techniques are broadly classified as those working on binarized images and those that work on gray scale images directly.
Feature Selection for Generator Excitation Neurocontroller Development Using Filter Technique
Venue: arXiv cs.SY 2011
Year: 2011

Essentially, motive behind using control system is to generate suitable control signal for yielding desired response of a physical process. Control of synchronous generator has always remained very critical in power system operation and control. For certain well known reasons power generators are normally operated well below their steady state stability limit. This raises demand for efficient and fast controllers. Artificial intelligence has been reported to give revolutionary outcomes in the field of control engineering. Artificial Neural Network (ANN), a branch of artificial intelligence has been used for nonlinear and adaptive control, utilizing its inherent observability. The overall performance of neurocontroller is dependent upon input features too. Selecting optimum features to train a neurocontroller optimally is very critical. Both quality and size of data are of equal importance for better performance. In this work filter technique is employed to select independent factors for ANN training.
Note on Needle in a Haystack
Venue: arXiv cs.ET 2011
Year: 2011

Introduced below is a quantum database method, not only for retrieval but also for creation. It uses a particular structure of true's and false's in a state vector of n qubits, permitting up to 2**2**n words, vastly more than for classical bits. Several copies are produced so that later they can be destructively observed and a word determined with high probability. Grover's algorithm is proposed below to read out, nondestructively the unknown contents of a given stored state vector using only one state vector.
Verification Across Intellectual Property Boundaries
Venue: arXiv cs.OH 2011
Year: 2011

In many industries, the importance of software components provided by third-party suppliers is steadily increasing. As the suppliers seek to secure their intellectual property (IP) rights, the customer usually has no direct access to the suppliers' source code, and is able to enforce the use of verification tools only by legal requirements. In turn, the supplier has no means to convince the customer about successful verification without revealing the source code. This paper presents an approach to resolve the conflict between the IP interests of the supplier and the quality interests of the customer. We introduce a protocol in which a dedicated server (called the "amanat") is controlled by both parties: the customer controls the verification task performed by the amanat, while the supplier controls the communication channels of the amanat to ensure that the amanat does not leak information about the source code. We argue that the protocol is both practically useful and mathematically sound. As the protocol is based on well-known (and relatively lightweight) cryptographic primitives, it allows a straightforward implementation on top of existing verification tool chains. To substantiate our security claims, we establish the correctness of the protocol by cryptographic reduction proofs.
Clones and Genoids in Lambda Calculus and First Order Logic
Venue: arXiv cs.LO 2012
Year: 2012

A genoid is a category of two objects such that one is the product of itself with the other. A genoid may be viewed as an abstract substitution algebra. It is a remarkable fact that such a simple concept can be applied to present a unified algebraic approach to lambda calculus and first order logic.
Young's axiomatization of the Shapley value - a new proof
Venue: arXiv cs.GT 2012
Year: 2012

We consider Young (1985)'s characterization of the Shapley value, and give a new proof of this axiomatization. Moreover, as applications of the new proof, we show that Young (1985)'s axiomatization of the Shapley value works on various well-known subclasses of TU games.