OpenRaiser/Intern-Atlas huggingface dataset:
Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack
Venue: arXiv cs.CC 2010
Year: 2010

In this paper, we study the integrality gap of the Knapsack linear program in the Sherali- Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 - ε persists up to a linear number of rounds of Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time approximation scheme [27,33]. Second, we show that the Lasserre hierarchy closes the gap quickly. Specifically, after t rounds of Lasserre, the integrality gap decreases to t/(t - 1). To the best of our knowledge, this is the first positive result that uses more than a small number of rounds in the Lasserre hierarchy. Our proof uses a decomposition theorem for the Lasserre hierarchy, which may be of independent interest.
Intrusions into Privacy in Video Chat Environments: Attacks and Countermeasures
Venue: arXiv cs.CR 2010
Year: 2010

Video chat systems such as Chatroulette have become increasingly popular as a way to meet and converse one-on-one via video and audio with other users online in an open and interactive manner. At the same time, security and privacy concerns inherent in such communication have been little explored. This paper presents one of the first investigations of the privacy threats found in such video chat systems, identifying three such threats, namely de-anonymization attacks, phishing attacks, and man-in-the-middle attacks. The paper further describes countermeasures against each of these attacks.
A note on interval edge-colorings of graphs
Venue: arXiv cs.DM 2010
Year: 2010

An edge-coloring of a graph $G$ with colors $1,2,\ldots,t$ is called an interval $t$-coloring if for each $i\in \{1,2,\ldots,t\}$ there is at least one edge of $G$ colored by $i$, and the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. In this paper we prove that if a connected graph $G$ with $n$ vertices admits an interval $t$-coloring, then $t\leq 2n-3$. We also show that if $G$ is a connected $r$-regular graph with $n$ vertices has an interval $t$-coloring and $n\geq 2r+2$, then this upper bound can be improved to $2n-5$.
An svm multiclassifier approach to land cover mapping
Venue: arXiv cs.AI 2010
Year: 2010

From the advent of the application of satellite imagery to land cover mapping, one of the growing areas of research interest has been in the area of image classification. Image classifiers are algorithms used to extract land cover information from satellite imagery. Most of the initial research has focussed on the development and application of algorithms to better existing and emerging classifiers. In this paper, a paradigm shift is proposed whereby a committee of classifiers is used to determine the final classification output. Two of the key components of an ensemble system are that there should be diversity among the classifiers and that there should be a mechanism through which the results are combined. In this paper, the members of the ensemble system include: Linear SVM, Gaussian SVM and Quadratic SVM. The final output was determined through a simple majority vote of the individual classifiers. From the results obtained it was observed that the final derived map generated by an ensemble system can potentially improve on the results derived from the individual classifiers making up the ensemble system. The ensemble system classification accuracy was, in this case, better than the linear and quadratic SVM result. It was however less than that of the RBF SVM. Areas for further research could focus on improving the diversity of the ensemble system used in this research.
Practically Stabilizing Atomic Memory
Venue: arXiv cs.DC 2010
Year: 2010

A self-stabilizing simulation of a single-writer multi-reader atomic register is presented. The simulation works in asynchronous message-passing systems, and allows processes to crash, as long as at least a majority of them remain working. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme that can accommodate arbitrary labels, i.e., including those not generated by the scheme itself.
Consistency of Feature Markov Processes
Venue: arXiv cs.LG 2010
Year: 2010

We are studying long term sequence prediction (forecasting). We approach this by investigating criteria for choosing a compact useful state representation. The state is supposed to summarize useful information from the history. We want a method that is asymptotically consistent in the sense it will provably eventually only choose between alternatives that satisfy an optimality property related to the used criterion. We extend our work to the case where there is side information that one can take advantage of and, furthermore, we briefly discuss the active setting where an agent takes actions to achieve desirable outcomes.
Comparative Studies of Programming Languages; Course Lecture Notes
Venue: arXiv cs.PL 2010
Year: 2010

Lecture notes for the Comparative Studies of Programming Languages course, COMP6411, taught at the Department of Computer Science and Software Engineering, Faculty of Engineering and Computer Science, Concordia University, Montreal, QC, Canada. These notes include a compiled book of primarily related articles from the Wikipedia, the Free Encyclopedia, as well as Comparative Programming Languages book and other resources, including our own. The original notes were compiled by Dr. Paquet.
Symmetric Submodular Function Minimization Under Hereditary Family Constraints
Venue: arXiv cs.DS 2010
Year: 2010

We present an efficient algorithm to find non-empty minimizers of a symmetric submodular function over any family of sets closed under inclusion. This for example includes families defined by a cardinality constraint, a knapsack constraint, a matroid independence constraint, or any combination of such constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular function where $n$ is the cardinality of the ground set. In contrast, the problem of minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $o(\sqrt{n/\log n})$ (Svitkina and Fleischer [2008]). The algorithm is similar to an algorithm of Nagamochi and Ibaraki [1998] to find all nontrivial inclusionwise minimal minimizers of a symmetric submodular function over a set of cardinality $n$ using $O(n^3)$ oracle calls. Their procedure in turn is based on Queyranne's algorithm [1998] to minimize a symmetric submodular
Ranking with Submodular Valuations
Venue: arXiv cs.DS 2010
Year: 2010

We study the problem of ranking with submodular valuations. An instance of this problem consists of a ground set $[m]$, and a collection of $n$ monotone submodular set functions $f^1, \ldots, f^n$, where each $f^i: 2^{[m]} \to R_+$. An additional ingredient of the input is a weight vector $w \in R_+^n$. The objective is to find a linear ordering of the ground set elements that minimizes the weighted cover time of the functions. The cover time of a function is the minimal number of elements in the prefix of the linear ordering that form a set whose corresponding function value is greater than a unit threshold value. Our main contribution is an $O(\ln(1 / ε))$-approximation algorithm for the problem, where $ε$ is the smallest non-zero marginal value that any function may gain from some element. Our algorithm orders the elements using an adaptive residual updates scheme, which may be of independent interest. We also prove that the problem is $Ω(\ln(1 / ε))$-hard to approximate, unless P = NP. This implies that the outcome of our algorithm is optimal up to constant factors.
Sampled Semantics of Timed Automata
Venue: arXiv cs.FL 2010
Year: 2010

Sampled semantics of timed automata is a finite approximation of their dense time behavior. While the former is closer to the actual software or hardware systems with a fixed granularity of time, the abstract character of the latter makes it appealing for system modeling and verification. We study one aspect of the relation between these two semantics, namely checking whether the system exhibits some qualitative (untimed) behaviors in the dense time which cannot be reproduced by any implementation with a fixed sampling rate. More formally, the \emph{sampling problem} is to decide whether there is a sampling rate such that all qualitative behaviors (the untimed language) accepted by a given timed automaton in dense time semantics can be also accepted in sampled semantics. We show that this problem is decidable.
Data processing theorems and the second law of thermodynamics
Venue: arXiv cs.IT 2010
Year: 2010

We draw relationships between the generalized data processing theorems of Zakai and Ziv (1973 and 1975) and the dynamical version of the second law of thermodynamics, a.k.a. the Boltzmann H-Theorem, which asserts that the Shannon entropy, $H(X_t)$, pertaining to a finite--state Markov process $\{X_t\}$, is monotonically non-decreasing as a function of time $t$, provided that the steady-state distribution of this process is uniform across the state space (which is the case when the process designates an isolated system). It turns out that both the generalized data processing theorems and the Boltzmann H-Theorem can be viewed as special cases of a more general principle concerning the monotonicity (in time) of a certain generalized information measure applied to a Markov process. This gives rise to a new look at the generalized data processing theorem, which suggests to exploit certain degrees of freedom that may lead to better bounds, for a given choice of the convex function that defines the generalized mutual information.
Enforcing Secure Object Initialization in Java
Venue: arXiv cs.PL 2010
Year: 2010

Sun and the CERT recommend for secure Java development to not allow partially initialized objects to be accessed. The CERT considers the severity of the risks taken by not following this recommendation as high. The solution currently used to enforce object initialization is to implement a coding pattern proposed by Sun, which is not formally checked. We propose a modular type system to formally specify the initialization policy of libraries or programs and a type checker to statically check at load time that all loaded classes respect the policy. This allows to prove the absence of bugs which have allowed some famous privilege escalations in Java. Our experimental results show that our safe default policy allows to prove 91% of classes of java.lang, java.security and javax.security safe without any annotation and by adding 57 simple annotations we proved all classes but four safe. The type system and its soundness theorem have been formalized and machine checked using Coq.
On Folding a Polygon to a Polyhedron
Venue: arXiv cs.CG 2010
Year: 2010

We show that the open problem presented in "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" [DO07] is solved by a theorem of Burago and Zalgaller [BZ96] from more than a decade earlier.
Verification of Java Bytecode using Analysis and Transformation of Logic Programs
Venue: arXiv cs.PL 2010
Year: 2010

State of the art analyzers in the Logic Programming (LP) paradigm are nowadays mature and sophisticated. They allow inferring a wide variety of global properties including termination, bounds on resource consumption, etc. The aim of this work is to automatically transfer the power of such analysis tools for LP to the analysis and verification of Java bytecode (JVML). In order to achieve our goal, we rely on well-known techniques for meta-programming and program specialization. More precisely, we propose to partially evaluate a JVML interpreter implemented in LP together with (an LP representation of) a JVML program and then analyze the residual program. Interestingly, at least for the examples we have studied, our approach produces very simple LP representations of the original JVML programs. This can be seen as a decompilation from JVML to high-level LP source. By reasoning about such residual programs, we can automatically prove in the CiaoPP system some non-trivial properties of JVML programs such as termination, run-time error freeness and infer bounds on its resource consumption. We are not aware of any other system which is able to verify such advanced properties of Java bytecode.
An Algorithmic Structuration of a Type System for an Orthogonal Object/Relational Model
Venue: arXiv cs.DB 2010
Year: 2010

Date and Darwen have proposed a theory of types, the latter forms the basis of a detailed presentation of a panoply of simple and complex types. However, this proposal has not been structured in a formal system. Specifically, Date and Darwen haven't indicated the formalism of the type system that corresponds to the type theory established. In this paper, we propose a pseudo-algorithmic and grammatical description of a system of types for Date and Darwen's model. Our type system is supposed take into account null values; for such intention, we introduce a particular type noted #, which expresses one or more occurrences of incomplete information in a database. Our algebraic grammar describes in detail the complete specification of an inheritance model and the subryping relation induced, thus the different definitions of related concepts.
A New Approach to Abstract Machines - Introduction to the Theory of Configuration Machines
Venue: arXiv cs.LO 2010
Year: 2010

An abstract machine is a theoretical model designed to perform a rigorous study of computation. Such a model usually consists of configurations, instructions, programs, inputs and outputs for the machine. In this paper we formalize these notions as a very simple algebraic system, called a configuration machine. If an abstract machine is defined as a configuration machine consisting of primitive recursive functions then the functions computed by the machine are always recursive. The theory of configuration machines provides a useful tool to study universal machines.
Multi-Source Transmission for Wireless Relay Networks with Linear Complexity
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers transmission schemes in multi-access relay networks (MARNs) where $J$ single-antenna sources send independent information to one $N$-antenna destination through one $M$-antenna relay. For complexity considerations, we propose a linear framework, where the relay linearly transforms its received signals to generate the forwarded signals without decoding and the destination uses its multi-antennas to fully decouple signals from different sources before decoding, by which the decoding complexity is linear in the number of sources. To achieve a high symbol rate, we first propose a scheme called DSTC-ICRec in which all sources' information streams are concurrently transmitted in both the source-relay link and the relay-destination link. In this scheme, distributed space-time coding (DSTC) is applied at the relay, which satisfies the linear constraint. DSTC also allows the destination to conduct the zero-forcing interference cancellation (IC) scheme originally proposed for multi-antenna systems to fully decouple signals from different sources. Our analysis shows that the symbol rate of DSTC-ICRec is $1/2$ symbols/source/channel use and the diversity gain of the scheme is upperbounded by $M-J+1$. To achieve a higher diversity gain, we propose another scheme called TDMA-ICRec in which the sources time-share the source-relay link. The relay coherently combines the signals on its antennas to maximize the signal-to-noise ratio (SNR) of each source, then concurrently forwards all sources' information. The destination performs zero-forcing IC. It is shown through both analysis and simulation that when $N \ge 2J-1$, TDMA-ICRec achieves the same maximum diversity gain as the full TDMA scheme in which the information stream from each source is assigned to an orthogonal channel in both links, but with a higher symbol rate.
Secret Key Generation for a Pairwise Independent Network Model
Venue: arXiv cs.IT 2010
Year: 2010

We consider secret key generation for a "pairwise independent network" model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight.
Single Parameter Combinatorial Auctions with Partially Public Valuations
Venue: arXiv cs.GT 2010
Year: 2010

We consider the problem of designing truthful auctions, when the bidders' valuations have a public and a private component. In particular, we consider combinatorial auctions where the valuation of an agent $i$ for a set $S$ of items can be expressed as $v_if(S)$, where $v_i$ is a private single parameter of the agent, and the function $f$ is publicly known. Our motivation behind studying this problem is two-fold: (a) Such valuation functions arise naturally in the case of ad-slots in broadcast media such as Television and Radio. For an ad shown in a set $S$ of ad-slots, $f(S)$ is, say, the number of {\em unique} viewers reached by the ad, and $v_i$ is the valuation per-unique-viewer. (b) From a theoretical point of view, this factorization of the valuation function simplifies the bidding language, and renders the combinatorial auction more amenable to better approximation factors. We present a general technique, based on maximal-in-range mechanisms, that converts any $α$-approximation non-truthful algorithm ($α\leq 1$) for this problem into $Ω(\fracα{\log{n}})$ and $Ω(α)$-approximate truthful mechanisms which run in polynomial time and quasi-polynomial time, respectively.
A Declarative Semantics for CLP with Qualification and Proximity
Venue: arXiv cs.LO 2010
Year: 2010

Uncertainty in Logic Programming has been investigated during the last decades, dealing with various extensions of the classical LP paradigm and different applications. Existing proposals rely on different approaches, such as clause annotations based on uncertain truth values, qualification values as a generalization of uncertain truth values, and unification based on proximity relations. On the other hand, the CLP scheme has established itself as a powerful extension of LP that supports efficient computation over specialized domains while keeping a clean declarative semantics. In this paper we propose a new scheme SQCLP designed as an extension of CLP that supports qualification values and proximity relations. We show that several previous proposals can be viewed as particular cases of the new scheme, obtained by partial instantiation. We present a declarative semantics for SQCLP that is based on observables, providing fixpoint and proof-theoretical characterizations of least program models as well as an implementation-independent notion of goal solutions.
Security Aware Mobile Web Service Provisioning
Venue: arXiv cs.DC 2010
Year: 2010

Mobile data services in combination with profluent web services are seemingly the path breaking domain in current information research. Effectively, these mobile web services will pave the way for exciting performance and security challenges, the core need-to-be-addressed issues. On security front, though a lot of standardized security specifications and implementations exist for web services in the wired networks, not much has been analysed and standardized in the wireless environments. This paper addresses some of the critical challenges in providing security to the mobile web service domain. We first explore mobile web services and their key security issues, with special focus on provisioning based on a mobile web service provider realized by us. Later we discuss state-of-the-art security awareness in the wired and wireless web services, and finally address the realization of security for the mobile web service provisioning with performance analysis results.
Non-Binary Polar Codes using Reed-Solomon Codes and Algebraic Geometry Codes
Venue: arXiv cs.IT 2010
Year: 2010

Polar codes, introduced by Arikan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.
Non-Deterministic Kleene Coalgebras
Venue: arXiv cs.LO 2010
Year: 2010

In this paper, we present a systematic way of deriving (1) languages of (generalised) regular expressions, and (2) sound and complete axiomatizations thereof, for a wide variety of systems. This generalizes both the results of Kleene (on regular languages and deterministic finite automata) and Milner (on regular behaviours and finite labelled transition systems), and includes many other systems such as Mealy and Moore machines.
Open Graphs and Computational Reasoning
Venue: arXiv cs.LO 2010
Year: 2010

We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end) and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information.
On the Approximability of Budget Feasible Mechanisms
Venue: arXiv cs.GT 2010
Year: 2010

Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for general submodular functions: we give a randomized mechanism with approximation ratio $7.91$ (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio $8.34$. Further we study the knapsack problem, which is special submodular function, give a $2+\sqrt{2}$ approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.