OpenRaiser/Intern-Atlas huggingface dataset:
A Cryptographic Treatment of the Wiretap Channel
Venue: arXiv cs.IT 2012
Year: 2012

The wiretap channel is a setting where one aims to provide information-theoretic privacy of communicated data based solely on the assumption that the channel from sender to adversary is "noisier" than the channel from sender to receiver. It has been the subject of decades of work in the information and coding (I&C) community. This paper bridges the gap between this body of work and modern cryptography with contributions along two fronts, namely metrics (definitions) of security, and schemes. We explain that the metric currently in use is weak and insufficient to guarantee security of applications and propose two replacements. One, that we call mis-security, is a mutual-information based metric in the I&C style. The other, semantic security, adapts to this setting a cryptographic metric that, in the cryptography community, has been vetted by decades of evaluation and endorsed as the target for standards and implementations. We show that they are equivalent (any scheme secure under one is secure under the other), thereby connecting two fundamentally different ways of defining security and providing a strong, unified and well-founded target for designs. Moving on to schemes, results from the wiretap community are mostly non-constructive, proving the existence of schemes without necessarily yielding ones that are explicit, let alone efficient, and only meeting their weak notion of security. We apply cryptographic methods based on extractors to produce explicit, polynomial-time and even practical encryption schemes that meet our new and stronger security target.
Bengali text summarization by sentence extraction
Venue: arXiv cs.IR 2012
Year: 2012

Text summarization is a process to produce an abstract or a summary by selecting significant portion of the information from one or more texts. In an automatic text summarization process, a text is given to the computer and the computer returns a shorter less redundant extract or abstract of the original text(s). Many techniques have been developed for summarizing English text(s). But, a very few attempts have been made for Bengali text summarization. This paper presents a method for Bengali text summarization which extracts important sentences from a Bengali document to produce a summary.
Characterisations of Testing Preorders for a Finite Probabilistic pi-Calculus
Venue: arXiv cs.LO 2012
Year: 2012

We consider two characterisations of the may and must testing preorders for a probabilistic extension of the finite pi-calculus: one based on notions of probabilistic weak simulations, and the other on a probabilistic extension of a fragment of Milner-Parrow-Walker modal logic for the pi-calculus. We base our notions of simulations on the similar concepts used in previous work for probabilistic CSP. However, unlike the case with CSP (or other non-value-passing calculi), there are several possible definitions of simulation for the probabilistic pi-calculus, which arise from different ways of scoping the name quantification. We show that in order to capture the testing preorders, one needs to use the "earliest" simulation relation (in analogy to the notion of early (bi)simulation in the non-probabilistic case). The key ideas in both characterisations are the notion of a "characteristic formula" of a probabilistic process, and the notion of a "characteristic test" for a formula. As in an earlier work on testing equivalence for the pi-calculus by Boreale and De Nicola, we extend the language of the $π$-calculus with a mismatch operator, without which the formulation of a characteristic test will not be possible.
Network Coding Meets Information-Centric Networking
Venue: arXiv cs.NI 2012
Year: 2012

The focus of user behavior in the Internet has changed over the recent years towards being driven by exchanging and accessing information. Many advances in networking technologies have utilized this change by focusing on the content of an exchange rather than the endpoints exchanging the content. Network coding and information centric networking are two examples of these technology trends, each being developed largely independent so far. This paper brings these areas together in an evolutionary as well as explorative setting for a new internetworking architecture. We outline opportunities for applying network coding in a novel and performance-enhancing way that could eventually push forward the case for information centric network itself.
The Development of a LAN for DVB-T Transmission and DVB-S Reception with Designed QAM Modulators and COFDM in the Island Mauritius
Venue: arXiv cs.NI 2012
Year: 2012

This paper is a thorough study of a digital broadcasting system adapted to the small mountainous island of Mauritius. A digital LAN was designed with MPEG-2 signals. The compressed signals were transmitted using DVB-T and QAM modulators. QAM-16 and QAM-64 modulators were designed and tested with a simulator under critical conditions of AWGN and phase noises. Results obtained from simulation have shown that Digital video broadcast with a single frequency network (SFN) is possible in Mauritius with QAM-64 and QAM-16 modulators applying COFDM mode of transmission. However, this study has also shown that QAM-16 modulator had a better performance at low AWGN values (less than 12 dB) and can be adopted for Mauritius Island, provided that the number of transmitted channels is not high enough.
Joint Approximation of Information and Distributed Link-Scheduling Decisions in Wireless Networks
Venue: arXiv cs.LG 2012
Year: 2012

For a large multi-hop wireless network, nodes are preferable to make distributed and localized link-scheduling decisions with only interactions among a small number of neighbors. However, for a slowly decaying channel and densely populated interferers, a small size neighborhood often results in nontrivial link outages and is thus insufficient for making optimal scheduling decisions. A question arises how to deal with the information outside a neighborhood in distributed link-scheduling. In this work, we develop joint approximation of information and distributed link scheduling. We first apply machine learning approaches to model distributed link-scheduling with complete information. We then characterize the information outside a neighborhood in form of residual interference as a random loss variable. The loss variable is further characterized by either a Mean Field approximation or a normal distribution based on the Lyapunov central limit theorem. The approximated information outside a neighborhood is incorporated in a factor graph. This results in joint approximation and distributed link-scheduling in an iterative fashion. Link-scheduling decisions are first made at each individual node based on the approximated loss variables. Loss variables are then updated and used for next link-scheduling decisions. The algorithm repeats between these two phases until convergence. Interactive iterations among these variables are implemented with a message-passing algorithm over a factor graph. Simulation results show that using learned information outside a neighborhood jointly with distributed link-scheduling reduces the outage probability close to zero even for a small neighborhood.
Time Stamp Attack in Smart Grid: Physical Mechanism and Damage Analysis
Venue: arXiv cs.CR 2012
Year: 2012

Many operations in power grids, such as fault detection and event location estimation, depend on precise timing information. In this paper, a novel time stamp attack (TSA) is proposed to attack the timing information in smart grid. Since many applications in smart grid utilize synchronous measurements and most of the measurement devices are equipped with global positioning system (GPS) for precise timing, it is highly probable to attack the measurement system by spoofing the GPS. The effectiveness of TSA is demonstrated for three applications of phasor measurement unit (PMU) in smart grid, namely transmission line fault detection, voltage stability monitoring and event locationing.
SybilControl: Practical Sybil Defense with Computational Puzzles
Venue: arXiv cs.NI 2012
Year: 2012

Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating behavior of multiple distinct nodes. Most recent work to address this problem leverages social networks to establish trust relationships between users. However, the use of social networks is not appropriate in all systems, as they can be subverted by social engineering techniques, require nodes in a P2P network to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present SybilControl, a novel, decentralized scheme for controlling the extent of Sybil attacks. SybilControl is an admission control mechanism for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with resilient lookup protocols. We evaluate SybilControl through simulations and find that SybilControl retains low overhead and latency. Additionally, even when the adversary controls 20% of the system's computational resources, SybilControl-enabled DHTs can be configured to maintain lookup performance at over 99% success rate using low communication overhead.
Faster Approximate Distance Queries and Compact Routing in Sparse Graphs
Venue: arXiv cs.DS 2012
Year: 2012

A distance oracle is a compact representation of the shortest distance matrix of a graph. It can be queried to approximate shortest paths between any pair of vertices. Any distance oracle that returns paths of worst-case stretch (2k-1) must require space $Ω(n^{1 + 1/k})$ for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree Ω(n^{1/k}). We present distance oracles that, for sparse graphs, substantially break the lower bound barrier at the expense of higher query time. For any 1 \leq α\leq n, our distance oracles can return stretch 2 paths using O(m + n^2/α) space and stretch 3 paths using O(m + n^2/α^2) space, at the expense of O(αm/n) query time. By setting appropriate values of α, we get the first distance oracles that have size linear in the size of the graph, and return constant stretch paths in non-trivial query time. The query time can be further reduced to O(α), by using an additional O(m α) space for all our distance oracles, or at the cost of a small constant additive stretch. We use our stretch 2 distance oracle to present the first compact routing scheme with worst-case stretch 2. Any compact routing scheme with stretch less than 2 must require linear memory at some nodes even for sparse graphs; our scheme, hence, achieves the optimal stretch with non-trivial memory requirements. Moreover, supported by large-scale simulations on graphs including the AS-level Internet graph, we argue that our stretch-2 scheme would be simple and efficient to implement as a distributed compact routing protocol.
Ultrametric Model of Mind, I: Review
Venue: arXiv cs.AI 2012
Year: 2012

We mathematically model Ignacio Matte Blanco's principles of symmetric and asymmetric being through use of an ultrametric topology. We use for this the highly regarded 1975 book of this Chilean psychiatrist and pyschoanalyst (born 1908, died 1995). Such an ultrametric model corresponds to hierarchical clustering in the empirical data, e.g. text. We show how an ultrametric topology can be used as a mathematical model for the structure of the logic that reflects or expresses Matte Blanco's symmetric being, and hence of the reasoning and thought processes involved in conscious reasoning or in reasoning that is lacking, perhaps entirely, in consciousness or awareness of itself. In a companion paper we study how symmetric (in the sense of Matte Blanco's) reasoning can be demarcated in a context of symmetric and asymmetric reasoning provided by narrative text.
ART : Sub-Logarithmic Decentralized Range Query Processing with Probabilistic Guarantees
Venue: arXiv cs.DB 2012
Year: 2012

We focus on range query processing on large-scale, typically distributed infrastructures, such as clouds of thousands of nodes of shared-datacenters, of p2p distributed overlays, etc. In such distributed environments, efficient range query processing is the key for managing the distributed data sets per se, and for monitoring the infrastructure's resources. We wish to develop an architecture that can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. Of course, in the last few years there have been a number of solutions (mostly from researchers in the p2p domain) for designing such large-scale systems. However, these are inadequate for our purposes, since at the envisaged scales the classic logarithmic complexity (for point queries) is still too expensive while for range queries it is even more disappointing. In this paper we go one step further and achieve a sub-logarithmic complexity. We contribute the ART, which outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. We contribute theoretical analysis, backed up by detailed experimental results, showing that the communication cost of query and update operations is $O(\log_{b}^2 \log N)$ hops, where the base $b$ is a double-exponentially power of two and $N$ is the total number of nodes. Moreover, ART is a fully dynamic and fault-tolerant structure, which supports the join/leave node operations in $O(\log \log N)$ expected w.h.p number of hops. Our experimental performance studies include a detailed performance comparison which showcases the improved performance, scalability, and robustness of ART.
Linear Kernels on Graphs Excluding Topological Minors
Venue: arXiv cs.DS 2012
Year: 2012

We show that problems which have finite integer index and satisfy a requirement we call treewidth-bounding admit linear kernels on the class of $H$-topological-minor free graphs, for an arbitrary fixed graph $H$. This builds on earlier results by Fomin et al.\ on linear kernels for $H$-minor-free graphs and by Bodlaender et al.\ on graphs of bounded genus. Our framework encompasses several problems, the prominent ones being Chordal Vertex Deletion, Feedback Vertex Set and Edge Dominating Set.
Event Space Theory and Its Application
Venue: arXiv cs.SE 2012
Year: 2012

In this paper, the basic ideal of the Event Space Theory and Analyzing Events are expatiated on. Then it is suggested that how to set up event base library in developing application software. Based above the designing principle of facing methodology. Finally, in order to explain how to apply the Event Space Theory in developing economic evaluation software, the software of "sewage treatment CAD" in a national "8th-Five Year Plan Research Project" of PRC is used as an example. This software concerns economic effectiveness evaluation for construction projects.
Degraded Broadcast Channel with Side Information, Confidential Messages and Noiseless Feedback
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, first, we investigate the model of degraded broadcast channel with side information and confidential messages. This work is from Steinberg's work on the degraded broadcast channel with causal and noncausal side information, and Csisz$\acute{a}$r-Körner's work on broadcast channel with confidential messages. Inner and outer bounds on the capacity-equivocation regions are provided for the noncausal and causal cases. Superposition coding and double-binning technique are used in the corresponding achievability proofs. Then, we investigate the degraded broadcast channel with side information, confidential messages and noiseless feedback. The noiseless feedback is from the non-degraded receiver to the channel encoder. Inner and outer bounds on the capacity-equivocation region are provided for the noncausal case, and the capacity-equivocation region is determined for the causal case. Compared with the model without feedback, we find that the noiseless feedback helps to enlarge the inner bounds for both causal and noncausal cases. In the achievability proof of the feedback model, the noiseless feedback is used as a secret key shared by the non-degraded receiver and the transmitter, and therefore, the code construction for the feedback model is a combination of superposition coding, Gel'fand-Pinsker's binning, block Markov coding and Ahlswede-Cai's secret key on the feedback system.
Joint Robust Weighted LMMSE Transceiver Design for Dual-Hop AF Multiple-Antenna Relay Systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, joint transceiver design for dual-hop amplify-and-forward (AF) MIMO relay systems with Gaussian distributed channel estimation errors in both two hops is investigated. Due to the fact that various linear transceiver designs can be transformed to a weighted linear minimum mean-square-error (LMMSE) transceiver design with specific weighting matrices, weighted mean square error (MSE) is chosen as the performance metric. Precoder matrix at source, forwarding matrix at relay and equalizer matrix at destination are jointly designed with channel estimation errors taken care of by Bayesian philosophy. Several existing algorithms are found to be special cases of the proposed solution. The performance advantage of the proposed robust design is demonstrated by the simulation results.
Spring Embedders and Force Directed Graph Drawing Algorithms
Venue: arXiv cs.CG 2012
Year: 2012

Force-directed algorithms are among the most flexible methods for calculating layouts of simple undirected graphs. Also known as spring embedders, such algorithms calculate the layout of a graph using only information contained within the structure of the graph itself, rather than relying on domain-specific knowledge. Graphs drawn with these algorithms tend to be aesthetically pleasing, exhibit symmetries, and tend to produce crossing-free layouts for planar graphs. In this survey we consider several classical algorithms, starting from Tutte's 1963 barycentric method, and including recent scalable multiscale methods for large and dynamic graphs.
Design of Emergent and Adaptive Virtual Players in a War RTS Game
Venue: arXiv cs.NE 2012
Year: 2012

Basically, in (one-player) war Real Time Strategy (wRTS) games a human player controls, in real time, an army consisting of a number of soldiers and her aim is to destroy the opponent's assets where the opponent is a virtual (i.e., non-human player controlled) player that usually consists of a pre-programmed decision-making script. These scripts have usually associated some well-known problems (e.g., predictability, non-rationality, repetitive behaviors, and sensation of artificial stupidity among others). This paper describes a method for the automatic generation of virtual players that adapt to the player skills; this is done by building initially a model of the player behavior in real time during the game, and further evolving the virtual player via this model in-between two games. The paper also shows preliminary results obtained on a one player wRTS game constructed specifically for experimentation.
Matrix representation of a solution of a combinatorial problem of the group theory
Venue: arXiv cs.MS 2012
Year: 2012

An equivalence relation in the symmetric group, where is a positive integer has been considered. An algorithm for calculation of the number of the equivalence classes by this relation for arbitrary integer has been described.
Near-Optimal Expanding Generating Sets for Solvable Permutation Groups
Venue: arXiv cs.CC 2012
Year: 2012

Let $G =<S>$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/λ)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $λ$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}.
Evaluation of a Simple, Scalable, Parallel Best-First Search Strategy
Venue: arXiv cs.AI 2012
Year: 2012

Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate Hash-Distributed A* (HDA*), a simple approach to parallel best-first search that asynchronously distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A* algorithm in an optimal sequential version of the Fast Downward planner, as well as a 24-puzzle solver. The scaling behavior of HDA* is evaluated experimentally on a shared memory, multicore machine with 8 cores, a cluster of commodity machines using up to 64 cores, and large-scale high-performance clusters, using up to 2400 processors. We show that this approach scales well, allowing the effective utilization of large amounts of distributed memory to optimally solve problems which require terabytes of RAM. We also compare HDA* to Transposition-table Driven Scheduling (TDS), a hash-based parallelization of IDA*, and show that, in planning, HDA* significantly outperforms TDS. A simple hybrid which combines HDA* and TDS to exploit strengths of both algorithms is proposed and evaluated.
Variations of images to increase their visibility
Venue: arXiv cs.CV 2012
Year: 2012

The calculus of variations applied to the image processing requires some numerical models able to perform the variations of images and the extremization of appropriate actions. To produce the variations of images, there are several possibilities based on the brightness maps. Before a numerical model, I propose an experimental approach, based on a tool of Gimp, GNU Image Manipulation Program, in order to visualize how the image variations can be. After the discussion of this tool, which is able to strongly increase the visibility of images, the variations and a possible functional for the visibility are proposed in the framework of a numerical model. The visibility functional is analogous to the fringe visibility of the optical interference.