OpenRaiser/Intern-Atlas huggingface dataset:
No occurrence obstructions in geometric complexity theory
Venue: arXiv cs.CC 2018
Year: 2018

The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes VP_{ws} and VNP. Mulmuley and Sohoni (SIAM J. Comput., 2001) suggested to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of GL_{n^2}(C), which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. However, we do not rule out the general approach to the permanent versus determinant problem via multiplicity obstructions as proposed by Mulmuley and Sohoni.
Deep Convolutional Neural Networks on Cartoon Functions
Venue: arXiv cs.LG 2018
Year: 2018

Wiatowski and Bölcskei, 2015, proved that deformation stability and vertical translation invariance of deep convolutional neural network-based feature extractors are guaranteed by the network structure per se rather than the specific convolution kernels and non-linearities. While the translation invariance result applies to square-integrable functions, the deformation stability bound holds for band-limited functions only. Many signals of practical relevance (such as natural images) exhibit, however, sharp and curved discontinuities and are, hence, not band-limited. The main contribution of this paper is a deformation stability result that takes these structural properties into account. Specifically, we establish deformation stability bounds for the class of cartoon functions introduced by Donoho, 2001.
Software search is not a science, even among scientists: A survey of how scientists and engineers find software
Venue: arXiv cs.CY 2018
Year: 2018

Improved software discovery is a prerequisite for greater software reuse: after all, if someone cannot find software for a particular task, they cannot reuse it. Understanding people's approaches and preferences when they look for software could help improve facilities for software discovery. We surveyed people working in several scientific and engineering fields to better understand their approaches and selection criteria. We found that even among highly-trained people, the rudimentary approaches of relying on general Web searches, the opinions of colleagues, and the literature were still the most commonly used. However, those who were involved in software development differed from nondevelopers in their use of social help sites, software project repositories, software catalogs, and organization-specific mailing lists or forums. For example, software developers in our sample were more likely to search in community sites such as Stack Overflow even when seeking ready-to-run software rather than source code, and likewise, asking colleagues was significantly more important when looking for ready-to-run software. Our survey also provides insight into the criteria that matter most to people when they are searching for ready-to-run software. Finally, our survey also identifies some factors that can prevent people from finding software.
Parameterized Complexity and Approximation Issues for the Colorful Components Problems
Venue: arXiv cs.DS 2018
Year: 2018

The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last ten years. Here we consider two variants, Minimum Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC), introduced in 2011 in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components; MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances. For MCC on trees we show that the problem is basically equivalent to Minimum Cut on Trees, thus MCC is not approximable within factor $1.36 - \varepsilon$, it is fixed-parameter tractable and it admits a poly-kernel (when the parameter is the number of colorful components). Moreover, we show that MCC, while it is polynomial time solvable on paths, it is NP-hard even for graphs with constant distance to disjoint paths number. Then we consider the parameterized complexity of MEC when parameterized by the number $k$ of edges in the transitive closure of a solution (the graph obtained by removing edges so that it is partitioned in colorful connected components). We give a fixed-parameter algorithm for MEC paramterized by $k$ and, when the input graph is a tree, we give a poly-kernel.
Robust and Globally Optimal Manhattan Frame Estimation in Near Real Time
Venue: arXiv cs.CV 2018
Year: 2018

Most man-made environments, such as urban and indoor scenes, consist of a set of parallel and orthogonal planar structures. These structures are approximated by the Manhattan world assumption, in which notion can be represented as a Manhattan frame (MF). Given a set of inputs such as surface normals or vanishing points, we pose an MF estimation problem as a consensus set maximization that maximizes the number of inliers over the rotation search space. Conventionally, this problem can be solved by a branch-and-bound framework, which mathematically guarantees global optimality. However, the computational time of the conventional branch-and-bound algorithms is rather far from real-time. In this paper, we propose a novel bound computation method on an efficient measurement domain for MF estimation, i.e., the extended Gaussian image (EGI). By relaxing the original problem, we can compute the bound with a constant complexity, while preserving global optimality. Furthermore, we quantitatively and qualitatively demonstrate the performance of the proposed method for various synthetic and real-world data. We also show the versatility of our approach through three different applications: extension to multiple MF estimation, 3D rotation based video stabilization, and vanishing point estimation (line clustering).
The Hourglass Effect in Hierarchical Dependency Networks
Venue: arXiv cs.SI 2018
Year: 2018

Many hierarchically modular systems are structured in a way that resembles an hourglass. This "hourglass effect" means that the system generates many outputs from many inputs through a relatively small number of intermediate modules that are critical for the operation of the entire system, referred to as the waist of the hourglass. We investigate the hourglass effect in general, not necessarily layered, hierarchical dependency networks. Our analysis focuses on the number of source-to-target dependency paths that traverse each vertex, and it identifies the core of a dependency network as the smallest set of vertices that collectively cover almost all dependency paths. We then examine if a given network exhibits the hourglass property or not, comparing its core size with a "flat" (i.e., non-hierarchical) network that preserves the source dependencies of each target in the original network. As a possible explanation for the hourglass effect, we propose the Reuse Preference (RP) model that captures the bias of new modules to reuse intermediate modules of similar complexity instead of connecting directly to sources or low complexity modules. We have applied the proposed framework in a diverse set of dependency networks from technological, natural and information systems, showing that all these networks exhibit the general hourglass property but to a varying degree and with different waist characteristics.
Scalable low dimensional manifold model in the reconstruction of noisy and incomplete hyperspectral images
Venue: arXiv cs.CV 2018
Year: 2018

We present a scalable low dimensional manifold model for the reconstruction of noisy and incomplete hyperspectral images. The model is based on the observation that the spatial-spectral blocks of a hyperspectral image typically lie close to a collection of low dimensional manifolds. To emphasize this, the dimension of the manifold is directly used as a regularizer in a variational functional, which is solved efficiently by alternating direction of minimization and weighted nonlocal Laplacian. Unlike general 3D images, the same similarity matrix can be shared across all spectral bands for a hyperspectral image, therefore the resulting algorithm is much more scalable than that for general 3D data. Numerical experiments on the reconstruction of hyperspectral images from sparse and noisy sampling demonstrate the superiority of our proposed algorithm in terms of both speed and accuracy.
A Study of $k$-dipath Colourings of Oriented Graphs
Venue: arXiv cs.DM 2018
Year: 2018

We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is described. Dichotomy theorems for the complexity of the problem of deciding, for fixed $k$ and $t$, whether there exists such a $t$-colouring are proved.
A Simpler Self-reduction Algorithm for Matroid Path-width
Venue: arXiv cs.DS 2018
Year: 2018

Path-width of matroids naturally generalizes the better known parameter of path-width for graphs, and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced by Geelen-Gerards-Whittle [JCTB 2006] in pure matroid theory, it was soon recognized by Kashyap [SIDMA 2008] that it is the same concept as long-studied so called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlineny [JCTB 2006] that the decision problem, whether a given matroid over a finite field has path-width at most t, is fixed-parameter tractable (FPT) in t, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given by Jeong-Kim-Oum [SODA 2016]. Here we propose a simpler "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal path-decomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most t (such as the aforementioned decision algorithm for matroid path-width).
Model Checking Flat Freeze LTL on One-Counter Automata
Venue: arXiv cs.LO 2018
Year: 2018

Freeze LTL is a temporal logic with registers that is suitable for specifying properties of data words. In this paper we study the model checking problem for Freeze LTL on one-counter automata. This problem is known to be undecidable in general and PSPACE-complete for the special case of deterministic one-counter automata. Several years ago, Demri and Sangnier investigated the model checking problem for the flat fragment of Freeze LTL on several classes of counter automata and posed the decidability of model checking flat Freeze LTL on one-counter automata as an open problem. In this paper we resolve this problem positively, utilising a known reduction to a reachability problem on one-counter automata with parameterised equality and disequality tests. Our main technical contribution is to show decidability of the latter problem by translation to Presburger arithmetic.
Hardness of approximation for H-free edge modification problems
Venue: arXiv cs.DS 2018
Year: 2018

The $H$-Free Edge Deletion problem asks, for a given graph $G$ and an integer $k$, whether it is possible to delete at most $k$ edges from $G$ to make it $H$-free, that is, not containing $H$ as an induced subgraph. The $H$-Free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs $H$, with several important exceptions occurring when the class of $H$-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to $H$-free graphs by considering their approximability. We prove that whenever $H$ is $3$-connected and has at least two non-edges, then both $H$-Free Edge Deletion and $H$-Free Edge Completion are very hard to approximate: they do not admit $\mathrm{poly}(\mathsf{OPT})$-approximation in polynomial time, unless $\mathrm{P}=\mathrm{NP}$, or even in time subexponential in $\mathsf{OPT}$, unless the Exponential Time Hypothesis fails. The assumption of the existence of two non-edges appears to be important: we show that whenever $H$ is a complete graph without one edge, then $H$-Free Edge Deletion is tightly connected to the Min Horn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond $3$-connected graphs, we consider the cases of $H$ being a path or a cycle, and we achieve an almost complete dichotomy there.
Uncertainty in Neural Network Word Embedding: Exploration of Threshold for Similarity
Venue: arXiv cs.CL 2018
Year: 2018

Word embedding, specially with its recent developments, promises a quantification of the similarity between terms. However, it is not clear to which extent this similarity value can be genuinely meaningful and useful for subsequent tasks. We explore how the similarity score obtained from the models is really indicative of term relatedness. We first observe and quantify the uncertainty factor of the word embedding models regarding to the similarity value. Based on this factor, we introduce a general threshold on various dimensions which effectively filters the highly related terms. Our evaluation on four information retrieval collections supports the effectiveness of our approach as the results of the introduced threshold are significantly better than the baseline while being equal to or statistically indistinguishable from the optimal results.
Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation
Venue: arXiv cs.AI 2018
Year: 2018

For an autonomous agent, executing a poor policy may be costly or even dangerous. For such agents, it is desirable to determine confidence interval lower bounds on the performance of any given policy without executing said policy. Current methods for exact high confidence off-policy evaluation that use importance sampling require a substantial amount of data to achieve a tight lower bound. Existing model-based methods only address the problem in discrete state spaces. Since exact bounds are intractable for many domains we trade off strict guarantees of safety for more data-efficient approximate bounds. In this context, we propose two bootstrapping off-policy evaluation methods which use learned MDP transition models in order to estimate lower confidence bounds on policy performance with limited data in both continuous and discrete state spaces. Since direct use of a model may introduce bias, we derive a theoretical upper bound on model bias for when the model transition function is estimated with i.i.d. trajectories. This bound broadens our understanding of the conditions under which model-based methods have high bias. Finally, we empirically evaluate our proposed methods and analyze the settings in which different bootstrapping off-policy confidence interval methods succeed and fail.
Efficient Analog Circuits for Boolean Satisfiability
Venue: arXiv cs.ET 2018
Year: 2018

Efficient solutions to NP-complete problems would significantly benefit both science and industry. However, such problems are intractable on digital computers based on the von Neumann architecture, thus creating the need for alternative solutions to tackle such problems. Recently, a deterministic, continuous-time dynamical system (CTDS) was proposed (Nat.Phys. {\bf 7}(12), 966 (2011)) to solve a representative NP-complete problem, Boolean Satisfiability (SAT). This solver shows polynomial analog time-complexity on even the hardest benchmark $k$-SAT ($k \geq 3$) formulas, but at an energy cost through exponentially driven auxiliary variables. This paper presents a novel analog hardware SAT solver, AC-SAT, implementing the CTDS via incorporating novel, analog circuit design ideas. AC-SAT is intended to be used as a co-processor and is programmable for handling different problem specifications. It is especially effective for solving hard $k$-SAT problem instances that are challenging for algorithms running on digital machines. Furthermore, with its modular design, AC-SAT can readily be extended to solve larger size problems, while the size of the circuit grows linearly with the product of the number of variables and number of clauses. The circuit is designed and simulated based on a 32nm CMOS technology. SPICE simulation results show speedup factors of $\sim$10$^4$ on even the hardest 3-SAT problems, when compared with a state-of-the-art SAT solver on digital computers. As an example, for hard problems with $N=50$ variables and $M=212$ clauses, solutions are found within from a few $ns$ to a few hundred $ns$.
Word sense disambiguation: a complex network approach
Venue: arXiv cs.CL 2018
Year: 2018

In recent years, concepts and methods of complex networks have been employed to tackle the word sense disambiguation (WSD) task by representing words as nodes, which are connected if they are semantically similar. Despite the increasingly number of studies carried out with such models, most of them use networks just to represent the data, while the pattern recognition performed on the attribute space is performed using traditional learning techniques. In other words, the structural relationship between words have not been explicitly used in the pattern recognition process. In addition, only a few investigations have probed the suitability of representations based on bipartite networks and graphs (bigraphs) for the problem, as many approaches consider all possible links between words. In this context, we assess the relevance of a bipartite network model representing both feature words (i.e. the words characterizing the context) and target (ambiguous) words to solve ambiguities in written texts. Here, we focus on the semantical relationships between these two type of words, disregarding the relationships between feature words. In special, the proposed method not only serves to represent texts as graphs, but also constructs a structure on which the discrimination of senses is accomplished. Our results revealed that the proposed learning algorithm in such bipartite networks provides excellent results mostly when topical features are employed to characterize the context. Surprisingly, our method even outperformed the support vector machine algorithm in particular cases, with the advantage of being robust even if a small training dataset is available. Taken together, the results obtained here show that the proposed representation/classification method might be useful to improve the semantical characterization of written texts.
Phaseless Rcovery using Gauss-Newton Method
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we develop a concrete algorithm for phase retrieval, which we refer to as Gauss-Newton algorithm. In short, this algorithm starts with a good initial estimation, which is obtained by a modified spectral method, and then update the iteration point by a Gauss-Newton iteration step. We prove that a re-sampled version of this algorithm quadratically converges to the solution for the real case with the number of random measurements being nearly minimal. Numerical experiments also show that Gauss-Newton method has better performance over the other algorithms.
Improved Lower Bounds on Mutual Information Accounting for Nonlinear Signal-Noise Interaction
Venue: arXiv cs.IT 2018
Year: 2018

In fiber-optic communications, evaluation of mutual information (MI) is still an open issue due to the unavailability of an exact and mathematically tractable channel model. Traditionally, lower bounds on MI are computed by approximating the (original) channel with an auxiliary forward channel. In this paper, lower bounds are computed using an auxiliary backward channel, which has not been previously considered in the context of fiber-optic communications. Distributions obtained through two variations of the stochastic digital backpropagation (SDBP) algorithm are used as auxiliary backward channels and these bounds are compared with bounds obtained through the conventional digital backpropagation (DBP). Through simulations, higher information rates were achieved with SDBP, {which can be explained by the ability of SDBP to account for nonlinear signal--noise interactions
Identification of block-oriented nonlinear systems starting from linear approximations: A survey
Venue: arXiv cs.SY 2018
Year: 2018

Block-oriented nonlinear models are popular in nonlinear system identification because of their advantages of being simple to understand and easy to use. Many different identification approaches were developed over the years to estimate the parameters of a wide range of block-oriented nonlinear models. One class of these approaches uses linear approximations to initialize the identification algorithm. The best linear approximation framework and the $ε$-approximation framework, or equivalent frameworks, allow the user to extract important information about the system, guide the user in selecting good candidate model structures and orders, and prove to be a good starting point for nonlinear system identification algorithms. This paper gives an overview of the different block-oriented nonlinear models that can be identified using linear approximations, and of the identification algorithms that have been developed in the past. A non-exhaustive overview of the most important other block-oriented nonlinear system identification approaches is also provided throughout this paper.
B.A.T.Mobile: Leveraging Mobility Control Knowledge for Efficient Routing in Mobile Robotic Networks
Venue: arXiv cs.NI 2018
Year: 2018

Efficient routing is one of the key challenges of wireless networking for unmanned autonomous vehicles (UAVs) due to dynamically changing channel and network topology characteristics. Various well known mobile-ad-hoc routing protocols, such as AODV, OLSR and B.A.T.M.A.N. have been proposed to allow for proactive and reactive routing decisions. In this paper, we present a novel approach which leverages application layer knowledge derived from mobility control algorithms guiding the behavior of UAVs to fulfill a dedicated task. Thereby a prediction of future trajectories of the UAVs can be integrated with the routing protocol to avoid unexpected route breaks and packet loss. The proposed extension of the B.A.T.M.A.N. routing protocol by a mobility prediction component - called B.A.T.Mobile - has shown to be very effective to realize this concept. The results of in-depth simulation studies show that the proposed protocol reaches a distinct higher availability compared to the established approaches and shows robust behavior even in challenging channel conditions.