OpenRaiser/Intern-Atlas huggingface dataset:
Robust Simulations and Significant Separations
Venue: arXiv cs.CC 2010
Year: 2010

We define and study a new notion of "robust simulations" between complexity classes which is intermediate between the traditional notions of infinitely-often and almost-everywhere, as well as a corresponding notion of "significant separations". A language L has a robust simulation in a complexity class C if there is a language in C which agrees with L on arbitrarily large polynomial stretches of input lengths. There is a significant separation of L from C if there is no robust simulation of L in C. The new notion of simulation is a cleaner and more natural notion of simulation than the infinitely-often notion. We show that various implications in complexity theory such as the collapse of PH if NP = P and the Karp-Lipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory, such as hierarchy theorems, fixed polynomial circuit lower bounds, time-space tradeoffs, and the theorems of Allender and Williams, can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown. Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for non-deterministic polynomial time than the ones previously known.
Almost-Optimum Signature Matrices in Binary-Input Synchronous Overloaded CDMA
Venue: arXiv cs.IT 2010
Year: 2010

The everlasting bandwidth limitations in wireless communication networks has directed the researchers' thrust toward analyzing the prospect of overloaded Code Division Multiple Access (CDMA). In this paper, we have proposed a Genetic Algorithm in search of optimum signature matrices for binary-input synchronous CDMA. The main measure of optimality considered in this paper, is the per-user channel capacity of the overall multiple access system. Our resulting matrices differ from the renowned Welch Bound Equality (WBE) codes, regarding the fact that our attention is specifically aimed at binary, rather than Gaussian, input distributions. Since design based on channel capacity is computationally expensive, we have focused on introducing a set of alternative criteria that not only speed up the matrix formation procedure, but also maintain optimality. The Bit Error Rate (BER) and Constellation measures are our main criteria propositions. Simulation results also verify our analytical justifications.
Nondeterministic fuzzy automata
Venue: arXiv cs.AI 2010
Year: 2010

Fuzzy automata have long been accepted as a generalization of nondeterministic finite automata. A closer examination, however, shows that the fundamental property---nondeterminism---in nondeterministic finite automata has not been well embodied in the generalization. In this paper, we introduce nondeterministic fuzzy automata with or without $\el$-moves and fuzzy languages recognized by them. Furthermore, we prove that (deterministic) fuzzy automata, nondeterministic fuzzy automata, and nondeterministic fuzzy automata with $\el$-moves are all equivalent in the sense that they recognize the same class of fuzzy languages.
Transforming a random graph drawing into a Lombardi drawing
Venue: arXiv cs.DS 2010
Year: 2010

The visualization of any graph plays important role in various aspects, such as graph drawing software. Complex systems (like large databases or networks) that have a graph structure should be properly visualized in order to avoid obfuscation. One way to provide an aesthetic improvement to a graph visualization is to apply a force-directed drawing algorithm to it. This method, that emerged in the 60's views graphs as spring systems that exert forces (repulsive or attractive) to the nodes. A Lombardi drawing of a graph is a drawing where the edges are drawn as circular arcs (straight edges are considered circular arcs of infinite radius) with perfect angular resolution. This means, that consecutive edges around a vertex are equally spaced around it. In other words, each angle between the tangents of two consecutive edges is equal to $2π/d$ where d is the degree of that specific vertex. The requirement of using circular edges in graphs when we want to provide perfect angular resolution is necessary, since even cycle graphs cannot be drawn with straight edges when perfect angular resolution is needed. In this survey, we provide an algorithm that takes as input a random drawing of a graph and provides its Lombardi drawing, giving a proper visualization of the graph.
Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP
Venue: arXiv cs.CC 2010
Year: 2010

We investigate the complexity of integration and derivative for multivariate polynomials in the standard computation model. The integration is in the unit cube $[0,1]^d$ for a multivariate polynomial, which has format $f(x_1,\cdots, x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots, x_d)$, where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with all single variable polynomials $q_j(x_j)$ of degree at most two and constant coefficients. We show that there is no any factor polynomial time approximation for the integration $\int_{[0,1]^d}f(x_1,\cdots,x_d)d_{x_1}\cdots d_{x_d}$ unless $P=NP$. For the complexity of multivariate derivative, we consider the functions with the format $f(x_1,\cdots, x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots, x_d),$ where each $p_i(x_1,\cdots, x_d)$ is of degree at most $2$ and $0,1$ coefficients. We also show that unless $P=NP$, there is no any factor polynomial time approximation to its derivative ${\partial f^{(d)}(x_1,\cdots, x_d)\over \partial x_1\cdots \partial x_d}$ at the origin point $(x_1,\cdots, x_d)=(0,\cdots,0)$. Our results show that the derivative may not be easier than the integration in high dimension. We also give some tractable cases of high dimension integration and derivative.
Convergence and Next Generation Networks
Venue: arXiv cs.NI 2010
Year: 2010

The communications sector is undergoing significant changes, with the emergence of a number of platforms available to provide a different range of services. Some of these platforms are complementary to each other, while others are competitive, or can provide a valid substitute for some of the services provided. Up till now, the most important communications platform in most of the developing countries has been the public switched telecommunication network (PSTN) which provides access to all households and buildings. This universality in providing access has also meant that the network has generally been designated as one for universal service.This chapter focuses on the area where the most significant changes are taking place in the communication sector. The objective of this chapter is neither to give an overview of all communication platforms, nor is it aimed to assess the relative extent to which different platforms complement or compete with each other. The central theme of this chapter is to examine the developments in what is commonly refereed to as next generation access networks and next generation core networks and their role in convergence.
Solving the Rural Postman problem using the Adleman-Lipton model
Venue: arXiv cs.CC 2010
Year: 2010

In this survey we investigate the application of the Adleman-Lipton model on Rural Postman problem, which given an undirected graph $G=(V,E)$ with positive integer lengths on each of its edges and a subset $E^{'}\subseteq E$, asks whether there exists a hamiltonian circuit that includes each edge of $E^{'}$ and has total cost (sum of edge lengths) less or equal to a given integer B (we are allowed to use any edges of the set $E-E^{'}$, but we must use all edges of the set $E'$). The Rural Postman problem (RPP) is a very interesting NP-complete problem used, especially, in network optimization. RPP is actually a special case of the Route Inspection problem, where we need to traverse all edges of an undirected graph at a minimum total cost. As all NP-complete problems, it currently admits no efficient solution and if actually $P\neq NP$ as it is widely accepted to be, it cannot admit a polynomial time algorithm to solve it. The application of the Adleman-Lipton model on this problem, provides an efficient way to solve RPP, as it is the fact for many other hard problems on which the Adleman-Lipton model has been applied. In this survey, we provide a polynomial algorithm based on the Lipton-Adleman model, which solves the RPP in $\mathcal{O}(n^{2})$ time, where n refers to the input of the problem.
Approximating Vertex Cover in Dense Hypergraphs
Venue: arXiv cs.DS 2010
Year: 2010

We consider the minimum vertex cover problem in hypergraphs in which every hyperedge has size k (also known as minimum hitting set problem, or minimum set cover with element frequency k). Simple algorithms exist that provide k-approximations, and this is believed to be the best possible approximation achievable in polynomial time. We show how to exploit density and regularity properties of the input hypergraph to break this barrier. In particular, we provide a randomized polynomial-time algorithm with approximation factor k/(1 +(k-1)d/(k Delta)), where d and Delta are the average and maximum degree, respectively, and Delta must be Omega(n^{k-1}/log n). The proposed algorithm generalizes the recursive sampling technique of Imamura and Iwama (SODA'05) for vertex cover in dense graphs. As a corollary, we obtain an approximation factor k/(2-1/k) for subdense regular hypergraphs, which is shown to be the best possible under the unique games conjecture.
The 2-Center Problem in Three Dimensions
Venue: arXiv cs.CG 2010
Year: 2010

Let P be a set of n points in R^3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n^3 log^5 n) expected time, and the second algorithm runs in O((n^2 log^5 n) /(1-r*/r_0)^3) expected time, where r* is the radius of the 2-center balls of P and r_0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not too close to r_0, which is equivalent to the condition that the centers of the two covering balls be not too close to each other.
On Probabilistic Parallel Programs with Process Creation and Synchronisation
Venue: arXiv cs.LO 2010
Year: 2010

We initiate the study of probabilistic parallel programs with dynamic process creation and synchronisation. To this end, we introduce probabilistic split-join systems (pSJSs), a model for parallel programs, generalising both probabilistic pushdown systems (a model for sequential probabilistic procedural programs which is equivalent to recursive Markov chains) and stochastic branching processes (a classical mathematical model with applications in various areas such as biology, physics, and language processing). Our pSJS model allows for a possibly recursive spawning of parallel processes; the spawned processes can synchronise and return values. We study the basic performance measures of pSJSs, especially the distribution and expectation of space, work and time. Our results extend and improve previously known results on the subsumed models. We also show how to do performance analysis in practice, and present two case studies illustrating the modelling power of pSJSs.
Random Generation and Approximate Counting of Combinatorial Structures
Venue: arXiv cs.CC 2010
Year: 2010

The aim of this thesis is to determine classes of NP relations for which random generation and approximate counting problems admit an efficient solution. Since efficient rank implies efficient random generation, we first investigate some classes of NP relations admitting efficient ranking. On the other hand, there are situations in which efficient random generation is possible even when ranking is computationally infeasible. We introduce the notion of ambiguous description as a tool for random generation and approximate counting in such cases and show, in particular, some applications to the case of formal languages. Finally, we discuss a limit of an heuristic for combinatorial optimization problems based on the random initialization of local search algorithms showing that derandomizing such heuristic can be, in some cases, #P-hard.
Numerically Representing A Stochastic Process Algebra
Venue: arXiv cs.LO 2010
Year: 2010

The syntactic nature and compositionality characteristic of stochastic process algebras make models to be easily understood by human beings, but not convenient for machines as well as people to directly carry out mathematical analysis and stochastic simulation. This paper presents a numerical representation schema for the stochastic process algebra PEPA, which can provide a platform to directly and conveniently employ a variety of computational approaches to both qualitatively and quantitatively analyse the models. Moreover, these approaches developed on the basis of the schema are demonstrated and discussed. In particular, algorithms for automatically deriving the schema from a general PEPA model and simulating the model based on the derived schema to derive performance measures are presented.
Iterative Beam Search for Simple Assembly Line Balancing with a Fixed Number of Work Stations
Venue: arXiv cs.DM 2010
Year: 2010

The simple assembly line balancing problem (SALBP) concerns the assignment of tasks with pre-defined processing times to work stations that are arranged in a line. Hereby, precedence constraints between the tasks must be respected. The optimization goal of the SALBP-2 version of the problem concerns the minimization of the so-called cycle time, that is, the time in which the tasks of each work station must be completed. In this work we propose to tackle this problem with an iterative search method based on beam search. The proposed algorithm is able to obtain optimal, respectively best-known, solutions in 283 out of 302 test cases. Moreover, for 9 further test cases the algorithm is able to produce new best-known solutions. These numbers indicate that the proposed iterative beam search algorithm is currently a state-of-the-art method for the SALBP-2.
On the transfer matrix of a MIMO system
Venue: arXiv cs.IT 2010
Year: 2010

We develop a deterministic ab-initio model for the input-output relationship of a multiple-input multiple-output (MIMO) wireless channel, starting from the Maxwell equations combined with Ohm's Law. The main technical tools are scattering and geometric perturbation theories. The derived relationship can lead us to a deep understanding of how the propagation conditions and the coupling effects between the elements of multiple-element arrays affect the properties of a MIMO channel, e.g. its capacity and its number of degrees of freedom.
Curve Reconstruction in Riemannian Manifolds: Ordering Motion Frames
Venue: arXiv cs.CG 2010
Year: 2010

In this article we extend the computational geometric curve reconstruction approach to curves in Riemannian manifolds. We prove that the minimal spanning tree, given a sufficiently dense sample, correctly reconstructs the smooth arcs and further closed and simple curves in Riemannian manifolds. The proof is based on the behaviour of the curve segment inside the tubular neighbourhood of the curve. To take care of the local topological changes of the manifold, the tubular neighbourhood is constructed in consideration with the injectivity radius of the underlying Riemannian manifold. We also present examples of successfully reconstructed curves and show an applications of curve reconstruction to ordering motion frames.
Stochastic Vector Quantisers
Venue: arXiv cs.NE 2010
Year: 2010

In this paper a stochastic generalisation of the standard Linde-Buzo-Gray (LBG) approach to vector quantiser (VQ) design is presented, in which the encoder is implemented as the sampling of a vector of code indices from a probability distribution derived from the input vector, and the decoder is implemented as a superposition of reconstruction vectors, and the stochastic VQ is optimised using a minimum mean Euclidean reconstruction distortion criterion, as in the LBG case. Numerical simulations are used to demonstrate how this leads to self-organisation of the stochastic VQ, where different stochastically sampled code indices become associated with different input subspaces. This property may be used to automate the process of splitting high-dimensional input vectors into low-dimensional blocks before encoding them.
Negative bases and automata
Venue: arXiv cs.FL 2010
Year: 2010

We study expansions in non-integer negative base -β introduced by Ito and Sadahiro. Using countable automata associated with (-β)-expansions, we characterize the case where the (-β)-shift is a system of finite type. We prove that, if β is a Pisot number, then the (-β)-shift is a sofic system. In that case, addition (and more generally normalization on any alphabet) is realizable by a finite transducer. We then give an on-line algorithm for the conversion from positive base β to negative base -β. When β is a Pisot number, the conversion can be realized by a finite on-line transducer.
Queue-Aware Dynamic Clustering and Power Allocation for Network MIMO Systems via Distributive Stochastic Learning
Venue: arXiv cs.LG 2010
Year: 2010

In this paper, we propose a two-timescale delay-optimal dynamic clustering and power allocation design for downlink network MIMO systems. The dynamic clustering control is adaptive to the global queue state information (GQSI) only and computed at the base station controller (BSC) over a longer time scale. On the other hand, the power allocations of all the BSs in one cluster are adaptive to both intra-cluster channel state information (CCSI) and intra-cluster queue state information (CQSI), and computed at the cluster manager (CM) over a shorter time scale. We show that the two-timescale delay-optimal control can be formulated as an infinite-horizon average cost Constrained Partially Observed Markov Decision Process (CPOMDP). By exploiting the special problem structure, we shall derive an equivalent Bellman equation in terms of Pattern Selection Q-factor to solve the CPOMDP. To address the distributive requirement and the issue of exponential memory requirement and computational complexity, we approximate the Pattern Selection Q-factor by the sum of Per-cluster Potential functions and propose a novel distributive online learning algorithm to estimate the Per-cluster Potential functions (at each CM) as well as the Lagrange multipliers (LM) (at each BS). We show that the proposed distributive online learning algorithm converges almost surely (with probability 1). By exploiting the birth-death structure of the queue dynamics, we further decompose the Per-cluster Potential function into sum of Per-cluster Per-user Potential functions and formulate the instantaneous power allocation as a Per-stage QSI-aware Interference Game played among all the CMs. We also propose a QSI-aware Simultaneous Iterative Water-filling Algorithm (QSIWFA) and show that it can achieve the Nash Equilibrium (NE).
Interpolation in Equilibrium Logic and Answer Set Programming: the Propositional Case
Venue: arXiv cs.LO 2010
Year: 2010

Interpolation is an important property of classical and many non classical logics that has been shown to have interesting applications in computer science and AI. Here we study the Interpolation Property for the propositional version of the non-monotonic system of equilibrium logic, establishing weaker or stronger forms of interpolation depending on the precise interpretation of the inference relation. These results also yield a form of interpolation for ground logic programs under the answer sets semantics. For disjunctive logic programs we also study the property of uniform interpolation that is closely related to the concept of variable forgetting.
ECLiPSe - from LP to CLP
Venue: arXiv cs.PL 2010
Year: 2010

ECLiPSe is a Prolog-based programming system, aimed at the development and deployment of constraint programming applications. It is also used for teaching most aspects of combinatorial problem solving, e.g. problem modelling, constraint programming, mathematical programming, and search techniques. It uses an extended Prolog as its high-level modelling and control language, complemented by several constraint solver libraries, interfaces to third-party solvers, an integrated development environment and interfaces for embedding into host environments. This paper discusses language extensions, implementation aspects, components and tools that we consider relevant on the way from Logic Programming to Constraint Logic Programming.
A Force-Directed Method for Large Crossing Angle Graph Drawing
Venue: arXiv cs.HC 2010
Year: 2010

Recent empirical research has indicated that human graph reading performance improves when crossing angles increase. However, crossing angle has not been used as an aesthetic criterion for graph drawing algorithms so far. In this paper, we introduce a force-directed method that aims to construct graph drawings with large crossing angles. Experiments indicate that our method significantly increases crossing angles. Surprisingly, the experimental results further demonstrate that the resulting drawings produced by our method have fewer edge crossings, a shorter total edge length and more uniform edge lengths, compared to classical spring algorithms.
Directed factor graph based fault diagnosis model construction for mode switching satellite power system
Venue: arXiv cs.SY 2010
Year: 2010

Satellite power system is a complex, highly interconnected hybrid system that exhibit nonlinear and mode switching behaviors. Directed factor graph is an inference model for fault diagnosis using probabilistic reasoning techniques. A novel approach for constructing the directed factor graph structure based on hybrid bond graph model is proposed. The system components status and their fault symptoms are treated as hypothesis and evidences respectively. The cause-effect relations between hypothesis and evidences are identified and concluded though qualitative equations and causal path analysis on hybrid bond graph model. A power supply module of a satellite power system is provided as case study to show the feasibility and validity of the proposed method.
Towards Correctness of Program Transformations Through Unification and Critical Pair Computation
Venue: arXiv cs.PL 2010
Year: 2010

Correctness of program transformations in extended lambda calculi with a contextual semantics is usually based on reasoning about the operational semantics which is a rewrite semantics. A successful approach to proving correctness is the combination of a context lemma with the computation of overlaps between program transformations and the reduction rules, and then of so-called complete sets of diagrams. The method is similar to the computation of critical pairs for the completion of term rewriting systems. We explore cases where the computation of these overlaps can be done in a first order way by variants of critical pair computation that use unification algorithms. As a case study we apply the method to a lambda calculus with recursive let-expressions and describe an effective unification algorithm to determine all overlaps of a set of transformations with all reduction rules. The unification algorithm employs many-sorted terms, the equational theory of left-commutativity modelling multi-sets, context variables of different kinds and a mechanism for compactly representing binding chains in recursive let-expressions.