OpenRaiser/Intern-Atlas huggingface dataset:
Using Elimination Theory to construct Rigid Matrices
Venue: arXiv cs.CC 2014
Year: 2014

The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all nxn matrices over an infinite field have a rigidity of (n-r)^2. It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Omega(n). In this paper, we construct an infinite family of complex matrices with the largest possible, i.e., (n-r)^2, rigidity. The entries of an n x n matrix in this family are distinct primitive roots of unity of orders roughly exp(n^2 log n). To the best of our knowledge, this is the first family of concrete (but not entirely explicit) matrices having maximal rigidity and a succinct algebraic description. Our construction is based on elimination theory of polynomial ideals. In particular, we use results on the existence of polynomials in elimination ideals with effective degree upper bounds (effective Nullstellensatz). Using elementary algebraic geometry, we prove that the dimension of the affine variety of matrices of rigidity at most k is exactly n^2-(n-r)^2+k. Finally, we use elimination theory to examine whether the rigidity function is semi-continuous.
A New Construction for Constant Weight Codes
Venue: arXiv cs.IT 2014
Year: 2014

A new construction for constant weight codes is presented. The codes are constructed from $k$-dimensional subspaces of the vector space $\F_q^n$. These subspaces form a constant dimension code in the Grassmannian space $\cG_q(n,k)$. Some of the constructed codes are optimal constant weight codes with parameters not known before. An efficient algorithm for error-correction is given for the constructed codes. If the constant dimension code has an efficient encoding and decoding algorithms then also the constructed constant weight code has an efficient encoding and decoding algorithms.
A Computational Algorithm for Metrical Classification of Verse
Venue: arXiv cs.OH 2014
Year: 2014

The science of versification and analysis of verse in Sanskrit is governed by rules of metre or chandas. Such metre-wise classification of verses has numerous uses for scholars and researchers alike, such as in the study of poets and their style of Sanskrit poetical works. This paper presents a comprehensive computational scheme and set of algorithms to identify the metre of verses given as Sanskrit (Unicode) or English E-text (Latin Unicode). The paper also demonstrates the use of euphonic conjunction rules to correct verses in which these conjunctions, which are compulsory in verse, have erroneously not been implemented.
A Population-centric Approach to the Beauty Contest Game
Venue: arXiv cs.GT 2014
Year: 2014

An population-centric analysis for a version of the p-beauty contest game is given for the two-player, finite population, and infinite population cases. Winning strategies are characterized in terms of iterative thinking relative to the population. To win the game one needs to iterate more times than the ambient population, but not too many more times depending on the population size and the value of p.
On Recursive Edit Distance Kernels with Application to Time Series Classification
Venue: arXiv cs.LG 2014
Year: 2014

This paper proposes some extensions to the work on kernels dedicated to string or time series global alignment based on the aggregation of scores obtained by local alignments. The extensions we propose allow to construct, from classical recursive definition of elastic distances, recursive edit distance (or time-warp) kernels that are positive definite if some sufficient conditions are satisfied. The sufficient conditions we end-up with are original and weaker than those proposed in earlier works, although a recursive regularizing term is required to get the proof of the positive definiteness as a direct consequence of the Haussler's convolution theorem. The classification experiment we conducted on three classical time warp distances (two of which being metrics), using Support Vector Machine classifier, leads to conclude that, when the pairwise distance matrix obtained from the training data is \textit{far} from definiteness, the positive definite recursive elastic kernels outperform in general the distance substituting kernels for the classical elastic distances we have tested.
Diamond Dicing
Venue: arXiv cs.DB 2014
Year: 2014

In OLAP, analysts often select an interesting sample of the data. For example, an analyst might focus on products bringing revenues of at least 100 000 dollars, or on shops having sales greater than 400 000 dollars. However, current systems do not allow the application of both of these thresholds simultaneously, selecting products and shops satisfying both thresholds. For such purposes, we introduce the diamond cube operator, filling a gap among existing data warehouse operations. Because of the interaction between dimensions the computation of diamond cubes is challenging. We compare and test various algorithms on large data sets of more than 100 million facts. We find that while it is possible to implement diamonds in SQL, it is inefficient. Indeed, our custom implementation can be a hundred times faster than popular database engines (including a row-store and a column-store).
On Packing Colorings of Distance Graphs
Venue: arXiv cs.DM 2014
Year: 2014

The {\em packing chromatic number} $χ_ρ(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$. We present lower and upper bounds for $χ_ρ(G(\mathbb{Z},D))$, showing that for finite $D$, the packing chromatic number is finite. Our main result concerns distance graphs with $D=\{1,t\}$ for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for $t\geq 447$: $χ_ρ(G(\mathbb{Z},\{1,t\}))\leq 40$ if $t$ is odd and $χ_ρ(G(\mathbb{Z},\{1,t\}))\leq 81$ if $t$ is even.
On the Capacity of the Heat Channel, Waterfilling in the Time-Frequency Plane, and a C-NODE Relationship
Venue: arXiv cs.IT 2014
Year: 2014

The heat channel is defined by a linear time-varying (LTV) filter with additive white Gaussian noise (AWGN) at the filter output. The continuous-time LTV filter is related to the heat kernel of the quantum mechanical harmonic oscillator, so the name of the channel. The channel's capacity is given in closed form by means of the Lambert W function. Also a waterfilling theorem in the time-frequency plane for the capacity is derived. It relies on a specific Szego theorem for which an essentially self-contained proof is provided. Similarly, the rate distortion function for a related nonstationary source is given in closed form and a (reverse) waterfilling theorem in the time-frequency plane is derived. Finally, a second closed-form expression for the capacity of the heat channel based on the detected perturbed filter output signals is presented. In this context, a precise differential connection between channel capacity and the normalized optimal detection error (NODE) is revealed. This C-NODE relationship is compared with the well-known I-MMSE relationship connecting mutual information with the minimum mean-square error (MMSE) of estimation theory.
A PSPACE-complete Graph Nim
Venue: arXiv cs.GT 2014
Year: 2014

We build off the game, NimG to create a version named Neighboring Nim. By reducing from Geography, we show that this game is PSPACE-hard. The games created by the reduction share strong similarities with Undirected (Vertex) Geography and regular Nim, both of which are in P. We show how to construct PSPACE-complete versions with nim heaps *1 and *2. This application of graphs can be used as a form of game sum with any games, not only Nim.
Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances
Venue: arXiv cs.DS 2014
Year: 2014

We develop a technique that we call Conflict Packing in the context of kernelization, obtaining (and improving) several polynomial kernels for editing problems on dense instances. We apply this technique on several well-studied problems: Feedback Arc Set in (Bipartite) Tournaments, Dense Rooted Triplet Inconsistency and Betweenness in Tournaments. For the former, one is given a (bipartite) tournament $T = (V,A)$ and seeks a set of at most $k$ arcs whose reversal in $T$ results in an acyclic (bipartite) tournament. While a linear vertex-kernel is already known for the first problem, using the Conflict Packing allows us to find a so-called safe partition, the central tool of the kernelization algorithm in, with simpler arguments. For the case of bipartite tournaments, the same technique allows us to obtain a quadratic vertex-kernel. Again, such a kernel was already known to exist, using the concept of so-called bimodules. We believe however that providing an unifying technique to cope with such problems is interesting. Regarding Dense Rooted Triplet Inconsistency, one is given a set of vertices $V$ and a dense collection $\mathcal{R}$ of rooted binary trees over three vertices of $V$ and seeks a rooted tree over $V$ containing all but at most $k$ triplets from $\mathcal{R}$. As a main consequence of our technique, we prove that the Dense Rooted Triplet Inconsistency problem admits a linear vertex-kernel. This result improves the best known bound of $O(k^2)$ vertices for this problem. Finally, we use this technique to obtain a linear vertex-kernel for Betweenness in Tournaments, where one is given a set of vertices $V$ and a dense collection $\mathcal{R}$ of so-called betweenness triplets and seeks a linear ordering of the vertices containing all but at most $k$ triplets from $\mathcal{R}$.
Randomness and dependencies extraction via polarization, with applications to Slepian-Wolf coding and secrecy
Venue: arXiv cs.IT 2014
Year: 2014

The polarization phenomenon for a single source is extended to a framework with multiple correlated sources. It is shown in addition to extracting the randomness of the source, the polar transforms takes the original arbitrary dependencies to extremal dependencies. Polar coding schemes for the Slepian-Wolf problem and for secret key generations are then proposed based on this phenomenon. In particular, constructions of secret keys achieving the secrecy capacity and compression schemes achieving the Slepian-Wolf capacity region are obtained with a complexity of $O(n \log (n))$.
Finite state verifiers with constant randomness
Venue: arXiv cs.CC 2014
Year: 2014

We give a new characterization of $\mathsf{NL}$ as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log n)-space bounded games of incomplete information where the universal player is allowed a constant number of moves equals NL.
A Note on the Compaction of long Training Sequences for Universal Classification -a Non-Probabilistic Approach
Venue: arXiv cs.IT 2014
Year: 2014

One of the central problems in the classification of individual test sequences (e.g. genetic analysis), is that of checking for the similarity of sample test sequences as compared with a set of much longer training sequences. This is done by a set of classifiers for test sequences of length N, where each of the classifiers is trained by the training sequences so as to minimize the classification error rate when fed with each of the training sequences. It should be noted that the storage of long training sequences is considered to be a serious bottleneck in the next generation sequencing for Genome analysis Some popular classification algorithms adopt a probabilistic approach, by assuming that the sequences are realizations of some variable-length Markov process or a hidden Markov process (HMM), thus enabling the imbeding of the training data onto a variable-length Suffix-tree, the size of which is usually linear in $N$, the length of the test sequence. Despite of the fact that it is not assumed here that the sequences are realizations of probabilistic processes (an assumption that does not seem to be fully justified when dealing with biological data), it is demonstrated that "feature-based" classifiers, where particular substrings (called "features" or markers) are sought in a set of "big data" training sequences may be based on a universal compaction of the training data that is contained in a set of $t$ (long) individual training sequences, onto a suffix-tree with no more than O(N) leaves, regardless of how long the training sequence is, at only a vanishing increase in the classification error rate.
Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks
Venue: arXiv cs.DC 2014
Year: 2014

Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm. The main contribution of this paper is to propose the combination of two existing tools in this direction: local computations by means of graph relabelings, and evolving graphs. Such a combination makes it possible to express fine-grained properties on the network dynamics, then examine what impact those properties have on the execution at a precise, intertwined, level. We illustrate the use of this framework through the analysis of three simple algorithms, then discuss general implications of this work, which include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) a formal hierarchy of dynamic networks based on these requirements, and (iii) the potential for mechanization induced by our framework, which we believe opens a door towards automated analysis and decision support in dynamic networks.
Computing all maps into a sphere
Venue: arXiv cs.CG 2014
Year: 2014

Given topological spaces X and Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X -> Y . We consider a computational version, where X, Y are given as finite simplicial complexes, and the goal is to compute [X,Y], i.e., all homotopy classes of such maps. We solve this problem in the stable range, where for some d >= 2, we have dim X <= 2d - 2 and Y is (d - 1)-connected; in particular, Y can be the d-dimensional sphere S^d. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S^1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A of X and a map A -> Y and ask whether it extends to a map X -> Y, or computing the Z_2-index---everything in the stable range. Outside the stable range, the extension problem is undecidable.
A further generalization of the colourful Carathéodory theorem
Venue: arXiv cs.CG 2014
Year: 2014

Given $d+1$ sets, or colours, $S_1, S_2,...,S_{d+1}$ of points in $\mathbb{R}^d$, a {\em colourful} set is a set $S\subseteq\bigcup_i S_i$ such that $|S\cap S_i|\leq 1$ for $i=1,...,d+1$. The convex hull of a colourful set $S$ is called a {\em colourful simplex}. Bárány's colourful Carathéodory theorem asserts that if the origin 0 is contained in the convex hull of $S_i$ for $i=1,...,d+1$, then there exists a colourful simplex containing 0. The sufficient condition for the existence of a colourful simplex containing 0 was generalized to 0 being contained in the convex hull of $S_i\cup S_j$ for $1\leq i< j \leq d+1$ by Arocha et al. and by Holmsen et al. We further generalize the sufficient condition and obtain new colourful Carathéodory theorems. We also give an algorithm to find a colourful simplex containing 0 under the generalized condition. In the plane an alternative, and more general, proof using graphs is given. In addition, we observe that any condition implying the existence of a colourful simplex containing 0 actually implies the existence of $\min_i|S_i|$ such simplices.
Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
Venue: arXiv cs.IT 2014
Year: 2014

Mathematical programming is a branch of applied mathematics and has recently been used to derive new decoding approaches, challenging established but often heuristic algorithms based on iterative message passing. Concepts from mathematical programming used in the context of decoding include linear, integer, and nonlinear programming, network flows, notions of duality as well as matroid and polyhedral theory. This survey article reviews and categorizes decoding methods based on mathematical programming approaches for binary linear codes over binary-input memoryless symmetric channels.
Interactive ontology debugging: two query strategies for efficient fault localization
Venue: arXiv cs.AI 2014
Year: 2014

Effective debugging of ontologies is an important prerequisite for their broad application, especially in areas that rely on everyday users to create and maintain knowledge bases, such as the Semantic Web. In such systems ontologies capture formalized vocabularies of terms shared by its users. However in many cases users have different local views of the domain, i.e. of the context in which a given term is used. Inappropriate usage of terms together with natural complications when formulating and understanding logical descriptions may result in faulty ontologies. Recent ontology debugging approaches use diagnosis methods to identify causes of the faults. In most debugging scenarios these methods return many alternative diagnoses, thus placing the burden of fault localization on the user. This paper demonstrates how the target diagnosis can be identified by performing a sequence of observations, that is, by querying an oracle about entailments of the target ontology. To identify the best query we propose two query selection strategies: a simple "split-in-half" strategy and an entropy-based strategy. The latter allows knowledge about typical user errors to be exploited to minimize the number of queries. Our evaluation showed that the entropy-based method significantly reduces the number of required queries compared to the "split-in-half" approach. We experimented with different probability distributions of user errors and different qualities of the a-priori probabilities. Our measurements demonstrated the superiority of entropy-based query selection even in cases where all fault probabilities are equal, i.e. where no information about typical user errors is available.
Enhanced public key security for the McEliece cryptosystem
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies a variant of the McEliece cryptosystem able to ensure that the code used as the public key is no longer permutation-equivalent to the secret code. This increases the security level of the public key, thus opening the way for reconsidering the adoption of classical families of codes, like Reed-Solomon codes, that have been longly excluded from the McEliece cryptosystem for security reasons. It is well known that codes of these classes are able to yield a reduction in the key size or, equivalently, an increased level of security against information set decoding; so, these are the main advantages of the proposed solution. We also describe possible vulnerabilities and attacks related to the considered system, and show what design choices are best suited to avoid them.
Inter-rater Agreement on Sentence Formality
Venue: arXiv cs.CL 2014
Year: 2014

Formality is one of the most important dimensions of writing style variation. In this study we conducted an inter-rater reliability experiment for assessing sentence formality on a five-point Likert scale, and obtained good agreement results as well as different rating distributions for different sentence categories. We also performed a difficulty analysis to identify the bottlenecks of our rating procedure. Our main objective is to design an automatic scoring mechanism for sentence-level formality, and this study is important for that purpose.
A Majorization Order on Monomials and Termination of a Successive Difference Substitution Algorithm
Venue: arXiv cs.SC 2014
Year: 2014

We introduce a majorization order on monomials. With the help of this order, we derive a necessary condition on the positive termination of a general successive difference substitution algorithm (KSDS) for an input form $f$.
Structural focalization
Venue: arXiv cs.LO 2014
Year: 2014

Focusing, introduced by Jean-Marc Andreoli in the context of classical linear logic, defines a normal form for sequent calculus derivations that cuts down on the number of possible derivations by eagerly applying invertible rules and grouping sequences of non-invertible rules. A focused sequent calculus is defined relative to some non-focused sequent calculus; focalization is the property that every non-focused derivation can be transformed into a focused derivation. In this paper, we present a focused sequent calculus for propositional intuitionistic logic and prove the focalization property relative to a standard presentation of propositional intuitionistic logic. Compared to existing approaches, the proof is quite concise, depending only on the internal soundness and completeness of the focused logic. In turn, both of these properties can be established (and mechanically verified) by structural induction in the style of Pfenning's structural cut elimination without the need for any tedious and repetitious invertibility lemmas. The proof of cut admissibility for the focused system, which establishes internal soundness, is not particularly novel. The proof of identity expansion, which establishes internal completeness, is a major contribution of this work.
A Logic for True Concurrency
Venue: arXiv cs.LO 2014
Year: 2014

We propose a logic for true concurrency whose formulae predicate about events in computations and their causal dependencies. The induced logical equivalence is hereditary history preserving bisimilarity, and fragments of the logic can be identified which correspond to other true concurrent behavioural equivalences in the literature: step, pomset and history preserving bisimilarity. Standard Hennessy-Milner logic, and thus (interleaving) bisimilarity, is also recovered as a fragment. We also propose an extension of the logic with fixpoint operators, thus allowing to describe causal and concurrency properties of infinite computations. We believe that this work contributes to a rational presentation of the true concurrent spectrum and to a deeper understanding of the relations between the involved behavioural equivalences.