OpenRaiser/Intern-Atlas huggingface dataset:
The Authorship Dilemma: Alphabetical or Contribution?
Venue: arXiv cs.GT 2016
Year: 2016

Scientific communities have adopted different conventions for ordering authors on publications. Are these choices inconsequential, or do they have significant influence on individual authors, the quality of the projects completed, and research communities at large? What are the trade-offs of using one convention over another? In order to investigate these questions, we formulate a basic two-player game theoretic model, which already illustrates interesting phenomena that can occur in more realistic settings. We find that alphabetical ordering can improve research quality, while contribution-based ordering leads to a denser collaboration network and a greater number of publications. Contrary to the assumption that free riding is a weakness of the alphabetical ordering scheme, this phenomenon can occur under any contribution scheme, and the worst case occurs under contribution-based ordering. Finally, we show how authors working on multiple projects can cooperate to attain optimal research quality and eliminate free riding given either contribution scheme.
The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages
Venue: arXiv cs.FL 2016
Year: 2016

Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices, and more. In our main result, we derive the fundamental Chomsky-Schützenberger theorem for such quantitative context-free languages, showing that each arises as the image of a Dyck language and a regular language under a suitable morphism. Moreover, we show that quantitative context-free language are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings. We also investigate when quantitative context-free languages assume only finitely many values.
Geometric Complexity Theory V: Efficient algorithms for Noether Normalization
Venue: arXiv cs.CC 2016
Year: 2016

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noether's Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, we show that: (1) The categorical quotient for any finite dimensional representation $V$ of $SL_m$, with constant $m$, is explicit in characteristic zero. (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$. (3) The categorical quotient of the space of $r$-tuples of $m \times m$ matrices by the simultaneous conjugation action of $SL_m$ is explicit in any characteristic. (4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p$ not in $[2,\ m/2]$. (5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory. The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.
LMMSE Filtering in Feedback Systems with White Random Modes: Application to Tracking in Clutter
Venue: arXiv cs.IT 2016
Year: 2016

A generalized state space representation of dynamical systems with random modes switching according to a white random process is presented. The new formulation includes a term, in the dynamics equation, that depends on the most recent linear minimum mean squared error (LMMSE) estimate of the state. This can model the behavior of a feedback control system featuring a state estimator. The measurement equation is allowed to depend on the previous LMMSE estimate of the state, which can represent the fact that measurements are obtained from a validation window centered about the predicted measurement and not from the entire surveillance region. The LMMSE filter is derived for the considered problem. The approach is demonstrated in the context of target tracking in clutter and is shown to be competitive with several popular nonlinear methods.
Honesty by Typing
Venue: arXiv cs.PL 2016
Year: 2016

We propose a type system for a calculus of contracting processes. Processes can establish sessions by stipulating contracts, and then can interact either by keeping the promises made, or not. Type safety guarantees that a typeable process is honest - that is, it abides by the contracts it has stipulated in all possible contexts, even in presence of dishonest adversaries. Type inference is decidable, and it allows to safely approximate the honesty of processes using either synchronous or asynchronous communication.
Sliding Mode Control for Torque Evolution of a Double Feed Asynchronous Generator
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes a robust control of doublefed induction generator of wind turbine to optimize its production: that means the energy quality and efficiency. The proposed control reposes in the sliding mode control using a multimodel approach which contributes on the minimization of the static error and the chattering phenomenon. This new approach is called sliding mode multimodel control (SMMC). Simulation results show good performances of this control.
STEVE - Space-Time-Enclosing Volume Extraction
Venue: arXiv cs.CG 2016
Year: 2016

The novel STEVE (i.e., Space-Time-Enclosing Volume Extraction) algorithm is described here for the very first time. It generates iso-valued hypersurfaces that may be implicitly contained in four-dimensional (4D) data sets, such as temporal sequences of three-dimensional images from time-varying computed tomography. Any final hypersurface that will be generated by STEVE is guaranteed to be free from accidental rifts, i.e., it always fully encloses a region in the 4D space under consideration. Furthermore, the information of the interior/exterior of the enclosed regions is propagated to each one of the tetrahedrons, which are embedded into 4D and which in their union represent the final, iso-valued hypersurface(s). STEVE is usually executed in a purely data-driven mode, and it uses lesser computational resources than other techniques that also generate simplex-based manifolds of codimension 1.
SYNTAGMA. A Linguistic Approach to Parsing
Venue: arXiv cs.CL 2016
Year: 2016

SYNTAGMA is a rule-based parsing system, structured on two levels: a general parsing engine and a language specific grammar. The parsing engine is a language independent program, while grammar and language specific rules and resources are given as text files, consisting in a list of constituent structuresand a lexical database with word sense related features and constraints. Since its theoretical background is principally Tesniere's Elements de syntaxe, SYNTAGMA's grammar emphasizes the role of argument structure (valency) in constraint satisfaction, and allows also horizontal bounds, for instance treating coordination. Notions such as Pro, traces, empty categories are derived from Generative Grammar and some solutions are close to Government&Binding Theory, although they are the result of an autonomous research. These properties allow SYNTAGMA to manage complex syntactic configurations and well known weak points in parsing engineering. An important resource is the semantic network, which is used in disambiguation tasks. Parsing process follows a bottom-up, rule driven strategy. Its behavior can be controlled and fine-tuned.
Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
Venue: arXiv cs.IT 2016
Year: 2016

We derive fundamental sample complexity bounds for recovering sparse and structured signals for linear and nonlinear observation models including sparse regression, group testing, multivariate regression and problems with missing features. In general, sparse signal processing problems can be characterized in terms of the following Markovian property. We are given a set of $N$ variables $X_1,X_2,\ldots,X_N$, and there is an unknown subset of variables $S \subset \{1,\ldots,N\}$ that are relevant for predicting outcomes $Y$. More specifically, when $Y$ is conditioned on $\{X_n\}_{n\in S}$ it is conditionally independent of the other variables, $\{X_n\}_{n \not \in S}$. Our goal is to identify the set $S$ from samples of the variables $X$ and the associated outcomes $Y$. We characterize this problem as a version of the noisy channel coding problem. Using asymptotic information theoretic analyses, we establish mutual information formulas that provide sufficient and necessary conditions on the number of samples required to successfully recover the salient variables. These mutual information expressions unify conditions for both linear and nonlinear observations. We then compute sample complexity bounds for the aforementioned models, based on the mutual information expressions in order to demonstrate the applicability and flexibility of our results in general sparse signal processing models.
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

We give two algorithms computing representative families of linear and uniform matroids and demonstrate how to use representative families for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include - LONGEST DIRECTED CYCLE - MINIMUM EQUIVALENT GRAPH (MEG) - Algorithms on graphs of bounded treewidth -k-PATH, k-TREE, and more generally, k-SUBGRAPH ISOMORPHISM, where the k-vertex pattern graph is of constant treewidth.
Online Leader Selection for Improved Collective Tracking and Formation Maintenance
Venue: arXiv cs.SY 2016
Year: 2016

The goal of this work is to propose an extension of the popular leader-follower framework for multi-agent collective tracking and formation maintenance in presence of a time- varying leader. In particular, the leader is persistently selected online so as to optimize the tracking performance of an exogenous collective velocity command while also maintaining a desired formation via a (possibly time-varying) communication-graph topology. The effects of a change in the leader identity are theoretically analyzed and exploited for defining a suitable error metric able to capture the tracking performance of the multi- agent group. Both the group performance and the metric design are found to depend upon the spectral properties of a special directed graph induced by the identity of the chosen leader. By exploiting these results, as well as distributed estimation techniques, we are then able to detail a fully-decentralized adaptive strategy able to periodically select online the best leader among the neighbors of the current leader. Numerical simulations show that the application of the proposed technique results in an improvement of the overall performance of the group behavior w.r.t. other possible strategies.
Theoretical Bounds in Minimax Decentralized Hypothesis Testing
Venue: arXiv cs.IT 2016
Year: 2016

Minimax decentralized detection is studied under two scenarios: with and without a fusion center when the source of uncertainty is the Bayesian prior. When there is no fusion center, the constraints in the network design are determined. Both for a single decision maker and multiple decision makers, the maximum loss in detection performance due to minimax decision making is obtained. In the presence of a fusion center, the maximum loss of detection performance between with- and without fusion center networks is derived assuming that both networks are minimax robust. The results are finally generalized.
Joint Optimization of Radio Resources and Code Partitioning in Mobile Edge Computing
Venue: arXiv cs.NI 2016
Year: 2016

The aim of this paper is to propose a computation offloading strategy for mobile edge computing. We exploit the concept of call graph, which models a generic computer program as a set of procedures related to each other through a weighted directed graph. Our goal is to derive the optimal partition of the call graph establishing which procedures are to be executed locally or remotely. The main novelty of our work is that the optimal partition is obtained jointly with the selection of radio parameters, e.g., transmit power and constellation size, in order to minimize the energy consumption at the mobile handset, under a latency constraint taking into account transmit time and execution time. We consider both single and multi-channel transmission strategies and we prove that a globally optimal solution can be achieved in both cases. Finally, we propose a suboptimal strategy aimed at solving a relaxed version of the original problem in order to tradeoff complexity and performance of the proposed framework. Finally, several numerical results illustrate under what conditions in terms of call graph topology, communication strategy, and computation parameters, the proposed offloading strategy provides large performance gains.
The Complexity of Reachability Problems for Flat Counter Machines with Periodic Loops
Venue: arXiv cs.CC 2016
Year: 2016

This paper proves the NP-completeness of the reachability problem for the class of flat counter machines with difference bounds and, more generally, octagonal relations, labeling the transitions on the loops. The proof is based on the fact that the sequence of powers $\{R^i\}_{i=1}^\infty$ of such relations can be encoded as a periodic sequence of matrices, and that both the prefix and the period of this sequence are $2^{\mathcal{O}(\bin{R})}$ in the size of the binary encoding $\bin{R}$ of a relation $R$. This result allows to characterize the complexity of the reachability problem for one of the most studied class of counter machines \cite{cav10,comon-jurski98}, and has a potential impact for other problems in program verification.
Wind Speed Data Analysis for Various Seasons during a Decade by Wavelet and S transform
Venue: arXiv cs.CE 2016
Year: 2016

The appropriate weather prediction is a challenging task and it can be feasible with proper wind speed fluctuation analysis. In this current paper daubechies-4 wavelet is used to analyze the winter wind speed fluctuations due to lesser agitated wind data samples of winter. In summer abrupt changes in wind speed occurs which creates difficulty for wavelets to keep proper track of wind speed fluctuations. So, in that case the concept of the S-transform is introduced.
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we study the Steiner tree problem over a dynamic set of terminals. We consider the model where we are given an $n$-vertex graph $G=(V,E,w)$ with positive real edge weights, and our goal is to maintain a tree which is a good approximation of the minimum Steiner tree spanning a terminal set $S \subseteq V$, which changes over time. The changes applied to the terminal set are either terminal additions (incremental scenario), terminal removals (decremental scenario), or both (fully dynamic scenario). Our task here is twofold. We want to support updates in sublinear $o(n)$ time, and keep the approximation factor of the algorithm as small as possible. We show that we can maintain a $(6+\varepsilon)$-approximate Steiner tree of a general graph in $\tilde{O}(\sqrt{n} \log D)$ time per terminal addition or removal. Here, $D$ denotes the stretch of the metric induced by $G$. For planar graphs we achieve the same running time and the approximation ratio of $(2+\varepsilon)$. Moreover, we show faster algorithms for incremental and decremental scenarios. Finally, we show that if we allow higher approximation ratio, even more efficient algorithms are possible. In particular we show a polylogarithmic time $(4+\varepsilon)$-approximate algorithm for planar graphs. One of the main building blocks of our algorithms are dynamic distance oracles for vertex-labeled graphs, which are of independent interest. We also improve and use the online algorithms for the Steiner tree problem.
Decentralized Charging of Plug-In Electric Vehicles with Distribution Feeder Overload Control
Venue: arXiv cs.SY 2016
Year: 2016

As the number of charging Plug-in Electric Vehicles (PEVs) increase, due to the limited power capacity of the distribution feeders and the sensitivity of the mid-way distribution transformers to the excessive load, it is crucial to control the amount of power through each specific distribution feeder to avoid system overloads that may lead to breakdowns. In this paper we develop, analyze and evaluate charging algorithms for PEVs with feeder overload constraints in the distribution grid. The algorithms we propose jointly minimize the variance of the aggregate load and prevent overloading of the distribution feeders.
The multi-vehicle covering tour problem: building routes for urban patrolling
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we study a particular aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community perceived safety, allowing quick emergency responses and providing surveillance of selected sites (e.g., hospitals, schools). The planning is restricted to the availability of vehicles and strives to achieve balanced routes. We study an adaptation of the model for the multi-vehicle covering tour problem, in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. It constitutes an NP-complete integer programming problem. Suboptimal solutions are obtained with several heuristics, some adapted from the literature and others developed by us. We solve some adapted instances from TSPLIB and an instance with real data, the former being compared with results from literature, and latter being compared with empirical data.
Quasi-decidability of a Fragment of the First-order Theory of Real Numbers
Venue: arXiv cs.CC 2016
Year: 2016

In this paper we consider a fragment of the first-order theory of the real numbers that includes systems of equations of continuous functions in bounded domains, and for which all functions are computable in the sense that it is possible to compute arbitrarily close piece-wise interval approximations. Even though this fragment is undecidable, we prove that there is a (possibly non-terminating) algorithm for checking satisfiability such that (1) whenever it terminates, it computes a correct answer, and (2) it always terminates when the input is robust. A formula is robust, if its satisfiability does not change under small perturbations. As a basic tool for our algorithm we use the notion of degree from the field of (differential) topology.
Online Algorithms for Factorization-Based Structure from Motion
Venue: arXiv cs.CV 2016
Year: 2016

We present a family of online algorithms for real-time factorization-based structure from motion, leveraging a relationship between incremental singular value decomposition and recently proposed methods for online matrix completion. Our methods are orders of magnitude faster than previous state of the art, can handle missing data and a variable number of feature points, and are robust to noise and sparse outliers. We demonstrate our methods on both real and synthetic sequences and show that they perform well in both online and batch settings. We also provide an implementation which is able to produce 3D models in real time using a laptop with a webcam.
Clustering on Multiple Incomplete Datasets via Collective Kernel Learning
Venue: arXiv cs.LG 2016
Year: 2016

Multiple datasets containing different types of features may be available for a given task. For instance, users' profiles can be used to group users for recommendation systems. In addition, a model can also use users' historical behaviors and credit history to group users. Each dataset contains different information and suffices for learning. A number of clustering algorithms on multiple datasets were proposed during the past few years. These algorithms assume that at least one dataset is complete. So far as we know, all the previous methods will not be applicable if there is no complete dataset available. However, in reality, there are many situations where no dataset is complete. As in building a recommendation system, some new users may not have a profile or historical behaviors, while some may not have a credit history. Hence, no available dataset is complete. In order to solve this problem, we propose an approach called Collective Kernel Learning to infer hidden sample similarity from multiple incomplete datasets. The idea is to collectively completes the kernel matrices of incomplete datasets by optimizing the alignment of the shared instances of the datasets. Furthermore, a clustering algorithm is proposed based on the kernel matrix. The experiments on both synthetic and real datasets demonstrate the effectiveness of the proposed approach. The proposed clustering algorithm outperforms the comparison algorithms by as much as two times in normalized mutual information.
An Efficient Feedback Coding Scheme with Low Error Probability for Discrete Memoryless Channels
Venue: arXiv cs.IT 2016
Year: 2016

Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk--Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has $O(n\log n)$ coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding/decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching.
The Log-Volume of Optimal Codes for Memoryless Channels, Asymptotically Within A Few Nats
Venue: arXiv cs.IT 2016
Year: 2016

Shannon's analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume $M_\avg^*(n,ε)$ of length-$n$ codes subject to an average decoding error probability $ε$ is shown to satisfy the following tight asymptotic lower and upper bounds as $n \to \infty$: \[ \underline{A}_ε+ o(1) \le \log M_\avg^*(n,ε) - [nC - \sqrt{nV_ε} \,Q^{-1}(ε) + \frac{1}{2} \log n] \le \overline{A}_ε+ o(1) \] where $C$ is the Shannon capacity, $V_ε$ the $ε$-channel dispersion, or second-order coding rate, $Q$ the tail probability of the normal distribution, and the constants $\underline{A}_ε$ and $\overline{A}_ε$ are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap $\overline{A}_ε- \underline{A}_ε$ is one nat for weakly symmetric channels in the Cover-Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the $Z$ channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacity-achieving input distribution modified by an $O(1/\sqrt{n})$ correction term.