OpenRaiser/Intern-Atlas huggingface dataset:
Bisimilarity of Pushdown Systems is Nonelementary
Venue: arXiv cs.FL 2012
Year: 2012

Given two pushdown systems, the bisimilarity problem asks whether they are bisimilar. While this problem is known to be decidable our main result states that it is nonelementary, improving EXPTIME-hardness, which was the previously best known lower bound for this problem. Our lower bound result holds for normed pushdown systems as well.
Solving Linear System of Equations Via A Convex Hull Algorithm
Venue: arXiv cs.NA 2012
Year: 2012

We present new iterative algorithms for solving a square linear system $Ax=b$ in dimension $n$ by employing the {\it Triangle Algorithm} \cite{kal12}, a fully polynomial-time approximation scheme for testing if the convex hull of a finite set of points in a Euclidean space contains a given point. By converting $Ax=b$ into a convex hull problem and solving via the Triangle Algorithm, together with a {\it sensitivity theorem}, we compute in $O(n^2ε^{-2})$ arithmetic operations an approximate solution satisfying $\Vert Ax_ε- b \Vert \leq ερ$, where $ρ= \max \{\Vert a_1 \Vert,..., \Vert a_n \Vert, \Vert b \Vert \}$, and $a_i$ is the $i$-th column of $A$. In another approach we apply the Triangle Algorithm incrementally, solving a sequence of convex hull problems while repeatedly employing a {\it distance duality}. The simplicity and theoretical complexity bounds of the proposed algorithms, requiring no structural restrictions on the matrix $A$, suggest their potential practicality, offering alternatives to the existing exact and iterative methods, especially for large scale linear systems. The assessment of computational performance however is the subject of future experimentations.
Channel-Adaptive Sensing Strategy for Cognitive Radio Ad Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

In Cognitive Radio (CR) ad hoc networks, secondary users (SU) attempt to utilize valuable spectral resources without causing significant interference to licensed primary users (PU). While there is a large body of research on spectrum opportunity detection, exploitation, and adaptive transmission in CR, most existing approaches focus only on avoiding PU activity when making sensing decisions. Since the myopic sensing strategy results in congestion and poor throughput, several collision-avoidance sensing approaches were investigated in the literature. However, they provide limited improvement. A channel-aware myopic sensing strategy that adapts the reward to the fading channel state information (CSI) of the SU link is proposed. This CSI varies over the CR spectrum and from one SU pair to another due to multipath and shadow fading, thus randomizing sensing decisions and increasing the network throughput. The proposed joint CSI adaptation at the medium access control (MAC) and physical layers provides large throughput gain over randomized sensing strategies and/or conventional adaptive transmission methods. The performance of the proposed CSI-aided sensing strategy is validated for practical network scenarios and demonstrated to be robust to CSI mismatch, sensing errors, and spatial channel correlation.
Synthesis-by-analysis of BCH Codes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we propose a technique to blindly synthesize the generator polynomial of BCH codes. The proposed technique involves finding Greatest Common Divisor (GCD) among different codewords and block lengths. Based on this combinatorial GCD calculation, correlation values are found. For a valid block length, the iterative GCD calculation results either into generator polynomial or some of its higher order multiples. These higher order polynomials are factorized under modulo-2 operation, and one of the resulting factors is always the generator polynomial which further increases the correlation value. The resulting correlation plot for different polynomials shows very high values for correct block length and valid generator polynomial. Knowing the valid block length and generator polynomial, all other parameters including number of parity-check digits (n-k), minimum distance dmin and error correcting capability t are readily exposed.
The Model of Semantic Concepts Lattice For Data Mining Of Microblogs
Venue: arXiv cs.CL 2012
Year: 2012

The model of semantic concept lattice for data mining of microblogs has been proposed in this work. It is shown that the use of this model is effective for the semantic relations analysis and for the detection of associative rules of key words.
Bayesian inference and the world mind
Venue: arXiv cs.OH 2012
Year: 2012

Knowledge is a central concept within both Bayesian inference and the mathematical and philosophical program of logic and semiotics initiated by Charles Sanders Peirce and further developed by George Spencer-Brown and Louis Kauffman. The latter school is more philosophical than is usual with the practitioners of Bayesian inference and claims the existence of a world mind. When these two disciplines inform each other semiotics is provided with mathematical mechanism and Bayesian inference is seen to be closely related to the act of distinction, the fundamental basis of logic in the work of Spencer-Brown. This hybridization also suggests a definition for knowledge within Bayesian inference; a definition that has been curiously lacking. Given that Darwinian processes are physical implementations of Bayesian inference and are utilized within numerous scientific theories across a wide range of disciplines as mechanisms for the creation and evolution of knowledge we may view the conjunction of these theories, within universal Darwinism, as descriptive of a world mind. Placing the world mind in this context provides detailed support from the scientific literature and goes some way to refute the charges of mysticism which have been leveled at the semiotic approach.
A note on planar partial 3-trees
Venue: arXiv cs.DM 2012
Year: 2012

It implicitly follows from the work of [Colbourn, El-Mallah: On two dual classes of planar graphs. Discrete Mathematics 80(1): 21-40 (1990)] that every planar partial 3-tree is a subgraph of a planar 3-tree. This fact has already enabled to prove a couple of results for planar partial 3-trees by induction on the structure of the underlying planar 3-tree completion. We provide an explicit proof of this observation and strengthen it by showing that one can keep the plane drawing of the input graph unchanged.
On U-Statistics and Compressed Sensing I: Non-Asymptotic Average-Case Analysis
Venue: arXiv cs.IT 2012
Year: 2012

Hoeffding's U-statistics model combinatorial-type matrix parameters (appearing in CS theory) in a natural way. This paper proposes using these statistics for analyzing random compressed sensing matrices, in the non-asymptotic regime (relevant to practice). The aim is to address certain pessimisms of "worst-case" restricted isometry analyses, as observed by both Blanchard & Dossal, et. al. We show how U-statistics can obtain "average-case" analyses, by relating to statistical restricted isometry property (StRIP) type recovery guarantees. However unlike standard StRIP, random signal models are not required; the analysis here holds in the almost sure (probabilistic) sense. For Gaussian/bounded entry matrices, we show that both l1-minimization and LASSO essentially require on the order of k \cdot [\log((n-k)/u) + \sqrt{2(k/n) \log(n/k)}] measurements to respectively recover at least 1-5u fraction, and 1-4u fraction, of the signals. Noisy conditions are considered. Empirical evidence suggests our analysis to compare well to Donoho & Tanner's recent large deviation bounds for l0/l1-equivalence, in the regime of block lengths 1000-3000 with high undersampling (50-150 measurements); similar system sizes are found in recent CS implementation. In this work, it is assumed throughout that matrix columns are independently sampled.
Minimum Opaque Covers for Polygonal Regions
Venue: arXiv cs.CG 2012
Year: 2012

The Opaque Cover Problem (OCP), also known as the Beam Detector Problem, is the problem of finding, for a set S in Euclidean space, the minimum-length set F which intersects every straight line passing through S. In spite of its simplicity, the problem remains remarkably intractable. The aim of this paper is to establish a framework and fundamental results for minimum opaque covers where S is a polygonal region in two-dimensional space. We begin by giving some general results about opaque covers, and describe the close connection that the OCP has with the Point Goalie Problem. We then consider properties of graphical solutions to the OCP when S is a convex polygonal region in the plane.
Detecting Linear Block Codes in Noise using the GLRT
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the problem of distinguishing the noisy codewords of a known binary linear block code from a random bit sequence. We propose to use the generalized likelihood ratio test (GLRT) to solve this problem. We also give a formula to find approximate number of codewords required and compare our results with an existing method.
First Experiments with PowerPlay
Venue: arXiv cs.AI 2012
Year: 2012

Like a scientist or a playing child, PowerPlay not only learns new skills to solve given problems, but also invents new interesting problems by itself. By design, it continually comes up with the fastest to find, initially novel, but eventually solvable tasks. It also continually simplifies or compresses or speeds up solutions to previous tasks. Here we describe first experiments with PowerPlay. A self-delimiting recurrent neural network SLIM RNN is used as a general computational problem solving architecture. Its connection weights can encode arbitrary, self-delimiting, halting or non-halting programs affecting both environment (through effectors) and internal states encoding abstractions of event sequences. Our PowerPlay-driven SLIM RNN learns to become an increasingly general solver of self-invented problems, continually adding new problem solving procedures to its growing skill repertoire. Extending a recent conference paper, we identify interesting, emerging, developmental stages of our open-ended system. We also show how it automatically self-modularizes, frequently re-using code for previously invented skills, always trying to invent novel tasks that can be quickly validated because they do not require too many weight changes affecting too many previous tasks.
An Alignment Algorithm for Sequences
Venue: arXiv cs.IT 2012
Year: 2012

This paper describes a new alignment algorithm for sequences that can be used for determination of deletions and substitutions. It provides several solutions out of which the best one can be chosen on the basis of minimization of gaps or other considerations. The algorithm does not use similarity tables and it performs aspects of both global and local alignment. The algorithm is compared with other sequence alignment algorithms.
Capacity and Security of Heterogeneous Distributed Storage Systems
Venue: arXiv cs.DC 2012
Year: 2012

We study the capacity of heterogeneous distributed storage systems under repair dynamics. Examples of these systems include peer-to-peer storage clouds, wireless, and Internet caching systems. Nodes in a heterogeneous system can have different storage capacities and different repair bandwidths. We give lower and upper bounds on the system capacity. These bounds depend on either the average resources per node, or on a detailed knowledge of the node characteristics. Moreover, we study the case in which nodes may be compromised by an eavesdropper, and give bounds on the system secrecy capacity. One implication of our results is that symmetric repair maximizes the capacity of a homogeneous system, which justifies the model widely used in the literature.
Segmentation of ultrasound images of thyroid nodule for assisting fine needle aspiration cytology
Venue: arXiv cs.CV 2012
Year: 2012

The incidence of thyroid nodule is very high and generally increases with the age. Thyroid nodule may presage the emergence of thyroid cancer. The thyroid nodule can be completely cured if detected early. Fine needle aspiration cytology is a recognized early diagnosis method of thyroid nodule. There are still some limitations in the fine needle aspiration cytology, and the ultrasound diagnosis of thyroid nodule has become the first choice for auxiliary examination of thyroid nodular disease. If we could combine medical imaging technology and fine needle aspiration cytology, the diagnostic rate of thyroid nodule would be improved significantly. The properties of ultrasound will degrade the image quality, which makes it difficult to recognize the edges for physicians. Image segmentation technique based on graph theory has become a research hotspot at present. Normalized cut (Ncut) is a representative one, which is suitable for segmentation of feature parts of medical image. However, how to solve the normalized cut has become a problem, which needs large memory capacity and heavy calculation of weight matrix. It always generates over segmentation or less segmentation which leads to inaccurate in the segmentation. The speckle noise in B ultrasound image of thyroid tumor makes the quality of the image deteriorate. In the light of this characteristic, we combine the anisotropic diffusion model with the normalized cut in this paper. After the enhancement of anisotropic diffusion model, it removes the noise in the B ultrasound image while preserves the important edges and local details. This reduces the amount of computation in constructing the weight matrix of the improved normalized cut and improves the accuracy of the final segmentation results. The feasibility of the method is proved by the experimental results.
On the Non-existence of Lattice Tilings by Quasi-crosses
Venue: arXiv cs.IT 2012
Year: 2012

We study necessary conditions for the existence of lattice tilings of $\R^n$ by quasi-crosses. We prove non-existence results, and focus in particular on the two smallest unclassified shapes, the $(3,1,n)$-quasi-cross and the $(3,2,n)$-quasi-cross. We show that for dimensions $n\leq 250$, apart from the known constructions, there are no lattice tilings of $\R^n$ by $(3,1,n)$-quasi-crosses except for ten remaining cases, and no lattice tilings of $\R^n$ by $(3,2,n)$-quasi-crosses except for eleven remaining cases.
Generation of Two-Layer Monotonic Functions
Venue: arXiv cs.NE 2012
Year: 2012

The problem of implementing a class of functions with particular conditions by using monotonic multilayer functions is considered. A genetic algorithm is used to create monotonic functions of a certain class, and these are implemented with two-layer monotonic functions. The existence of a solution to the given problem suggests that from two monotone functions, a monotonic function with the same dimensions can be created. A new algorithm based on the genetic algorithm is proposed, which easily implemented two-layer monotonic functions of a specific class for up to six variables.
Student Modeling using Case-Based Reasoning in Conventional Learning System
Venue: arXiv cs.AI 2012
Year: 2012

Conventional face-to-face classrooms are still the main learning system applied in Indonesia. In assisting such conventional learning towards an optimal learning, formative evaluations are needed to monitor the progress of the class. This task can be very hard when the size of the class is large. Hence, this research attempted to create a classroom monitoring system based on student data of Department of Electrical Engineering and Information Technology. In order to achieve the goal, a student modeling using Case-Based Reasoning was proposed. A generic student model based on a framework was developed. The model represented student knowledge of a subject. The result showed that the system was able to store and retrieve student data for suggestion of the current situation and formative evaluation for one of the subject in the Department.
Brain Computer Interface Technologies in the Coming Decades
Venue: arXiv cs.HC 2012
Year: 2012

As the proliferation of technology dramatically infiltrates all aspects of modern life, in many ways the world is becoming so dynamic and complex that technological capabilities are overwhelming human capabilities to optimally interact with and leverage those technologies. Fortunately, these technological advancements have also driven an explosion of neuroscience research over the past several decades, presenting engineers with a remarkable opportunity to design and develop flexible and adaptive brain-based neurotechnologies that integrate with and capitalize on human capabilities and limitations to improve human-system interactions. Major forerunners of this conception are brain-computer interfaces (BCIs), which to this point have been largely focused on improving the quality of life for particular clinical populations and include, for example, applications for advanced communications with paralyzed or locked in patients as well as the direct control of prostheses and wheelchairs. Near-term applications are envisioned that are primarily task oriented and are targeted to avoid the most difficult obstacles to development. In the farther term, a holistic approach to BCIs will enable a broad range of task-oriented and opportunistic applications by leveraging pervasive technologies and advanced analytical approaches to sense and merge critical brain, behavioral, task, and environmental information. Communications and other applications that are envisioned to be broadly impacted by BCIs are highlighted; however, these represent just a small sample of the potential of these technologies.
Decoding Delay Minimization in Inter-Session Network Coding
Venue: arXiv cs.IT 2012
Year: 2012

Intra-session network coding has been shown to offer significant gains in terms of achievable throughput and delay in settings where one source multicasts data to several clients. In this paper, we consider a more general scenario where multiple sources transmit data to sets of clients and study the benefits of inter-session network coding, when network nodes have the opportunity to combine packets from different sources. In particular, we propose a novel framework for optimal rate allocation in inter-session network coding systems. We formulate the problem as the minimization of the average decoding delay in the client population and solve it with a gradient-based stochastic algorithm. Our optimized inter-session network coding solution is evaluated in different network topologies and compared with basic intra-session network coding solutions. Our results show the benefits of proper coding decisions and effective rate allocation for lowering the decoding delay when the network is used by concurrent multicast sessions.
Jointly Optimal Sensing and Resource Allocation for Multiuser Overlay Cognitive Radios
Venue: arXiv cs.NI 2012
Year: 2012

Successful deployment of cognitive radios requires efficient sensing of the spectrum and dynamic adaptation of the available resources according to the sensed (imperfect) information. While most works design these two tasks separately, in this paper we address them jointly. In particular, we investigate an overlay cognitive radio with multiple secondary users that access orthogonally a set of frequency bands originally devoted to primary users. The schemes are designed to minimize the cost of sensing, maximize the performance of the secondary users (weighted sum rate), and limit the probability of interfering the primary users. The joint design is addressed using dynamic programming and nonlinear optimization techniques. A two-step strategy that first finds the optimal resource allocation for any sensing scheme and then uses that solution as input to solve for the optimal sensing policy is implemented. The two-step strategy is optimal, gives rise to intuitive optimal policies, and entails a computational complexity much lower than that required to solve the original formulation.
Adaptive Bee Colony in an Artificial Bee Colony for Solving Engineering Design Problems
Venue: arXiv cs.CE 2012
Year: 2012

A wide range of engineering design problems have been solved by the algorithms that simulates collective intelligence in swarms of birds or insects. The Artificial Bee Colony or ABC is one of the recent additions to the class of swarm intelligence based algorithms that mimics the foraging behavior of honey bees. ABC consists of three groups of bees namely employed, onlooker and scout bees. In ABC, the food locations represent the potential candidate solution. In the present study an attempt is made to generate the population of food sources (Colony Size) adaptively and the variant is named as A-ABC. A-ABC is further enhanced to improve convergence speed and exploitation capability, by employing the concept of elitism, which guides the bees towards the best food source. This enhanced variant is called E-ABC. The proposed algorithms are validated on a set of standard benchmark problems with varying dimensions taken from literature and on five engineering design problems. The numerical results are compared with the basic ABC and three recent variant of ABC. Numerically and statistically simulated results illustrate that the proposed method is very efficient and competitive.
Detecting, Representing and Querying Collusion in Online Rating Systems
Venue: arXiv cs.CR 2012
Year: 2012

Online rating systems are subject to malicious behaviors mainly by posting unfair rating scores. Users may try to individually or collaboratively promote or demote a product. Collaborating unfair rating 'collusion' is more damaging than individual unfair rating. Although collusion detection in general has been widely studied, identifying collusion groups in online rating systems is less studied and needs more investigation. In this paper, we study impact of collusion in online rating systems and asses their susceptibility to collusion attacks. The proposed model uses a frequent itemset mining algorithm to detect candidate collusion groups. Then, several indicators are used for identifying collusion groups and for estimating how damaging such colluding groups might be. Also, we propose an algorithm for finding possible collusive subgroup inside larger groups which are not identified as collusive. The model has been implemented and we present results of experimental evaluation of our methodology.
Beyond Worst-Case Analysis in Private Singular Vector Computation
Venue: arXiv cs.DS 2012
Year: 2012

We consider differentially private approximate singular vector computation. Known worst-case lower bounds show that the error of any differentially private algorithm must scale polynomially with the dimension of the singular vector. We are able to replace this dependence on the dimension by a natural parameter known as the coherence of the matrix that is often observed to be significantly smaller than the dimension both theoretically and empirically. We also prove a matching lower bound showing that our guarantee is nearly optimal for every setting of the coherence parameter. Notably, we achieve our bounds by giving a robust analysis of the well-known power iteration algorithm, which may be of independent interest. Our algorithm also leads to improvements in worst-case settings and to better low-rank approximations in the spectral norm.