OpenRaiser/Intern-Atlas huggingface dataset:
SqFreeEVAL: An (almost) optimal real-root isolation algorithm
Venue: arXiv cs.DS 2011
Year: 2011

Let f be a univariate polynomial with real coefficients, f in R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+ln d)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits. Our proof uses two amortization-based techniques: First, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.
Power Allocation for Cognitive Wireless Mesh Networks by Applying Multi-agent Q-learning Approach
Venue: arXiv cs.IT 2011
Year: 2011

As the scarce spectrum resource is becoming over-crowded, cognitive radios (CRs) indicate great flexibility to improve the spectrum efficiency by opportunistically accessing the authorized frequency bands. One of the critical challenges for operating such radios in a network is how to efficiently allocate transmission powers and frequency resource among the secondary users (SUs) while satisfying the quality-of-service (QoS) constraints of the primary users (PUs). In this paper, we focus on the non-cooperative power allocation problem in cognitive wireless mesh networks (CogMesh) formed by a number of clusters with the consideration of energy efficiency. Due to the SUs' selfish and spontaneous properties, the problem is modeled as a stochastic learning process. We first extend the single-agent Q-learning to a multi-user context, and then propose a conjecture based multi-agent Qlearning algorithm to achieve the optimal transmission strategies with only private and incomplete information. An intelligent SU performs Q-function updates based on the conjecture over the other SUs' stochastic behaviors. This learning algorithm provably converges given certain restrictions that arise during learning procedure. Simulation experiments are used to verify the performance of our algorithm and demonstrate its effectiveness of improving the energy efficiency.
An Implicit Cover Problem in Wild Population Study
Venue: arXiv cs.CC 2011
Year: 2011

In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly For example, the well-known minimum feedback arc set problem is such a problem. In this paper, we consider such a cover problem that arises in the study of wild populations in biology in which the sets are defined implicitly via the Mendelian constraints and prove approximability results for this problem.
Hierarchical Heavy Hitters with the Space Saving Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

The Hierarchical Heavy Hitters problem extends the notion of frequent items to data arranged in a hierarchy. This problem has applications to network traffic monitoring, anomaly detection, and DDoS detection. We present a new streaming approximation algorithm for computing Hierarchical Heavy Hitters that has several advantages over previous algorithms. It improves on the worst-case time and space bounds of earlier algorithms, is conceptually simple and substantially easier to implement, offers improved accuracy guarantees, is easily adopted to a distributed or parallel setting, and can be efficiently implemented in commodity hardware such as ternary content addressable memory (TCAMs). We present experimental results showing that for parameters of primary practical interest, our two-dimensional algorithm is superior to existing algorithms in terms of speed and accuracy, and competitive in terms of space, while our one-dimensional algorithm is also superior in terms of speed and accuracy for a more limited range of parameters.
Covert channel detection using Information Theory
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents an information theory based detection framework for covert channels. We first show that the usual notion of interference does not characterize the notion of deliberate information flow of covert channels. We then show that even an enhanced notion of "iterated multivalued interference" can not capture flows with capacity lower than one bit of information per channel use. We then characterize and compute the capacity of covert channels that use control flows for a class of systems.
Distributed Adaptive Attitude Synchronization of Multiple Spacecraft
Venue: arXiv cs.SY 2011
Year: 2011

This paper addresses the distributed attitude synchronization problem of multiple spacecraft with unknown inertia matrices. Two distributed adaptive controllers are proposed for the cases with and without a virtual leader to which a time-varying reference attitude is assigned. The first controller achieves attitude synchronization for a group of spacecraft with a leaderless communication topology having a directed spanning tree. The second controller guarantees that all spacecraft track the reference attitude if the virtual leader has a directed path to all other spacecraft. Simulation examples are presented to illustrate the effectiveness of the results.
A novel super resolution reconstruction of low reoslution images progressively using dct and zonal filter based denoising
Venue: arXiv cs.CV 2011
Year: 2011

Due to the factors like processing power limitations and channel capabilities images are often down sampled and transmitted at low bit rates resulting in a low resolution compressed image. High resolution images can be reconstructed from several blurred, noisy and down sampled low resolution images using a computational process know as super resolution reconstruction. Super-resolution is the process of combining multiple aliased low-quality images to produce a high resolution, high-quality image. The problem of recovering a high resolution image progressively from a sequence of low resolution compressed images is considered. In this paper we propose a novel DCT based progressive image display algorithm by stressing on the encoding and decoding process. At the encoder we consider a set of low resolution images which are corrupted by additive white Gaussian noise and motion blur. The low resolution images are compressed using 8 by 8 blocks DCT and noise is filtered using our proposed novel zonal filter. Multiframe fusion is performed in order to obtain a single noise free image. At the decoder the image is reconstructed progressively by transmitting the coarser image first followed by the detail image. And finally a super resolution image is reconstructed by applying our proposed novel adaptive interpolation technique. We have performed both objective and subjective analysis of the reconstructed image, and the resultant image has better super resolution factor, and a higher ISNR and PSNR. A comparative study done with Iterative Back Projection (IBP) and Projection on to Convex Sets (POCS),Papoulis Grechberg, FFT based Super resolution Reconstruction shows that our method has out performed the previous contributions.
XMLlab : multimedia publication of simulations applets using XML and Scilab
Venue: arXiv cs.MS 2011
Year: 2011

We present an XML-based simulation authoring environment. The proposed description language allows to describe mathematical objects such as systems of ordinary differential equations, partial differential equations in two dimensions, or simple curves and surfaces. It also allows to describe the parameters on which these objects depend. This language is independent of the target software and allows to ensure the perennity of author's work, as well as collaborative work and content reuse. The actual implementation of XMLlab allows to run the generated simulations within the open source mathematical software Scilab, either locally when Scilab is installed on the client machines, or on thin clients running a simple web browser, when XMLlab and Scilab are installed on a distant server running a standard HTTP server.
Improving the character recognition efficiency of feed forward BP neural network
Venue: arXiv cs.NE 2011
Year: 2011

This work is focused on improving the character recognition capability of feed-forward back-propagation neural network by using one, two and three hidden layers and the modified additional momentum term. 182 English letters were collected for this work and the equivalent binary matrix form of these characters was applied to the neural network as training patterns. While the network was getting trained, the connection weights were modified at each epoch of learning. For each training sample, the error surface was examined for minima by computing the gradient descent. We started the experiment by using one hidden layer and the number of hidden layers was increased up to three and it has been observed that accuracy of the network was increased with low mean square error but at the cost of training time. The recognition accuracy was improved further when modified additional momentum term was used.
On the Sum-Capacity with Successive Decoding in Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms (a simple one and a finer one) to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the sum-capacity of the Gaussian Han-Kobayashi schemes, which automatically upper bound the sum-capacity using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Han-Kobayashi schemes and that with single message schemes.
From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions
Venue: arXiv cs.GT 2011
Year: 2011

We design an expected polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our results apply to bidders with valuations that are m matroid rank sums (MRS), which encompass most concrete examples of submodular functions studied in this context, including coverage functions, matroid weighted-rank functions, and convex combinations thereof. Our approximation factor is the best possible, even for known and explicitly given coverage valuations, assuming P != NP. Ours is the first truthful-in-expectation and polynomial-time mechanism to achieve a constant-factor approximation for an NP-hard welfare maximization problem in combinatorial auctions with heterogeneous goods and restricted valuations. Our mechanism is an instantiation of a new framework for designing approximation mechanisms based on randomized rounding algorithms. A typical such algorithm first optimizes over a fractional relaxation of the original problem, and then randomly rounds the fractional solution to an integral one. With rare exceptions, such algorithms cannot be converted into truthful mechanisms. The high-level idea of our mechanism design framework is to optimize directly over the (random) output of the rounding algorithm, rather than over the input to the rounding algorithm. This approach leads to truthful-in-expectation mechanisms, and these mechanisms can be implemented efficiently when the corresponding objective function is concave. For bidders with MRS valuations, we give a novel randomized rounding algorithm that leads to both a concave objective function and a (1-1/e)-approximation of the optimal welfare.
A generic trust framework for large-scale open systems using machine learning
Venue: arXiv cs.DC 2011
Year: 2011

In many large scale distributed systems and on the web, agents need to interact with other unknown agents to carry out some tasks or transactions. The ability to reason about and assess the potential risks in carrying out such transactions is essential for providing a safe and reliable environment. A traditional approach to reason about the trustworthiness of a transaction is to determine the trustworthiness of the specific agent involved, derived from the history of its behavior. As a departure from such traditional trust models, we propose a generic, machine learning approach based trust framework where an agent uses its own previous transactions (with other agents) to build a knowledge base, and utilize this to assess the trustworthiness of a transaction based on associated features, which are capable of distinguishing successful transactions from unsuccessful ones. These features are harnessed using appropriate machine learning algorithms to extract relationships between the potential transaction and previous transactions. The trace driven experiments using real auction dataset show that this approach provides good accuracy and is highly efficient compared to other trust mechanisms, especially when historical information of the specific agent is rare, incomplete or inaccurate.
Automatic Detection of Ringworm using Local Binary Pattern (LBP)
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we present a novel approach for automatic recognition of ring worm skin disease based on LBP (Local Binary Pattern) feature extracted from the affected skin images. The proposed method is evaluated by extensive experiments on the skin images collected from internet. The dataset is tested using three different classifiers i.e. Bayesian, MLP and SVM. Experimental results show that the proposed methodology efficiently discriminates between a ring worm skin and a normal skin. It is a low cost technique and does not require any special imaging devices.
Learning transformed product distributions
Venue: arXiv cs.LG 2011
Year: 2011

We consider the problem of learning an unknown product distribution $X$ over $\{0,1\}^n$ using samples $f(X)$ where $f$ is a \emph{known} transformation function. Each choice of a transformation function $f$ specifies a learning problem in this framework. Information-theoretic arguments show that for every transformation function $f$ the corresponding learning problem can be solved to accuracy $\eps$, using $\tilde{O}(n/\eps^2)$ examples, by a generic algorithm whose running time may be exponential in $n.$ We show that this learning problem can be computationally intractable even for constant $\eps$ and rather simple transformation functions. Moreover, the above sample complexity bound is nearly optimal for the general problem, as we give a simple explicit linear transformation function $f(x)=w \cdot x$ with integer weights $w_i \leq n$ and prove that the corresponding learning problem requires $Ω(n)$ samples. As our main positive result we give a highly efficient algorithm for learning a sum of independent unknown Bernoulli random variables, corresponding to the transformation function $f(x)= \sum_{i=1}^n x_i$. Our algorithm learns to $\eps$-accuracy in poly$(n)$ time, using a surprising poly$(1/\eps)$ number of samples that is independent of $n.$ We also give an efficient algorithm that uses $\log n \cdot \poly(1/\eps)$ samples but has running time that is only $\poly(\log n, 1/\eps).$
First-order Logic: Modality and Intensionality
Venue: arXiv cs.LO 2011
Year: 2011

Contemporary use of the term 'intension' derives from the traditional logical Frege-Russell's doctrine that an idea (logic formula) has both an extension and an intension. From the Montague's point of view, the meaning of an idea can be considered as particular extensions in different possible worlds. In this paper we analyze the minimal intensional semantic enrichment of the syntax of the FOL language, by unification of different views: Tarskian extensional semantics of the FOL, modal interpretation of quantifiers, and a derivation of the Tarskian theory of truth from unified semantic theory based on a single meaning relation. We show that not all modal predicate logics are intensional, and that an equivalent modal Kripke's interpretation of logic quantifiers in FOL results in a particular pure extensional modal predicate logic (as is the standard Tarskian semantics of the FOL). This minimal intensional enrichment is obtained by adopting the theory of properties, relations and propositions (PRP) as the universe or domain of the FOL, composed by particulars and universals (or concepts), with the two-step interpretation of the FOL that eliminates the weak points of the Montague's intensional semantics. Differently from the Bealer's intensional FOL, we show that it is not necessary the introduction of the intensional abstraction in order to obtain the full intensional properties of the FOL. Final result of this paper is represented by the commutative homomorphic diagram that holds in each given possible world of this new intensional FOL, from the free algebra of the FOL syntax, toward its intensional algebra of concepts, and, successively, to the new extensional relational algebra (different from Cylindric algebras), and we show that it corresponds to the Tarski's interpretation of the standard extensional FOL in this possible world.
Scheduler Vulnerabilities and Attacks in Cloud Computing
Venue: arXiv cs.DC 2011
Year: 2011

In hardware virtualization a hypervisor provides multiple Virtual Machines (VMs) on a single physical system, each executing a separate operating system instance. The hypervisor schedules execution of these VMs much as the scheduler in an operating system does, balancing factors such as fairness and I/O performance. As in an operating system, the scheduler may be vulnerable to malicious behavior on the part of users seeking to deny service to others or maximize their own resource usage. Recently, publically available cloud computing services such as Amazon EC2 have used virtualization to provide customers with virtual machines running on the provider's hardware, typically charging by wall clock time rather than resources consumed. Under this business model, manipulation of the scheduler may allow theft of service at the expense of other customers, rather than merely reallocating resources within the same administrative domain. We describe a flaw in the Xen scheduler allowing virtual machines to consume almost all CPU time, in preference to other users, and demonstrate kernel-based and user-space versions of the attack. We show results demonstrating the vulnerability in the lab, consuming as much as 98% of CPU time regardless of fair share, as well as on Amazon EC2, where Xen modifications protect other users but still allow theft of service. In case of EC2, following the responsible disclosure model, we have reported this vulnerability to Amazon; they have since implemented a fix that we have tested and verified (See Appendix B). We provide a novel analysis of the necessary conditions for such attacks, and describe scheduler modifications to eliminate the vulnerability. We present experimental results demonstrating the effectiveness of these defenses while imposing negligible overhead.
Two-Bit Bit Flipping Decoding of LDPC Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.
Hiding Secret Information in Movie Clip: A Steganographic Approach
Venue: arXiv cs.MM 2011
Year: 2011

Establishing hidden communication is an important subject of discussion that has gained increasing importance nowadays with the development of the internet. One of the key methods for establishing hidden communication is steganography. Modern day steganography mainly deals with hiding information within files like image, text, html, binary files etc. These file contains small irrelevant information that can be substituted for small secret data. To store a high capacity secret data these carrier files are not very supportive. To overcome the problem of storing the high capacity secret data with the utmost security fence, we have proposed a novel methodology for concealing a voluminous data with high levels of security wall by using movie clip as a carrier file.