OpenRaiser/Intern-Atlas huggingface dataset:
A Proof of the Boyd-Carr Conjecture
Venue: arXiv cs.DS 2011
Year: 2011

Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9. In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching.
Measurement Design for Detecting Sparse Signals
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of testing for the presence (or detection) of an unknown sparse signal in additive white noise. Given a fixed measurement budget, much smaller than the dimension of the signal, we consider the general problem of designing compressive measurements to maximize the measurement signal-to-noise ratio (SNR), as increasing SNR improves the detection performance in a large class of detectors. We use a lexicographic optimization approach, where the optimal measurement design for sparsity level $k$ is sought only among the set of measurement matrices that satisfy the optimality conditions for sparsity level k-1. We consider optimizing two different SNR criteria, namely a worst-case SNR measure, over all possible realizations of a k-sparse signal, and an average SNR measure with respect to a uniform distribution on the locations of the up to k nonzero entries in the signal. We establish connections between these two criteria and certain classes of tight frames. We constrain our measurement matrices to the class of tight frames to avoid coloring the noise covariance matrix. For the worst-case problem, we show that the optimal measurement matrix is a Grassmannian line packing for most---and a uniform tight frame for all---sparse signals. For the average SNR problem, we prove that the optimal measurement matrix is a uniform tight frame with minimum sum-coherence for most---and a tight frame for all---sparse signals.
Efficient Identity Based Public Verifiable Signcryption Scheme
Venue: arXiv cs.CR 2011
Year: 2011

Signcryption is a cryptographic primitive which performs encryption and signature in a single logical step. In conventional signcryption only receiver of the signcrypted text can verify the authenticity of the origin i.e. signature of the sender on the message after decrypting the cipher text. In public verifiable signcryption scheme anyone can verify the authenticity of the origin who can access the signcrypted text i.e. signature of the sender on the cipher text. Public verifiable signcryption scheme in which the receiver can convince a third party, by providing additional information other than his private key along with the signcryption is called third party verifiable signcryption schemes. In this paper we proposed an efficient identity based public verifiable signcryption scheme with third party verification and proved its security in the random oracle model.
Benchmarking ordering techniques for nonserial dynamic programming
Venue: arXiv cs.DM 2011
Year: 2011

Five ordering algorithms for the nonserial dynamic programming algorithm for solving sparse discrete optimization problems are compared in this paper. The benchmarking reveals that the ordering of the variables has a significant impact on the run-time of these algorithms. In addition, it is shown that different orderings are most effective for different classes of problems. Finally, it is shown that, amongst the algorithms considered here, heuristics based on maximum cardinality search and minimum fill-in perform best for solving the discrete optimization problems considered in this paper.
Linear Index Coding via Semidefinite Programming
Venue: arXiv cs.DS 2011
Year: 2011

In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS, 2006). We show a polynomial time algorithm that, given an n vertex graph G with minrank k, finds a linear index code for G of length $\widetilde{O}(n^{f(k)})$, where f(k) depends only on k. For example, for k=3 we obtain f(3) ~ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan (J. ACM, 1998) for graph coloring and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank. At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovasz theta-function of a graph with minrank k. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.
Towards a Calculus of Object Programs
Venue: arXiv cs.SE 2011
Year: 2011

Verifying properties of object-oriented software requires a method for handling references in a simple and intuitive way, closely related to how O-O programmers reason about their programs. The method presented here, a Calculus of Object Programs, combines four components: compositional logic, a framework for describing program semantics and proving program properties; negative variables to address the specifics of O-O programming, in particular qualified calls; the alias calculus, which determines whether reference expressions can ever have the same value; and the calculus of object structures, a specification technique for the structures that arise during the execution of an object-oriented program. The article illustrates the Calculus by proving the standard algorithm for reversing a linked list.
Efficient Deterministic Replay Using Complete Race Detection
Venue: arXiv cs.PL 2011
Year: 2011

Data races can significantly affect the executions of multi-threaded programs. Hence, one has to recur the results of data races to deterministically replay a multi-threaded program. However, data races are concealed in enormous number of memory operations in a program. Due to the difficulty of accurately identifying data races, previous multi-threaded deterministic record/replay schemes for commodity multi-processor system give up to record data races directly. Consequently, they either record all shared memory operations, which brings remarkable slowdown to the production run, or record the synchronization only, which introduces significant efforts to replay. Inspired by the advances in data race detection, we propose an efficient software-only deterministic replay scheme for commodity multi-processor systems, which is named RacX. The key insight of RacX is as follows: although it is NP-hard to accurately identify the existence of data races between a pair of memory operations, we can find out all potential data races in a multi-threaded program, in which the false positives can be reduced to a small amount with our automatic false positive reduction techniques. As a result, RacX can efficiently monitor all potential data races to deterministically replay a multi-threaded program. To evaluate RacX, we have carried out experiments over a number of well-known multi-threaded programs from SPLASH-2 benchmark suite and large-scale commercial programs. RacX can precisely recur production runs of these programs with value determinism. Averagely, RacX causes only about 1.21%, 1.89%, 2.20%, and 8.41% slowdown to the original run during recording (for 2-, 4-, 8- and 16-thread programs, respectively). The soundness, efficiency, scalability, and portability of RacX well demonstrate its superiority.
Decidable Problems for Probabilistic Automata on Infinite Words
Venue: arXiv cs.FL 2011
Year: 2011

We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every epsilon > 0 there is a word that is accepted with probability at least 1 - epsilon. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.
Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-run Average Objectives
Venue: arXiv cs.GT 2011
Year: 2011

Turn-based stochastic games and its important subclass Markov decision processes (MDPs) provide models for systems with both probabilistic and nondeterministic behaviors. We consider turn-based stochastic games with two classical quantitative objectives: discounted-sum and long-run average objectives. The game models and the quantitative objectives are widely used in probabilistic verification, planning, optimal inventory control, network protocol and performance analysis. Games and MDPs that model realistic systems often have very large state spaces, and probabilistic abstraction techniques are necessary to handle the state-space explosion. The commonly used full-abstraction techniques do not yield space-savings for systems that have many states with similar value, but does not necessarily have similar transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions (MLA), that clusters states based on value only, disregarding differences in their transition relation was proposed for qualitative objectives (reachability and safety objectives). In this paper we extend the MLA technique to solve stochastic games with discounted-sum and long-run average objectives. We present the MLA technique based abstraction-refinement algorithm for stochastic games and MDPs with discounted-sum objectives. For long-run average objectives, our solution works for all MDPs and a sub-class of stochastic games where every state has the same value.
Surface tension of multi-phase flow with multiple junctions governed by the variational principle
Venue: arXiv cs.NA 2011
Year: 2011

We explore a computational model of an incompressible fluid with a multi-phase field in three-dimensional Euclidean space. By investigating an incompressible fluid with a two-phase field geometrically, we reformulate the expression of the surface tension for the two-phase field found by Lafaurie, Nardone, Scardovelli, Zaleski and Zanetti (J. Comp. Phys. \vol{113} \yr{1994} \pages{134-147}) as a variational problem related to an infinite dimensional Lie group, the volume-preserving diffeomorphism. The variational principle to the action integral with the surface energy reproduces their Euler equation of the two-phase field with the surface tension. Since the surface energy of multiple interfaces even with singularities is not difficult to be evaluated in general and the variational formulation works for every action integral, the new formulation enables us to extend their expression to that of a multi-phase ($N$-phase, $N\ge2$) flow and to obtain a novel Euler equation with the surface tension of the multi-phase field. The obtained Euler equation governs the equation of motion of the multi-phase field with different surface tension coefficients without any difficulties for the singularities at multiple junctions. In other words, we unify the theory of multi-phase fields which express low dimensional interface geometry and the theory of the incompressible fluid dynamics on the infinite dimensional geometry as a variational problem. We apply the equation to the contact angle problems at triple junctions. We computed the fluid dynamics for a two-phase field with a wall numerically and show the numerical computational results that for given surface tension coefficients, the contact angles are generated by the surface tension as results of balances of the kinematic energy and the surface energy.
The Chan-Vese Algorithm
Venue: arXiv cs.CV 2011
Year: 2011

Segmentation is the process of partitioning a digital image into multiple segments (sets of pixels). Such common segmentation tasks including segmenting written text or segmenting tumors from healthy brain tissue in an MRI image, etc. Chan-Vese model for active contours is a powerful and flexible method which is able to segment many types of images, including some that would be quite difficult to segment in means of "classical" segmentation - i.e., using thresholding or gradient based methods. This model is based on the Mumford-Shah functional for segmentation, and is used widely in the medical imaging field, especially for the segmentation of the brain, heart and trachea. The model is based on an energy minimization problem, which can be reformulated in the level set formulation, leading to an easier way to solve the problem. In this project, the model will be presented (there is an extension to color (vector-valued) images, but it will not be considered here), and Matlab code that implements it will be introduced.
Diverse Consequences of Algorithmic Probability
Venue: arXiv cs.IT 2011
Year: 2011

We reminisce and discuss applications of algorithmic probability to a wide range of problems in artificial intelligence, philosophy and technological society. We propose that Solomonoff has effectively axiomatized the field of artificial intelligence, therefore establishing it as a rigorous scientific discipline. We also relate to our own work in incremental machine learning and philosophy of complexity.
Optimization with Demand Oracles
Venue: arXiv cs.GT 2011
Year: 2011

We study \emph{combinatorial procurement auctions}, where a buyer with a valuation function $v$ and budget $B$ wishes to buy a set of items. Each item $i$ has a cost $c_i$ and the buyer is interested in a set $S$ that maximizes $v(S)$ subject to $Σ_{i\in S}c_i\leq B$. Special cases of combinatorial procurement auctions are classical problems from submodular optimization. In particular, when the costs are all equal (\emph{cardinality constraint}), a classic result by Nemhauser et al shows that the greedy algorithm provides an $\frac e {e-1}$ approximation. Motivated by many papers that utilize demand queries to elicit the preferences of agents in economic settings, we develop algorithms that guarantee improved approximation ratios in the presence of demand oracles. We are able to break the $\frac e {e-1}$ barrier: we present algorithms that use only polynomially many demand queries and have approximation ratios of $\frac 9 8+ε$ for the general problem and $\frac 9 8$ for maximization subject to a cardinality constraint. We also consider the more general class of subadditive valuations. We present algorithms that obtain an approximation ratio of $2+ε$ for the general problem and 2 for maximization subject to a cardinality constraint. We guarantee these approximation ratios even when the valuations are non-monotone. We show that these ratios are essentially optimal, in the sense that for any constant $ε>0$, obtaining an approximation ratio of $2-ε$ requires exponentially many demand queries.
An Introductory Review of Information Theory in the Context of Computational Neuroscience
Venue: arXiv cs.IT 2011
Year: 2011

This paper introduces several fundamental concepts in information theory from the perspective of their origins in engineering. Understanding such concepts is important in neuroscience for two reasons. Simply applying formulae from information theory without understanding the assumptions behind their definitions can lead to erroneous results and conclusions. Furthermore, this century will see a convergence of information theory and neuroscience; information theory will expand its foundations to incorporate more comprehensively biological processes thereby helping reveal how neuronal networks achieve their remarkable information processing abilities.
Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts
Venue: arXiv cs.DS 2011
Year: 2011

Length-$q$ substrings, or $q$-grams, can represent important characteristics of text data, and determining the frequencies of all $q$-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the {\em non-overlapping frequencies} of all $q$-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in $O(q^2n)$ time and $O(qn)$ space where $n$ is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for $q=2$ in $O(n^4\log n)$ time and $O(n^3)$ space.
On the mathematical synthesis of equational logics
Venue: arXiv cs.LO 2011
Year: 2011

We provide a mathematical theory and methodology for synthesising equational logics from algebraic metatheories. We illustrate our methodology by means of two applications: a rational reconstruction of Birkhoff's Equational Logic and a new equational logic for reasoning about algebraic structure with name-binding operators.
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
Venue: arXiv cs.DS 2011
Year: 2011

The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most $k$ of its vertices. In a breakthrough result Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a $\BigOh(4^kkmn)$ time algorithm for it, the first algorithm with polynomial runtime of uniform degree for every fixed $k$. It is known that this implies a polynomial-time compression algorithm that turns OCT instances into equivalent instances of size at most $\BigOh(4^k)$, a so-called kernelization. Since then the existence of a polynomial kernel for OCT, i.e., a kernelization with size bounded polynomially in $k$, has turned into one of the main open questions in the study of kernelization. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in $k$. For OCT, the matroid is built to allow us to simulate the computation of the iterative compression step of the algorithm of Reed, Smith, and Vetta, applied (for only one round) to an approximate odd cycle transversal which it is aiming to shrink to size $k$. The process is randomized with one-sided error exponentially small in $k$, where the result can contain false positives but no false negatives, and the size guarantee is cubic in the size of the approximate solution. Combined with an $\BigOh(\sqrt{\log n})$-approximation (Agarwal et al., STOC 2005), we get a reduction of the instance to size $\BigOh(k^{4.5})$, implying a randomized polynomial kernelization.
Algorithm for Optimal Mode Scheduling in Switched Systems
Venue: arXiv cs.SY 2011
Year: 2011

This paper considers the problem of computing the schedule of modes in a switched dynamical system, that minimizes a cost functional defined on the trajectory of the system's continuous state variable. A recent approach to such optimal control problems consists of algorithms that alternate between computing the optimal switching times between modes in a given sequence, and updating the mode-sequence by inserting to it a finite number of new modes. These algorithms have an inherent inefficiency due to their sparse update of the mode-sequences, while spending most of the computing times on optimizing with respect to the switching times for a given mode-sequence. This paper proposes an algorithm that operates directly in the schedule space without resorting to the timing optimization problem. It is based on the Armijo step size along certain Gateaux derivatives of the performance functional, thereby avoiding some of the computational difficulties associated with discrete scheduling parameters. Its convergence to local minima as well as its rate of convergence are proved, and a simulation example on a nonlinear system exhibits quite a fast convergence.
On the infeasibility of entanglement generation in Gaussian quantum systems via classical control
Venue: arXiv cs.SY 2011
Year: 2011

This paper uses a system theoretic approach to show that classical linear time invariant controllers cannot generate steady state entanglement in a bipartite Gaussian quantum system which is initialized in a Gaussian state. The paper also shows that the use of classical linear controllers cannot generate entanglement in a finite time from a bipartite system initialized in a separable Gaussian state. The approach reveals connections between system theoretic concepts and the well known physical principle that local operations and classical communications cannot generate entangled states starting from separable states.
Licensing the Mizar Mathematical Library
Venue: arXiv cs.DL 2011
Year: 2011

The Mizar Mathematical Library (MML) is a large corpus of formalised mathematical knowledge. It has been constructed over the course of many years by a large number of authors and maintainers. Yet the legal status of these efforts of the Mizar community has never been clarified. In 2010, after many years of loose deliberations, the community decided to investigate the issue of licensing the content of the MML, thereby clarifying and crystallizing the status of the texts, the text's authors, and the library's long-term maintainers. The community has settled on a copyright and license policy that suits the peculiar features of Mizar and its community. In this paper we discuss the copyright and license solutions. We offer our experience in the hopes that the communities of other libraries of formalised mathematical knowledge might take up the legal and scientific problems that we addressed for Mizar.
Cloud Computing Future Framework for e-management of NGO's
Venue: arXiv cs.OH 2011
Year: 2011

Cloud computing is an emerging new computing paradigm for delivering computing services. This computing approach relies on a number of existing technologies, e.g., the Internet, virtualization, grid computing, Web services, etc. Cloud Computing aims to provide scalable and inexpensive on-demand computing infrastructures with good quality of service levels. It represents a shift away from computing as a product that is purchased, to computing as a service that is delivered to consumers from the cloud. It helps an organization in saving costs and creating new business opportunities.This paper provides a framework, Education Cloud for the e- management of NGO's. The Education Cloud can transform a nonprofit, or an entire sector of nonprofits, achieves its mission and creates lasting impact in its communities. This paper also presents the case study of Kalgidhar trust, Baru Sahib, Himachal Pradesh, NGO which is using the education as the tool to solve the social issues.