OpenRaiser/Intern-Atlas huggingface dataset:
Runtime-Flexible Multi-dimensional Arrays and Views for C++98 and C++0x
Venue: arXiv cs.DS 2010
Year: 2010

Multi-dimensional arrays are among the most fundamental and most useful data structures of all. In C++, excellent template libraries exist for arrays whose dimension is fixed at runtime. Arrays whose dimension can change at runtime have been implemented in C. However, a generic object-oriented C++ implementation of runtime-flexible arrays has so far been missing. In this article, we discuss our new implementation called Marray, a package of class templates that fills this gap. Marray is based on views as an underlying concept. This concept brings some of the flexibility known from script languages such as R and MATLAB to C++. Marray is free both for commercial and non-commercial use and is publicly available from www.andres.sc/marray
Motion planning with pull moves
Venue: arXiv cs.CC 2010
Year: 2010

It is well known that Sokoban is PSPACE-complete (Culberson 1998) and several of its variants are NP-hard (Demaine et al. 2003). In this paper we prove the NP-hardness of some variants of Sokoban where the warehouse keeper can only pull boxes.
Achievable Rates in Two-user Interference Channels with Finite Inputs and (Very) Strong Interference
Venue: arXiv cs.IT 2010
Year: 2010

For two-user interference channels, the capacity is known for the case where interference is stronger than the desired signal. Moreover, it is known that if the interference is above a certain level, it does not reduce the capacity at all. To achieve this capacity, the channel inputs need to be Gaussian distributed. However, Gaussian signals are continuous and unbounded. Thus, they are not well suited for practical applications. In this paper, we investigate the achievable rates if the channel inputs are restricted to finite constellations. Moreover, we will show by numerical simulations that rotating one of these input alphabets in the complex plane can increase the achievable rate region. Finally, we show that the threshold at which the single-user rates are achieved also depends on this rotation.
2-FREE-FLOOD-IT is polynomial
Venue: arXiv cs.DS 2010
Year: 2010

We study a discrete diffusion process introduced in some combinatorial games called FLOODIT and MADVIRUS that can be played online and whose computational complexity has been recently studied by Arthur et al (FUN'2010). The flooding dynamics used in those games can be defined for any colored graph. It has been shown in a first report (in french, hal-00509488 on HAL archive) that studying this dynamics directly on general graph is a valuable approach to understand its specificities and extract uncluttered key patterns or algorithms that can be applied with success to particular cases like the square grid of FLOODIT or the hexagonal grid of MADVIRUS, and many other classes of graphs. This report is the translation from french to english of the section in the french report showing that the variant of the problem called 2-FREE-FLOOD-IT can be solved with a polynomial algorithm, answering a question raised in the previous study of FLOODIT by Arthur et al.
Don't 'have a clue'? Unsupervised co-learning of downward-entailing operators
Venue: arXiv cs.CL 2010
Year: 2010

Researchers in textual entailment have begun to consider inferences involving 'downward-entailing operators', an interesting and important class of lexical items that change the way inferences are made. Recent work proposed a method for learning English downward-entailing operators that requires access to a high-quality collection of 'negative polarity items' (NPIs). However, English is one of the very few languages for which such a list exists. We propose the first approach that can be applied to the many languages for which there is no pre-existing high-precision database of NPIs. As a case study, we apply our method to Romanian and show that our method yields good results. Also, we perform a cross-linguistic analysis that suggests interesting connections to some findings in linguistic typology.
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Venue: arXiv cs.DS 2010
Year: 2010

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms with identical guarantees for general integer knapsack, the multidimensional knapsack problem (with a constant number of constraints) and for contingency tables (with a constant number of rows). Previously, only randomized approximation schemes were known for these problems due to work by Morris and Sinclair and work by Dyer. Our algorithms work by constructing small-width, read-once branching programs for approximating the underlying solution space under a carefully chosen distribution. As a byproduct of this approach, we obtain new query algorithms for learning functions of k halfspaces with respect to the uniform distribution on {0,1}^n. The running time of our algorithm is polynomial in the accuracy parameter eps. Previously even for the case of k=2, only algorithms with an exponential dependence on eps were known.
Proximity Drawings of High-Degree Trees
Venue: arXiv cs.CG 2010
Year: 2010

A drawing of a given (abstract) tree that is a minimum spanning tree of the vertex set is considered aesthetically pleasing. However, such a drawing can only exist if the tree has maximum degree at most 6. What can be said for trees of higher degree? We approach this question by supposing that a partition or covering of the tree by subtrees of bounded degree is given. Then we show that if the partition or covering satisfies some natural properties, then there is a drawing of the entire tree such that each of the given subtrees is drawn as a minimum spanning tree of its vertex set.
On minimum vertex cover of generalized Petersen graphs
Venue: arXiv cs.DM 2010
Year: 2010

For natural numbers $n$ and $k$ ($n > 2k$), a generalized Petersen graph $P(n,k)$, is defined by vertex set $\lbrace u_i,v_i\rbrace$ and edge set $\lbrace u_iu_{i+1},u_iv_i,v_iv_{i+k}\rbrace$; where $i = 1,2,\dots,n$ and subscripts are reduced modulo $n$. Here first, we characterize minimum vertex covers in generalized Petersen graphs. Second, we present a lower bound and some upper bounds for $β(P(n,k))$, the size of minimum vertex cover of $P(n,k)$. Third, in some cases, we determine the exact values of $β(P(n,k))$. Our conjecture is that $β(P(n,k)) \le n + \lceil\frac{n}{5}\rceil$, for all $n$ and $k$.
An approximation algorithm for the total cover problem
Venue: arXiv cs.DS 2010
Year: 2010

We introduce a $2$-approximation algorithm for the minimum total covering number problem.
Proofs for an Abstraction of Continuous Dynamical Systems Utilizing Lyapunov Functions
Venue: arXiv cs.SY 2010
Year: 2010

In this report proofs are presented for a method for abstracting continuous dynamical systems by timed automata. The method is based on partitioning the state space of dynamical systems with invariant sets, which form cells representing locations of the timed automata. To enable verification of the dynamical system based on the abstraction, conditions for obtaining sound, complete, and refinable abstractions are set up. It is proposed to partition the state space utilizing sub-level sets of Lyapunov functions, since they are positive invariant sets. The existence of sound abstractions for Morse-Smale systems and complete and refinable abstractions for linear systems are proved.
Modeling Spammer Behavior: Naïve Bayes vs. Artificial Neural Networks
Venue: arXiv cs.IR 2010
Year: 2010

Addressing the problem of spam emails in the Internet, this paper presents a comparative study on Naïve Bayes and Artificial Neural Networks (ANN) based modeling of spammer behavior. Keyword-based spam email filtering techniques fall short to model spammer behavior as the spammer constantly changes tactics to circumvent these filters. The evasive tactics that the spammer uses are themselves patterns that can be modeled to combat spam. It has been observed that both Naïve Bayes and ANN are best suitable for modeling spammer common patterns. Experimental results demonstrate that both of them achieve a promising detection rate of around 92%, which is considerably an improvement of performance compared to the keyword-based contemporary filtering approaches.
Modelling of Multi-Agent Systems: Experiences with Membrane Computing and Future Challenges
Venue: arXiv cs.MA 2010
Year: 2010

Formal modelling of Multi-Agent Systems (MAS) is a challenging task due to high complexity, interaction, parallelism and continuous change of roles and organisation between agents. In this paper we record our research experience on formal modelling of MAS. We review our research throughout the last decade, by describing the problems we have encountered and the decisions we have made towards resolving them and providing solutions. Much of this work involved membrane computing and classes of P Systems, such as Tissue and Population P Systems, targeted to the modelling of MAS whose dynamic structure is a prominent characteristic. More particularly, social insects (such as colonies of ants, bees, etc.), biology inspired swarms and systems with emergent behaviour are indicative examples for which we developed formal MAS models. Here, we aim to review our work and disseminate our findings to fellow researchers who might face similar challenges and, furthermore, to discuss important issues for advancing research on the application of membrane computing in MAS modelling.
Efficient Approaches for Designing Fault Tolerant Reversible Carry Look-Ahead and Carry-Skip Adders
Venue: arXiv cs.AR 2010
Year: 2010

Combinational or Classical logic circuits dissipate heat for every bit of information that is lost. Information is lost when the input vector cannot be recovered from its corresponding output vector. Reversible logic circuit implements only the functions having one-to-one mapping between its input and output vectors and therefore naturally takes care of heating. Reversible logic design becomes one of the promising research directions in low power dissipating circuit design in the past few years and has found its application in low power CMOS design, digital signal processing and nanotechnology. This paper presents the efficient approaches for designing fault tolerant reversible fast adders that implement carry look-ahead and carry-skip logic. The proposed high speed reversible adders include MIG gates for the realization of its basic building block. The MIG gate is universal and parity preserving. It allows any fault that affects no more than a single signal readily detectable at the circuit's primary outputs. It has also been demonstrated that the proposed design offers less hardware complexity and is efficient in terms of gate count, garbage outputs and constant inputs than the existing counterparts.
Quantum realization of extensive games
Venue: arXiv cs.GT 2010
Year: 2010

We generalize a concept of classical finite extensive game to make it useful for application of quantum objects. The generalization extends a quantum realization scheme of static games to any finite extensive game. It represents an extension of any classical finite extensive games to the quantum domain. In addition our model is compatible with well-known quantum schemes of static games. The paper is summed up by two examples.
Comparative study of the Pros and Cons of Programming languages Java, Scala, C++, Haskell, VB .NET, AspectJ, Perl, Ruby, PHP & Scheme - a Team 11 COMP6411-S10 Term Report
Venue: arXiv cs.PL 2010
Year: 2010

With the advent of numerous languages it is difficult to realize the edge of one language in a particular scope over another one. We are making an effort, realizing these few issues and comparing some main stream languages like Java, Scala, C++, Haskell, VB .NET, AspectJ, Perl, Ruby, PHP and Scheme keeping in mind some core issues in program development.
Memristor-based Circuits for Performing Basic Arithmetic Operations
Venue: arXiv cs.AR 2010
Year: 2010

In almost all of the currently working circuits, especially in analog circuits implementing signal processing applications, basic arithmetic operations such as multiplication, addition, subtraction and division are performed on values which are represented by voltages or currents. However, in this paper, we propose a new and simple method for performing analog arithmetic operations which in this scheme, signals are represented and stored through a memristance of the newly found circuit element, i.e. memristor, instead of voltage or current. Some of these operators such as divider and multiplier are much simpler and faster than their equivalent voltage-based circuits and they require less chip area. In addition, a new circuit is designed for programming the memristance of the memristor with predetermined analog value. Presented simulation results demonstrate the effectiveness and the accuracy of the proposed circuits.
Bit-size estimates for triangular sets in positive dimension
Venue: arXiv cs.SC 2010
Year: 2010

We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over Q. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends results by the first and last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and inter- polation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.
A Novel Quantum Cost Efficient Reversible Full Adder Gate in Nanotechnology
Venue: arXiv cs.AR 2010
Year: 2010

Reversible logic has become one of the promising research directions in low power dissipating circuit design in the past few years and has found its applications in low power CMOS design, cryptography, optical information processing and nanotechnology. This paper presents a novel and quantum cost efficient reversible full adder gate in nanotechnology. This gate can work singly as a reversible full adder unit and requires only one clock cycle. The proposed gate is a universal gate in the sense that it can be used to synthesize any arbitrary Boolean functions. It has been demonstrated that the hardware complexity offered by the proposed gate is less than the existing counterparts. The proposed reversible full adder gate also adheres to the theoretical minimum established by the researchers.
Ultrametric and Generalized Ultrametric in Computational Logic and in Data Analysis
Venue: arXiv cs.LO 2010
Year: 2010

Following a review of metric, ultrametric and generalized ultrametric, we review their application in data analysis. We show how they allow us to explore both geometry and topology of information, starting with measured data. Some themes are then developed based on the use of metric, ultrametric and generalized ultrametric in logic. In particular we study approximation chains in an ultrametric or generalized ultrametric context. Our aim in this work is to extend the scope of data analysis by facilitating reasoning based on the data analysis; and to show how quantitative and qualitative data analysis can be incorporated into logic programming.
Congestion in planar graphs with demands on faces
Venue: arXiv cs.DM 2010
Year: 2010

We give an algorithm to route a multicommodity flow in a planar graph $G$ with congestion $O(\log k)$, where $k$ is the maximum number of terminals on the boundary of a face, when each demand edge lie on a face of $G$. We also show that our specific method cannot achieve a substantially better congestion.
Sorting Network for Reversible Logic Synthesis
Venue: arXiv cs.AR 2010
Year: 2010

In this paper, we have introduced an algorithm to implement a sorting network for reversible logic synthesis based on swapping bit strings. The algorithm first constructs a network in terms of n*n Toffoli gates read from left to right. The number of gates in the circuit produced by our algorithm is then reduced by template matching and removing useless gates from the network. We have also compared the efficiency of the proposed method with the existing ones.
Data Cleaning and Query Answering with Matching Dependencies and Matching Functions
Venue: arXiv cs.DB 2010
Year: 2010

Matching dependencies were recently introduced as declarative rules for data cleaning and entity resolution. Enforcing a matching dependency on a database instance identifies the values of some attributes for two tuples, provided that the values of some other attributes are sufficiently similar. Assuming the existence of matching functions for making two attributes values equal, we formally introduce the process of cleaning an instance using matching dependencies, as a chase-like procedure. We show that matching functions naturally introduce a lattice structure on attribute domains, and a partial order of semantic domination between instances. Using the latter, we define the semantics of clean query answering in terms of certain/possible answers as the greatest lower bound/least upper bound of all possible answers obtained from the clean instances. We show that clean query answering is intractable in some cases. Then we study queries that behave monotonically wrt semantic domination order, and show that we can provide an under/over approximation for clean answers to monotone queries. Moreover, non-monotone positive queries can be relaxed into monotone queries.
Proliferating cell nuclear antigen (PCNA) allows the automatic identification of follicles in microscopic images of human ovarian tissue
Venue: arXiv cs.CV 2010
Year: 2010

Human ovarian reserve is defined by the population of nongrowing follicles (NGFs) in the ovary. Direct estimation of ovarian reserve involves the identification of NGFs in prepared ovarian tissue. Previous studies involving human tissue have used hematoxylin and eosin (HE) stain, with NGF populations estimated by human examination either of tissue under a microscope, or of images taken of this tissue. In this study we replaced HE with proliferating cell nuclear antigen (PCNA), and automated the identification and enumeration of NGFs that appear in the resulting microscopic images. We compared the automated estimates to those obtained by human experts, with the "gold standard" taken to be the average of the conservative and liberal estimates by three human experts. The automated estimates were within 10% of the "gold standard", for images at both 100x and 200x magnifications. Automated analysis took longer than human analysis for several hundred images, not allowing for breaks from analysis needed by humans. Our results both replicate and improve on those of previous studies involving rodent ovaries, and demonstrate the viability of large-scale studies of human ovarian reserve using a combination of immunohistochemistry and computational image analysis techniques.
A stabilized mixed formulation for unsteady Brinkman equation based on the method of horizontal lines
Venue: arXiv cs.NA 2010
Year: 2010

In this paper, we present a stabilized mixed formulation for unsteady Brinkman equation. The formulation is systematically derived based on the variational multiscale formalism and the method of horizontal lines. The derivation does not need the assumption that the fine-scale variables do not depend on the time, which is the case with the conventional derivation of multiscale stabilized formulations for transient mixed problems. An expression for the stabilization parameter is obtained in terms of a bubble function, and appropriate bubble functions for various finite elements are also presented. Under the proposed formulation, equal-order interpolation for the velocity and pressure (which is computationally the most convenient) is stable. Representative numerical results are presented to illustrate the performance of the proposed formulation. Spatial and temporal convergence studies are also performed, and the proposed formulation performed well.
Combinatorial Approximation Algorithms for MaxCut using Random Walks
Venue: arXiv cs.DS 2010
Year: 2010

We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant b > 1.5, there is an O(n^{b}) algorithm that outputs a (0.5+delta)-approximation for Maxcut, where delta = delta(b) is some positive constant. One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex $i$ and a conductance parameter phi, unless a random walk of length ell = O(log n) starting from i mixes rapidly (in terms of phi and ell), we can find a cut of conductance at most phi close to the vertex. The work done per vertex found in the cut is sublinear in n.
Power Control with Imperfect Exchanges and Applications to Spectrum Sharing
Venue: arXiv cs.NI 2010
Year: 2010

In various applications, the effect of errors in gradient-based iterations is of particular importance when seeking saddle points of the Lagrangian function associated with constrained convex optimization problems. Of particular interest here are problems arising in power control applications, where network utility is maximized subject to minimum signal-to-interference-plus-noise ratio (SINR) constraints, maximum interference constraints, maximum received power constraints, or simultaneous minimum and maximum SINR constraints. Especially when the gradient iterations are executed in a disributed fashion, imperfect exchanges among the link nodes may result in erroneous gradient vectors. In order to assess and cope with such errors, two running averages (ergodic sequences) are formed from the iterates generated by the perturbed saddle point method, each with complementary strengths. Under the assumptions of problem convexity and error boundedness, bounds on the constraint violation and the suboptimality per iteration index are derived. The two types of running averages are tested on a spectrum sharing problem with minimum and maximum SINR constraints, as well as maximum interference constraints.
Cognitive Radio Transmission Strategies for Primary Erasure Channels
Venue: arXiv cs.IT 2010
Year: 2010

A fundamental problem in cognitive radio systems is that the cognitive radio is ignorant of the primary channel state and the interference it inflicts on the primary license holder. In this paper we assume that the primary transmitter sends packets across an erasure channel and the primary receiver employs ACK/NAK feedback (ARQ) to retransmit erased packets. The cognitive radio can eavesdrop on the primary's ARQs. Assuming the primary channel states follow a Markov chain, this feedback gives the cognitive radio an indication of the primary link quality. Based on the ACK/NACK received, we devise optimal transmission strategies for the cognitive radio so as to maximize a weighted sum of primary and secondary throughput. The actual weight used during network operation is determined by the degree of protection afforded to the primary link. We study a two-state model where we characterize a scheme that spans the boundary of the primary-secondary rate region. Moreover, we study a three-state model where we derive the optimal strategy using dynamic programming. We also show via simulations that our optimal strategies achieve gains over the simple greedy algorithm for a range of primary channel parameters.