OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Label MRF Optimization via Least Squares s-t Cuts
Venue: arXiv cs.CV 2009
Year: 2009

There are many applications of graph cuts in computer vision, e.g. segmentation. We present a novel method to reformulate the NP-hard, k-way graph partitioning problem as an approximate minimal s-t graph cut problem, for which a globally optimal solution is found in polynomial time. Each non-terminal vertex in the original graph is replaced by a set of ceil(log_2(k)) new vertices. The original graph edges are replaced by new edges connecting the new vertices to each other and to only two, source s and sink t, terminal nodes. The weights of the new edges are obtained using a novel least squares solution approximating the constraints of the initial k-way setup. The minimal s-t cut labels each new vertex with a binary (s vs t) "Gray" encoding, which is then decoded into a decimal label number that assigns each of the original vertices to one of k classes. We analyze the properties of the approximation and present quantitative as well as qualitative segmentation results.
Evidence of coevolution in multi-objective evolutionary algorithms
Venue: arXiv cs.NE 2009
Year: 2009

This paper demonstrates that simple yet important characteristics of coevolution can occur in evolutionary algorithms when only a few conditions are met. We find that interaction-based fitness measurements such as fitness (linear) ranking allow for a form of coevolutionary dynamics that is observed when 1) changes are made in what solutions are able to interact during the ranking process and 2) evolution takes place in a multi-objective environment. This research contributes to the study of simulated evolution in a at least two ways. First, it establishes a broader relationship between coevolution and multi-objective optimization than has been previously considered in the literature. Second, it demonstrates that the preconditions for coevolutionary behavior are weaker than previously thought. In particular, our model indicates that direct cooperation or competition between species is not required for coevolution to take place. Moreover, our experiments provide evidence that environmental perturbations can drive coevolutionary processes; a conclusion that mirrors arguments put forth in dual phase evolution theory. In the discussion, we briefly consider how our results may shed light onto this and other recent theories of evolution.
The Self-Organization of Interaction Networks for Nature-Inspired Optimization
Venue: arXiv cs.NE 2009
Year: 2009

Over the last decade, significant progress has been made in understanding complex biological systems, however there have been few attempts at incorporating this knowledge into nature inspired optimization algorithms. In this paper, we present a first attempt at incorporating some of the basic structural properties of complex biological systems which are believed to be necessary preconditions for system qualities such as robustness. In particular, we focus on two important conditions missing in Evolutionary Algorithm populations; a self-organized definition of locality and interaction epistasis. We demonstrate that these two features, when combined, provide algorithm behaviors not observed in the canonical Evolutionary Algorithm or in Evolutionary Algorithms with structured populations such as the Cellular Genetic Algorithm. The most noticeable change in algorithm behavior is an unprecedented capacity for sustainable coexistence of genetically distinct individuals within a single population. This capacity for sustained genetic diversity is not imposed on the population but instead emerges as a natural consequence of the dynamics of the system.
Multi-User MISO Interference Channels with Single-User Detection: Optimality of Beamforming and the Achievable Rate Region
Venue: arXiv cs.IT 2009
Year: 2009

For a multi-user interference channel with multi-antenna transmitters and single-antenna receivers, by restricting each transmitter to Gaussian input and each receiver to a single-user detector, computing the largest achievable rate region amounts to solving a family of non-convex optimization problems. Recognizing the intrinsic connection between the signal power at the intended receiver and the interference power at the unintended receiver, the original family of non-convex optimization problems is converted into a new family of convex optimization problems. It is shown that, for such interference channels with each receiver implementing single-user detection, transmitter beamforming can achieve all boundary points of the achievable rate region.
Adaptation and Self-Organization in Evolutionary Algorithms
Venue: arXiv cs.NE 2009
Year: 2009

Abbreviated Abstract: The objective of Evolutionary Computation is to solve practical problems (e.g. optimization, data mining) by simulating the mechanisms of natural evolution. This thesis addresses several topics related to adaptation and self-organization in evolving systems with the overall aims of improving the performance of Evolutionary Algorithms (EA), understanding its relation to natural evolution, and incorporating new mechanisms for mimicking complex biological systems.
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Venue: arXiv cs.FL 2009
Year: 2009

Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over $\{0,1\}$ without two consecutive 1. Given a set $X$ of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not $X$ is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.
High-Rate Full-Diversity Space-Time Block Codes for Three and Four Transmit Antennas
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we deal with the design of high-rate, full-diversity, low maximum likelihood (ML) decoding complexity space-time block codes (STBCs) with code rates of 2 and 1.5 complex symbols per channel use for multiple-input multiple output (MIMO) systems employing three and four transmit antennas. We fill the empty slots of the existing STBCs from CIODs in their transmission matrices by additional symbols and use the conditional ML decoding technique which significantly reduces the ML decoding complexity of non-orthogonal STBCs while ensuring full-diversity and high coding gain. First, two new schemes with code rates of 2 and 1.5 are proposed for MIMO systems with four transmit antennas. We show that our low-complexity rate-2 STBC outperforms the corresponding best STBC recently proposed by Biglieri et al. for QPSK, due to its superior coding gain while our rate-1.5 STBC outperforms the full-diversity quasi-orthogonal STBC (QOSTBC). Then, two STBCs with code rates of 2 and 1.5 are proposed for three transmit antennas which are shown to outperform the corresponding full-diversity QOSTBC for three transmit antennas. We prove by an information-theoretic analysis that the capacities of new rate-2 STBCs for three and four transmit antennas are much closer to the actual MIMO channel capacity than the capacities of classical OSTBCs and CIODs.
A Large-Scale Exploration of Effective Global Features for a Joint Entity Detection and Tracking Model
Venue: arXiv cs.CL 2009
Year: 2009

Entity detection and tracking (EDT) is the task of identifying textual mentions of real-world entities in documents, extending the named entity detection and coreference resolution task by considering mentions other than names (pronouns, definite descriptions, etc.). Like NE tagging and coreference resolution, most solutions to the EDT task separate out the mention detection aspect from the coreference aspect. By doing so, these solutions are limited to using only local features for learning. In contrast, by modeling both aspects of the EDT task simultaneously, we are able to learn using highly complex, non-local features. We develop a new joint EDT model and explore the utility of many features, demonstrating their effectiveness on this task.
Breaking a new substitution-diffusion based image cipher using chaotic standard and logistic maps
Venue: arXiv cs.CR 2009
Year: 2009

Recently, an image encryption scheme based on chaotic standard and logistic maps was proposed. This paper studies the security of the scheme and shows that it can be broken with only one chosen-plaintext. Some other security defects of the scheme are also reported.
The threshold for random (1,2)-QSAT
Venue: arXiv cs.DM 2009
Year: 2009

The QSAT problem is the quantified version of the SAT problem. We show the existence of a threshold effect for the phase transition associated with the satisfiability of random quantified extended 2-CNF formulas. We consider boolean CNF formulas of the form $\forall X \exists Y φ(X,Y)$, where $X$ has $m$ variables, $Y$ has $n$ variables and each clause in $φ$ has one literal from $X$ and two from $Y$. For such formulas, we show that the threshold phenomenon is controlled by the ratio between the number of clauses and the number $n$ of existential variables. Then we give the exact location of the associated critical ratio $c^{*}$. Indeed, we prove that $c^{*}$ is a decreasing function of $ α$, where $α$ is the limiting value of $m / \log (n)$ when $n$ tends to infinity.
Design of an Optimal Bayesian Incentive Compatible Broadcast Protocol for Ad hoc Networks with Rational Nodes
Venue: arXiv cs.GT 2009
Year: 2009

Nodes in an ad hoc wireless network incur certain costs for forwarding packets since packet forwarding consumes the resources of the nodes. If the nodes are rational, free packet forwarding by the nodes cannot be taken for granted and incentive based protocols are required to stimulate cooperation among the nodes. Existing incentive based approaches are based on the VCG (Vickrey-Clarke-Groves) mechanism which leads to high levels of incentive budgets and restricted applicability to only certain topologies of networks. Moreover, the existing approaches have only focused on unicast and multicast. Motivated by this, we propose an incentive based broadcast protocol that satisfies Bayesian incentive compatibility and minimizes the incentive budgets required by the individual nodes. The proposed protocol, which we call {\em BIC-B} (Bayesian incentive compatible broadcast) protocol, also satisfies budget balance. We also derive a necessary and sufficient condition for the ex-post individual rationality of the BIC-B protocol. The {\em BIC-B} protocol exhibits superior performance in comparison to a dominant strategy incentive compatible broadcast protocol.
Quasi-Polynomial Time Approximation Schemes for Target Tracking
Venue: arXiv cs.CG 2009
Year: 2009

We consider the problem of tracking $n$ targets in the plane using $2n$ cameras. We can use two cameras to estimate the location of a target. We are then interested in forming $n$ camera pairs where each camera belongs to exactly one pair, followed by forming a matching between the targets and camera pairs so as to best estimate the locations of each of the targets. We consider a special case of this problem where each of the cameras are placed along a horizontal line $l$, and we consider two objective functions which have been shown to give good estimates of the locations of the targets when the distances between the targets and the cameras are sufficiently large. In the first objective, the value of an assignment of a camera pair to a target is the tracking angle formed by the assignment. Here, we are interested in maximizing the sum of these tracking angles. A polynomial time 2-approximation is known for this problem. We give a quasi-polynomial time algorithm that returns a solution whose value is at least a $(1-ε)$ factor of the value of an optimal solution for any $ε> 0$. In the second objective, the cost of an assignment of a camera pair to a target is the ratio of the vertical distance between the target and $l$ to the horizontal distance between the cameras in the camera pair. In this setting, we are interested in minimizing the sum of these ratios. A polynomial time 2-approximation is known for this problem. We give a quasi-polynomial time algorithm that returns a solution whose value is at most a $(1+ε)$ factor of the value of an optimal solution for any $ε> 0$.
On the Complexity of Envy-Free Cake Cutting
Venue: arXiv cs.GT 2009
Year: 2009

We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a $θ(({1\overε})^{d-1})$ time matching bound for the query complexity of $d+1$ player cake cutting with Lipschitz utilities for any $d> 1$. When the utility functions are given by a polynomial time algorithm, we prove the problem to be PPAD-complete. For measurable utility functions, we find a fully polynomial-time algorithm for finding an approximate envy-free allocation of a cake among three people using two cuts.
The SAT solving method as applied to cryptographic analysis of asymmetric ciphers
Venue: arXiv cs.CR 2009
Year: 2009

The one of the most interesting problem of discrete mathematics is the SAT (satisfiability) problem. Good way in SAT solver developing is to transform the SAT problem to the problem of continuous search of global minimums of the functional associated with the CNF. This article proves the special construction of the functional and offers to solve the system of non-linear algebraic equation that determines functional stationary points via modified method of consecutive approximation. The article describes parallel versions of the method. Also gives the schema of using the method to important problems of cryptographic analysis of asymmetric ciphers, including determining concrete bits of multipliers (in binary form) in large factorization problems and concrete bits of exponent of discrete logarithm problem.
FNT-based Reed-Solomon Erasure Codes
Venue: arXiv cs.IT 2009
Year: 2009

This paper presents a new construction of Maximum-Distance Separable (MDS) Reed-Solomon erasure codes based on Fermat Number Transform (FNT). Thanks to FNT, these codes support practical coding and decoding algorithms with complexity O(n log n), where n is the number of symbols of a codeword. An open-source implementation shows that the encoding speed can reach 150Mbps for codes of length up to several 10,000s of symbols. These codes can be used as the basic component of the Information Dispersal Algorithm (IDA) system used in a several P2P systems.
Frustratingly Easy Domain Adaptation
Venue: arXiv cs.LG 2009
Year: 2009

We describe an approach to domain adaptation that is appropriate exactly in the case when one has enough ``target'' data to do slightly better than just using only ``source'' data. Our approach is incredibly simple, easy to implement as a preprocessing step (10 lines of Perl!) and outperforms state-of-the-art approaches on a range of datasets. Moreover, it is trivially extended to a multi-domain adaptation problem, where one has data from a variety of different domains.
A new intrinsic numerical method for PDE on surfaces
Venue: arXiv cs.CG 2009
Year: 2009

In this note we shall introduce a simple, effective numerical method for solving partial differential equations for scalar and vector-valued data defined on surfaces. Even though we shall follow the traditional way to approximate the regular surfaces under consideration by triangular meshes, the key idea of our algorithm is to develop an intrinsic and unified way to compute directly the partial derivatives of functions defined on triangular meshes. We shall present examples in computer graphics and image processing applications.
Compressive Sensing for Feedback Reduction in MIMO Broadcast Channels
Venue: arXiv cs.IT 2009
Year: 2009

We propose a generalized feedback model and compressive sensing based opportunistic feedback schemes for feedback resource reduction in MIMO Broadcast Channels under the assumption that both uplink and downlink channels undergo block Rayleigh fading. Feedback resources are shared and are opportunistically accessed by users who are strong, i.e. users whose channel quality information is above a certain fixed threshold. Strong users send same feedback information on all shared channels. They are identified by the base station via compressive sensing. Both analog and digital feedbacks are considered. The proposed analog & digital opportunistic feedback schemes are shown to achieve the same sum-rate throughput as that achieved by dedicated feedback schemes, but with feedback channels growing only logarithmically with number of users. Moreover, there is also a reduction in the feedback load. In the analog feedback case, we show that the propose scheme reduces the feedback noise which eventually results in better throughput, whereas in the digital feedback case the proposed scheme in a noisy scenario achieves almost the throughput obtained in a noiseless dedicated feedback scenario. We also show that for a fixed given budget of feedback bits, there exist a trade-off between the number of shared channels and thresholds accuracy of the feedback SINR.
Foundations for a Developmental State: A case for technical education
Venue: arXiv cs.CY 2009
Year: 2009

This paper studies the viability of making a country a developmental state. In particular it studies the characteristics of a developmental state and how they are linked to technology. It then identifies technical education, as a vital force for the creation of a developmental state. In particular it identifies analytical, numeracy, computational and communication skills as vital forces for a society to create a developmental society.
Some bounds on the capacity of communicating the sum of sources
Venue: arXiv cs.IT 2009
Year: 2009

We consider directed acyclic networks with multiple sources and multiple terminals where each source generates one i.i.d. random process over an abelian group and all the terminals want to recover the sum of these random processes. The different source processes are assumed to be independent. The solvability of such networks has been considered in some previous works. In this paper we investigate on the capacity of such networks, referred as {\it sum-networks}, and present some bounds in terms of min-cut, and the numbers of sources and terminals.
Topology Discovery Using Cisco Discovery Protocol
Venue: arXiv cs.NI 2009
Year: 2009

In this paper we address the problem of discovering network topology in proprietary networks. Namely, we investigate topology discovery in Cisco-based networks. Cisco devices run Cisco Discovery Protocol (CDP) which holds information about these devices. We first compare properties of topologies that can be obtained from networks deploying CDP versus Spanning Tree Protocol (STP) and Management Information Base (MIB) Forwarding Database (FDB). Then we describe a method of discovering topology of CDP-based networks. Our experiments show that the physical topology of the network including links that are in Forwarding Block state can be discovered.
Benchmarking Declarative Approximate Selection Predicates
Venue: arXiv cs.DB 2009
Year: 2009

Declarative data quality has been an active research topic. The fundamental principle behind a declarative approach to data quality is the use of declarative statements to realize data quality primitives on top of any relational data source. A primary advantage of such an approach is the ease of use and integration with existing applications. Several similarity predicates have been proposed in the past for common quality primitives (approximate selections, joins, etc.) and have been fully expressed using declarative SQL statements. In this thesis, new similarity predicates are proposed along with their declarative realization, based on notions of probabilistic information retrieval. Then, full declarative specifications of previously proposed similarity predicates in the literature are presented, grouped into classes according to their primary characteristics. Finally, a thorough performance and accuracy study comparing a large number of similarity predicates for data cleaning operations is performed.
Permutation Arrays Under the Chebyshev Distance
Venue: arXiv cs.IT 2009
Year: 2009

An (n,d) permutation array (PA) is a set of permutations of length n with the property that the distance (under some metric) between any two permutations in the array is at least d. They became popular recently for communication over power lines. Motivated by an application to flash memories, in this paper the metric used is the Chebyshev metric. A number of different constructions are given as well as bounds on the size of such PA.
General Deviants: An Analysis of Perturbations in Compressed Sensing
Venue: arXiv cs.IT 2009
Year: 2009

We analyze the Basis Pursuit recovery of signals with general perturbations. Previous studies have only considered partially perturbed observations Ax + e. Here, x is a signal which we wish to recover, A is a full-rank matrix with more columns than rows, and e is simple additive noise. Our model also incorporates perturbations E to the matrix A which result in multiplicative noise. This completely perturbed framework extends the prior work of Candes, Romberg and Tao on stable signal recovery from incomplete and inaccurate measurements. Our results show that, under suitable conditions, the stability of the recovered signal is limited by the noise level in the observation. Moreover, this accuracy is within a constant multiple of the best-case reconstruction using the technique of least squares. In the absence of additive noise numerical simulations essentially confirm that this error is a linear function of the relative perturbation.
Duality for Min-Max Orderings and Dichotomy for Min Cost Homomorphisms
Venue: arXiv cs.DM 2009
Year: 2009

Min-Max orderings correspond to conservative lattice polymorphisms. Digraphs with Min-Max orderings have polynomial time solvable minimum cost homomorphism problems. They can also be viewed as digraph analogues of proper interval graphs and bigraphs. We give a forbidden structure characterization of digraphs with a Min-Max ordering which implies a polynomial time recognition algorithm. We also similarly characterize digraphs with an extended Min-Max ordering, and we apply this characterization to prove a conjectured form of dichotomy for minimum cost homomorphism problems.
A Metric Encoding for Bounded Model Checking (extended version)
Venue: arXiv cs.LO 2009
Year: 2009

In Bounded Model Checking both the system model and the checked property are translated into a Boolean formula to be analyzed by a SAT-solver. We introduce a new encoding technique which is particularly optimized for managing quantitative future and past metric temporal operators, typically found in properties of hard real time systems. The encoding is simple and intuitive in principle, but it is made more complex by the presence, typical of the Bounded Model Checking technique, of backward and forward loops used to represent an ultimately periodic infinite domain by a finite structure. We report and comment on the new encoding technique and on an extensive set of experiments carried out to assess its feasibility and effectiveness.