OpenRaiser/Intern-Atlas huggingface dataset:
Interpretations of Directed Information in Portfolio Theory, Data Compression, and Hypothesis Testing
Venue: arXiv cs.IT 2009
Year: 2009

We investigate the role of Massey's directed information in portfolio theory, data compression, and statistics with causality constraints. In particular, we show that directed information is an upper bound on the increment in growth rates of optimal portfolios in a stock market due to {causal} side information. This upper bound is tight for gambling in a horse race, which is an extreme case of stock markets. Directed information also characterizes the value of {causal} side information in instantaneous compression and quantifies the benefit of {causal} inference in joint compression of two stochastic processes. In hypothesis testing, directed information evaluates the best error exponent for testing whether a random process $Y$ {causally} influences another process $X$ or not. These results give a natural interpretation of directed information $I(Y^n \to X^n)$ as the amount of information that a random sequence $Y^n = (Y_1,Y_2,..., Y_n)$ {causally} provides about another random sequence $X^n = (X_1,X_2,...,X_n)$. A new measure, {\em directed lautum information}, is also introduced and interpreted in portfolio theory, data compression, and hypothesis testing.
Typage fort et typage souple des collections topologiques et des transformations
Venue: arXiv cs.PL 2009
Year: 2009

Topological collections allow to consider uniformly many data structures in programming languages and are handled by functions defined by pattern matching called transformations. We present two type systems for languages with topological collections and transformations. The first one is a strong type system à la Hindley/Milner which can be entirely typed at compile time. The second one is a mixed static and dynamic type system allowing to handle heterogeneous collections, that is collections which contain values with different types. In the two cases, automatic type inference is possible.
A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source
Venue: arXiv cs.IT 2009
Year: 2009

Suppose that, for any (k \geq 1), (ε> 0) and sufficiently large $σ$, we are given a black box that allows us to sample characters from a $k$th-order Markov source over the alphabet (\{0, ..., σ- 1\}). Even if we know the source has entropy either 0 or at least (\log (σ- k)), there is still no algorithm that, with probability bounded away from (1 / 2), guesses the entropy correctly after sampling at most ((σ- k)^{k / 2 - ε}) characters.
Believe It or Not: Adding Belief Annotations to Databases
Venue: arXiv cs.DB 2009
Year: 2009

We propose a database model that allows users to annotate data with belief statements. Our motivation comes from scientific database applications where a community of users is working together to assemble, revise, and curate a shared data repository. As the community accumulates knowledge and the database content evolves over time, it may contain conflicting information and members can disagree on the information it should store. For example, Alice may believe that a tuple should be in the database, whereas Bob disagrees. He may also insert the reason why he thinks Alice believes the tuple should be in the database, and explain what he thinks the correct tuple should be instead. We propose a formal model for Belief Databases that interprets users' annotations as belief statements. These annotations can refer both to the base data and to other annotations. We give a formal semantics based on a fragment of multi-agent epistemic logic and define a query language over belief databases. We then prove a key technical result, stating that every belief database can be encoded as a canonical Kripke structure. We use this structure to describe a relational representation of belief databases, and give an algorithm for translating queries over the belief database into standard relational queries. Finally, we report early experimental results with our prototype implementation on synthetic data.
Uniqueness theorem for analytic functions and its application in denoising problem
Venue: arXiv cs.IT 2009
Year: 2009

In various applications the problem of separation of the original signal and the noise arises. For example, in the identification problem for discrete linear and causal systems, the original signal consists of the values of transfer function at some points in the unit disk. In this paper we discuss the problem of choosing the points in the unite disk, for which it is possible to remove the additive noise with probability one. Since the transfer function is analytic in the unite disk, so this problem is related to the uniqueness theorems for analytic functions. Here we give a new uniqueness result for bounded analytic functions and show its applications in the denoising problem.
Why so? or Why no? Functional Causality for Explaining Query Answers
Venue: arXiv cs.DB 2009
Year: 2009

In this paper, we propose causality as a unified framework to explain query answers and non-answers, thus generalizing and extending several previously proposed approaches of provenance and missing query result explanations. We develop our framework starting from the well-studied definition of actual causes by Halpern and Pearl. After identifying some undesirable characteristics of the original definition, we propose functional causes as a refined definition of causality with several desirable properties. These properties allow us to apply our notion of causality in a database context and apply it uniformly to define the causes of query results and their individual contributions in several ways: (i) we can model both provenance as well as non-answers, (ii) we can define explanations as either data in the input relations or relational operations in a query plan, and (iii) we can give graded degrees of responsibility to individual causes, thus allowing us to rank causes. In particular, our approach allows us to explain contributions to relational aggregate functions and to rank causes according to their respective responsibilities. We give complexity results and describe polynomial algorithms for evaluating causality in tractable cases. Throughout the paper, we illustrate the applicability of our framework with several examples. Overall, we develop in this paper the theoretical foundations of causality theory in a database context.
A Variable Depth Sequential Search Heuristic for the Quadratic Assignment Problem
Venue: arXiv cs.DS 2009
Year: 2009

We develop a variable depth search heuristic for the quadratic assignment problem. The heuristic is based on sequential changes in assignments analogous to the Lin-Kernighan sequential edge moves for the traveling salesman problem. We treat unstructured problem instances of sizes 60 to 400. When the heuristic is used in conjunction with robust tabu search, we measure performance improvements of up to a factor of 15 compared to the use of robust tabu alone. The performance improvement increases as the problem size increases.
Teaching Physical Based Animation via OpenGL Slides
Venue: arXiv cs.GR 2009
Year: 2009

This work expands further our earlier poster presentation and integration of the OpenGL Slides Framework (OGLSF) - to make presentations with real-time animated graphics where each slide is a scene with tidgets - and physical based animation of elastic two-, three-layer softbody objects. The whole project is very interactive, and serves dual purpose - delivering the teaching material in a classroom setting with real running animated examples as well as releasing the source code to the students to show how the actual working things are made.
Oriented Straight Line Segment Algebra: Qualitative Spatial Reasoning about Oriented Objects
Venue: arXiv cs.AI 2009
Year: 2009

Nearly 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. This work received substantial interest amongst the qualitative spatial reasoning community. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations and other properties of dipole calculi. Our results are based on a condensed semantics of the dipole relations. In contrast to the points that are normally used, dipoles are extended and have an intrinsic direction. Both features are important properties of natural objects. This allows for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of the dipole calculus. We integrate our results into two reasoning tools which are publicly available.
On the structure of non-full-rank perfect codes
Venue: arXiv cs.IT 2009
Year: 2009

The Krotov combining construction of perfect 1-error-correcting binary codes from 2000 and a theorem of Heden saying that every non-full-rank perfect 1-error-correcting binary code can be constructed by this combining construction is generalized to the $q$-ary case. Simply, every non-full-rank perfect code $C$ is the union of a well-defined family of $μ$-components $K_μ$, where $μ$ belongs to an "outer" perfect code $C^*$, and these components are at distance three from each other. Components from distinct codes can thus freely be combined to obtain new perfect codes. The Phelps general product construction of perfect binary code from 1984 is generalized to obtain $μ$-components, and new lower bounds on the number of perfect 1-error-correcting $q$-ary codes are presented.
Algorithm for generating orthogonal matrices with rational elements
Venue: arXiv cs.MS 2009
Year: 2009

Special orthogonal matrices with rational elements form the group SO(n,Q), where Q is the field of rational numbers. A theorem describing the structure of an arbitrary matrix from this group is proved. This theorem yields an algorithm for generating such matrices by means of random number routines.
6-cycle double covers of cubic graphs
Venue: arXiv cs.DM 2009
Year: 2009

A cycle double cover (CDC) of an undirected graph is a collection of the graph's cycles such that every edge of the graph belongs to exactly two cycles. We describe a constructive method for generating all the cubic graphs that have a 6-CDC (a CDC in which every cycle has length 6). As an application of the method, we prove that all such graphs have a Hamiltonian cycle. A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably reduce the complexity of several distributed problems. In [9], a particular instance of sense of direction, called a chordal sense of direction (CSD), is studied and the class of k-regular graphs that admit a CSD with exactly k labels (a minimal CSD) is analyzed. We now show that nearly all the cubic graphs in this class have a 6-CDC, the only exception being K4.
Efficient Query Answering over Conceptual Schemas of Relational Databases : Technical Report
Venue: arXiv cs.DB 2009
Year: 2009

We develop a query answering system, where at the core of the work there is an idea of query answering by rewriting. For this purpose we extend the DL DL-Lite with the ability to support n-ary relations, obtaining the DL DLR-Lite, which is still polynomial in the size of the data. We devise a flexible way of mapping the conceptual level to the relational level, which provides the users an SQL-like query language over the conceptual schema. The rewriting technique adds value to conventional query answering techniques, allowing to formulate simpler queries, with the ability to infer additional information that was not stated explicitly in the user query. The formalization of the conceptual schema and the developed reasoning technique allow checking for consistency between the database and the conceptual schema, thus improving the trustiness of the information system.
Finding total unimodularity in optimization problems solved by linear programs
Venue: arXiv cs.DS 2009
Year: 2009

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with the same cost from the fractional solution. Examples are two scheduling problems and the single disk prefetching/caching problem. We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.
High Data-Rate Single-Symbol ML Decodable Distributed STBCs for Cooperative Networks
Venue: arXiv cs.IT 2009
Year: 2009

High data-rate Distributed Orthogonal Space-Time Block Codes (DOSTBCs) which achieve the single-symbol decodability and full diversity order are proposed in this paper. An upper bound of the data-rate of the DOSTBC is derived and it is approximately twice larger than that of the conventional repetition-based cooperative strategy. In order to facilitate the systematic constructions of the DOSTBCs achieving the upper bound of the data-rate, some special DOSTBCs, which have diagonal noise covariance matrices at the destination terminal, are investigated. These codes are referred to as the row-monomial DOSTBCs. An upper bound of the data-rate of the row-monomial DOSTBC is derived and it is equal to or slightly smaller than that of the DOSTBC. Lastly, the systematic construction methods of the row-monomial DOSTBCs achieving the upper bound of the data-rate are presented.
Quaternary Constant-Amplitude Codes for Multicode CDMA
Venue: arXiv cs.IT 2009
Year: 2009

A constant-amplitude code is a code that reduces the peak-to-average power ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to the favorable value 1. In this paper quaternary constant-amplitude codes (codes over Z_4) of length 2^m with error-correction capabilities are studied. These codes exist for every positive integer m, while binary constant-amplitude codes cannot exist if m is odd. Every word of such a code corresponds to a function from the binary m-tuples to Z_4 having the bent property, i.e., its Fourier transform has magnitudes 2^{m/2}. Several constructions of such functions are presented, which are exploited in connection with algebraic codes over Z_4 (in particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to construct families of quaternary constant-amplitude codes. Mappings from binary to quaternary constant-amplitude codes are presented as well.
General-Purpose Computing on a Semantic Network Substrate
Venue: arXiv cs.AI 2010
Year: 2010

This article presents a model of general-purpose computing on a semantic network substrate. The concepts presented are applicable to any semantic network representation. However, due to the standards and technological infrastructure devoted to the Semantic Web effort, this article is presented from this point of view. In the proposed model of computing, the application programming interface, the run-time program, and the state of the computing virtual machine are all represented in the Resource Description Framework (RDF). The implementation of the concepts presented provides a practical computing paradigm that leverages the highly-distributed and standardized representational-layer of the Semantic Web.
Cryptanalysis of group-based key agreement protocols using subgroup distance functions
Venue: arXiv cs.CR 2010
Year: 2010

We introduce a new approach for cryptanalysis of key agreement protocols based on noncommutative groups. This approach uses functions that estimate the distance of a group element to a given subgroup. We test it against the Shpilrain-Ushakov protocol, which is based on Thompson's group F.
Spectral Efficiency of Spectrum Pooling Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this contribution, we investigate the idea of using cognitive radio to reuse locally unused spectrum to increase the total system capacity. We consider a multiband/wideband system in which the primary and cognitive users wish to communicate to different receivers, subject to mutual interference and assume that each user knows only his channel and the unused spectrum through adequate sensing. The basic idea under the proposed scheme is based on the notion of spectrum pooling. The idea is quite simple: a cognitive radio will listen to the channel and, if sensed idle, will transmit during the voids. It turns out that, although its simplicity, the proposed scheme showed very interesting features with respect to the spectral efficiency and the maximum number of possible pairwise cognitive communications. We impose the constraint that users successively transmit over available bands through selfish water filling. For the first time, our study has quantified the asymptotic (with respect to the band) achievable gain of using spectrum pooling in terms of spectral efficiency compared to classical radio systems. We then derive the total spectral efficiency as well as the maximum number of possible pairwise communications of such a spectrum pooling system.
Efficient Batch Update of Unique Identifiers in a Distributed Hash Table for Resources in a Mobile Host
Venue: arXiv cs.NI 2010
Year: 2010

Resources in a distributed system can be identified using identifiers based on random numbers. When using a distributed hash table to resolve such identifiers to network locations, the straightforward approach is to store the network location directly in the hash table entry associated with an identifier. When a mobile host contains a large number of resources, this requires that all of the associated hash table entries must be updated when its network address changes. We propose an alternative approach where we store a host identifier in the entry associated with a resource identifier and the actual network address of the host in a separate host entry. This can drastically reduce the time required for updating the distributed hash table when a mobile host changes its network address. We also investigate under which circumstances our approach should or should not be used. We evaluate and confirm the usefulness of our approach with experiments run on top of OpenDHT.
A Dichotomy Theorem for General Minimum Cost Homomorphism Problem
Venue: arXiv cs.LG 2010
Year: 2010

In the constraint satisfaction problem ($CSP$), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem ($MinHom$), one is additionally given weights $c_{va}$ for every variable $v$ and value $a$, and the aim is to find an assignment $f$ to the variables that minimizes $\sum_{v} c_{vf(v)}$. Let $MinHom(Γ)$ denote the $MinHom$ problem parameterized by the set of predicates allowed for constraints. $MinHom(Γ)$ is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that $MinHom(Γ)$ can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of $MinHom(Γ)$ for all choices of $Γ$. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].
Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
Venue: arXiv cs.CC 2010
Year: 2010

Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency structure from independent samples from the Markov random fields. We analyze a simple algorithm for reconstructing the underlying graph defining a Markov random field on $n$ nodes and maximum degree $d$ given observations. We show that under mild non-degeneracy conditions it reconstructs the generating graph with high probability using $Θ(d ε^{-2}δ^{-4} \log n)$ samples where $ε,δ$ depend on the local interactions. For most local interaction $\eps,δ$ are of order $\exp(-O(d))$. Our results are optimal as a function of $n$ up to a multiplicative constant depending on $d$ and the strength of the local interactions. Our results seem to be the first results for general models that guarantee that {\em the} generating model is reconstructed. Furthermore, we provide explicit $O(n^{d+2} ε^{-2}δ^{-4} \log n)$ running time bound. In cases where the measure on the graph has correlation decay, the running time is $O(n^2 \log n)$ for all fixed $d$. We also discuss the effect of observing noisy samples and show that as long as the noise level is low, our algorithm is effective. On the other hand, we construct an example where large noise implies non-identifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.
On disjoint matchings in cubic graphs
Venue: arXiv cs.DM 2010
Year: 2010

For $i=2,3$ and a cubic graph $G$ let $ν_{i}(G)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that $ν_{2}(G)\geq {4/5}| V(G)| $ and $ν_{3}(G)\geq {7/6}| V(G)| $. Moreover, it turns out that $ν_{2}(G)\leq \frac{|V(G)|+2ν_{3}(G)}{4}$.
What Can We Learn Privately?
Venue: arXiv cs.LG 2010
Year: 2010

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (non-private) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private PAC learner for the class of parity functions. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms.