OpenRaiser/Intern-Atlas huggingface dataset:
On the hardness of learning sparse parities
Venue: arXiv cs.CC 2015
Year: 2015

This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equations over F_2 on n variables, decide if there exists a nonzero solution of Hamming weight at most k (i.e. a k-sparse solution). While there is a simple O(n^{k/2})-time algorithm for it, establishing fixed parameter intractability for k-EvenSet has been a notorious open problem. Towards this goal, we show that unless k-Clique can be solved in n^{o(k)} time, k-EvenSet has no poly(n)2^{o(sqrt{k})} time algorithm and no polynomial time algorithm when k = (log n)^{2+eta} for any eta > 0. Our work also shows that the non-homogeneous generalization of the problem -- which we call k-VectorSum -- is W[1]-hard on instances where the number of equations is O(k log n), improving on previous reductions which produced Omega(n) equations. We also show that for any constant eps > 0, given a system of O(exp(O(k))log n) linear equations, it is W[1]-hard to decide if there is a k-sparse linear form satisfying all the equations or if every function on at most k-variables (k-junta) satisfies at most (1/2 + eps)-fraction of the equations. In the setting of computational learning, this shows hardness of approximate non-proper learning of k-parities. In a similar vein, we use the hardness of k-EvenSet to show that that for any constant d, unless k-Clique can be solved in n^{o(k)} time there is no poly(m, n)2^{o(sqrt{k}) time algorithm to decide whether a given set of m points in F_2^n satisfies: (i) there exists a non-trivial k-sparse homogeneous linear form evaluating to 0 on all the points, or (ii) any non-trivial degree d polynomial P supported on at most k variables evaluates to zero on approx. Pr_{F_2^n}[P(z) = 0] fraction of the points i.e., P is fooled by the set of points.
Engineering Oracles for Time-Dependent Road Networks
Venue: arXiv cs.DS 2015
Year: 2015

We implement and experimentally evaluate landmark-based oracles for min-cost paths in large-scale time-dependent road networks. We exploit parallelism and lossless compression, combined with a novel travel-time approximation technique, to severely reduce preprocessing space and time. We significantly improve the FLAT oracle, improving the previous query time by $30\%$ and doubling the Dijkstra-rank speedup. We also implement and experimentally evaluate a novel oracle (HORN), based on a landmark hierarchy, achieving even better performance wrt to FLAT.
Nez: practical open grammar language
Venue: arXiv cs.PL 2015
Year: 2015

Nez is a PEG(Parsing Expressing Grammar)-based open grammar language that allows us to describe complex syntax constructs without action code. Since open grammars are declarative and free from a host programming language of parsers, software engineering tools and other parser applications can reuse once-defined grammars across programming languages. A key challenge to achieve practical open grammars is the expressiveness of syntax constructs and the resulting parser performance, as the traditional action code approach has provided very pragmatic solutions to these two issues. In Nez, we extend the symbol-based state management to recognize context-sensitive language syntax, which often appears in major programming languages. In addition, the Abstract Syntax Tree constructor allows us to make flexible tree structures, including the left-associative pair of trees. Due to these extensions, we have demonstrated that Nez can parse not all but many grammars. Nez can generate various types of parsers since all Nez operations are independent of a specific parser language. To highlight this feature, we have implemented Nez with dynamic parsing, which allows users to integrate a Nez parser as a parser library that loads a grammar at runtime. To achieve its practical performance, Nez operators are assembled into low-level virtual machine instructions, including automated state modifications when backtracking, transactional controls of AST construction, and efficient memoization in packrat parsing. We demonstrate that Nez dynamic parsers achieve very competitive performance compared to existing efficient parser generators.
Modeling of anechoich chambers with equivalent materials and equivalent sources
Venue: arXiv cs.CE 2015
Year: 2015

Numerical simulation of anechoic chambers is a hot topic since it can provide useful data about the performance of the EMC site. However, the mathematical nature of the problem, the physical dimensions of the simulated sites and the frequency ranges pose nontrivial challenges to the simulation. Computational requirements in particular will quickly become unmanageable if adequate techniques are not employed. In this work we describe a novel approach, based on equivalent elements, that enables the simulation of large chambers with modest computational resources. The method is then validated against real measurement results.
A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs
Venue: arXiv cs.AI 2015
Year: 2015

POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.
On Characterization of Feasible Interference Regions in Cognitive Radio Networks
Venue: arXiv cs.NI 2015
Year: 2015

In the state-of-the-art interference management schemes for underlay CRNs, it is considered that all PUs are protected if the cognitive interference for each primary receiving-point is lower than a maximum threshold, the so called interference temperature limit (ITL) for the corresponding receiving-point. This is assumed to be fixed and independent of ITL values for other primary receiving-points, which corresponds to a box-like FCIR. In this paper, we characterize the FCIR for {\em uplink} transmissions in cellular CRNs and for direct transmissions in ad-hoc CRNs. We show that the FCIR is in fact a polyhedron (i.e., the maximum feasible cognitive interference threshold for each primary receiving-point is not a constant, and it depends on that for the other primary receiving-points). Therefore, in practical interference management algorithms, it is not proper to consider a constant and independent ITL value for each of the primary receiving-points. This finding would significantly affect the design of practical interference management schemes for CRNs. To demonstrate this, based on the characterized FCIR, we propose two power control algorithms to find the maximum number of admitted SUs and the maximum aggregate throughput of the SUs in infeasible and feasible CRNs, respectively. For two distinct objectives, our proposed interference management schemes outperform the existing ones.
Spatially Distributed Sampling and Reconstruction
Venue: arXiv cs.IT 2015
Year: 2015

A spatially distributed system contains a large amount of agents with limited sensing, data processing, and communication capabilities. Recent technological advances have opened up possibilities to deploy spatially distributed systems for signal sampling and reconstruction. In this paper, we introduce a graph structure for a distributed sampling and reconstruction system by coupling agents in a spatially distributed system with innovative positions of signals. A fundamental problem in sampling theory is the robustness of signal reconstruction in the presence of sampling noises. For a distributed sampling and reconstruction system, the robustness could be reduced to the stability of its sensing matrix. In a traditional centralized sampling and reconstruction system, the stability of the sensing matrix could be verified by its central processor, but the above procedure is infeasible in a distributed sampling and reconstruction system as it is decentralized. In this paper, we split a distributed sampling and reconstruction system into a family of overlapping smaller subsystems, and we show that the stability of the sensing matrix holds if and only if its quasi-restrictions to those subsystems have uniform stability. This new stability criterion could be pivotal for the design of a robust distributed sampling and reconstruction system against supplement, replacement and impairment of agents, as we only need to check the uniform stability of affected subsystems. In this paper, we also propose an exponentially convergent distributed algorithm for signal reconstruction, that provides a suboptimal approximation to the original signal in the presence of bounded sampling noises.
On Visibility Representations of Non-planar Graphs
Venue: arXiv cs.CG 2015
Year: 2015

A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
Agri-Info: Cloud Based Autonomic System for Delivering Agriculture as a Service
Venue: arXiv cs.DC 2015
Year: 2015

Cloud computing has emerged as an important paradigm for managing and delivering services efficiently over the Internet. Convergence of cloud computing with technologies such as wireless sensor networking and mobile computing offers new applications of cloud services but this requires management of Quality of Service (QoS) parameters to efficiently monitor and measure the delivered services. This paper presents a QoS-aware Cloud Based Autonomic Information System for delivering agriculture related information as a service through the use of latest Cloud technologies which manage various types of agriculture related data based on different domains. Proposed system gathers information from various users through preconfigured devices and manages and provides required information to users automatically. Further, Cuckoo Optimization Algorithm has been used for efficient resource allocation at infrastructure level for effective utilization of resources. We have evaluated the performance of the proposed approach in Cloud environment and experimental results show that the proposed system performs better in terms of resource utilization, execution time, cost and computing capacity along with other QoS parameters.
Quantifier Alternation for Infinite Words
Venue: arXiv cs.FL 2015
Year: 2015

We investigate the expressive power of quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes $Σ_i$ (sentences having at most $i$ blocks of quantifiers starting with an $\exists$) and $\mathcal{B}Σ_i$ (Boolean combinations of $Σ_i$ sentences). So far, this expressive power has been effectively characterized for the lower levels only. Recently, a breakthrough was made over finite words, and decidable characterizations were obtained for $\mathcal{B}Σ_2$ and $Σ_3$, by relying on a decision problem called separation, and solving it for $Σ_2$. The contribution of this paper is a generalization of these results to the setting of infinite words: we solve separation for $Σ_2$ and $Σ_3$, and obtain decidable characterizations of $\mathcal{B}Σ_2$ and $Σ_3$ as consequences.
On-line Recognition of Handwritten Mathematical Symbols
Venue: arXiv cs.CV 2015
Year: 2015

Finding the name of an unknown symbol is often hard, but writing the symbol is easy. This bachelor's thesis presents multiple systems that use the pen trajectory to classify handwritten symbols. Five preprocessing steps, one data augmentation algorithm, five features and five variants for multilayer Perceptron training were evaluated using 166898 recordings which were collected with two crowdsourcing projects. The evaluation results of these 21 experiments were used to create an optimized recognizer which has a TOP1 error of less than 17.5% and a TOP3 error of 4.0%. This is an improvement of 18.5% for the TOP1 error and 29.7% for the TOP3 error.
Development of a Large-scale Neuroimages and Clinical Variables Data Atlas in the neuGRID4You (N4U) project
Venue: arXiv cs.DB 2015
Year: 2015

Exceptional growth in the availability of large-scale clinical imaging datasets has led to the development of computational infrastructures offering scientists access to image repositories and associated clinical variables data. The EU FP7 neuGRID and its follow on neuGRID4You (N4U) project is a leading e-Infrastructure where neuroscientists can find core services and resources for brain image analysis. The core component of this e-Infrastructure is the N4U Virtual Laboratory, which offers an easy access for neuroscientists to a wide range of datasets and algorithms, pipelines, computational resources, services, and associated support services. The foundation of this virtual laboratory is a massive data store plus information services called the Data Atlas that stores datasets, clinical study data, data dictionaries, algorithm/pipeline definitions, and provides interfaces for parameterised querying so that neuroscientists can perform analyses on required datasets. This paper presents the overall design and development of the Data Atlas, its associated datasets and indexing and a set of retrieval services that originated from the development of the N4U Virtual Laboratory in the EU FP7 N4U project in the light of user requirements.
Sparse Coral Classification Using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Autonomous repair of deep-sea coral reefs is a recent proposed idea to support the oceans ecosystem in which is vital for commercial fishing, tourism and other species. This idea can be operated through using many small autonomous underwater vehicles (AUVs) and swarm intelligence techniques to locate and replace chunks of coral which have been broken off, thus enabling re-growth and maintaining the habitat. The aim of this project is developing machine vision algorithms to enable an underwater robot to locate a coral reef and a chunk of coral on the seabed and prompt the robot to pick it up. Although there is no literature on this particular problem, related work on fish counting may give some insight into the problem. The technical challenges are principally due to the potential lack of clarity of the water and platform stabilization as well as spurious artifacts (rocks, fish, and crabs). We present an efficient sparse classification for coral species using supervised deep learning method called Convolutional Neural Networks (CNNs). We compute Weber Local Descriptor (WLD), Phase Congruency (PC), and Zero Component Analysis (ZCA) Whitening to extract shape and texture feature descriptors, which are employed to be supplementary channels (feature-based maps) besides basic spatial color channels (spatial-based maps) of coral input image, we also experiment state-of-art preprocessing underwater algorithms for image enhancement and color normalization and color conversion adjustment. Our proposed coral classification method is developed under MATLAB platform, and evaluated by two different coral datasets (University of California San Diego's Moorea Labeled Corals, and Heriot-Watt University's Atlantic Deep Sea).
Individual Secrecy for the Broadcast Channel
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the problem of secure communication over broadcast channels under the individual secrecy constraints. That is, the transmitter wants to send two independent messages to two legitimate receivers in the presence of an eavesdropper, while keeping the eavesdropper ignorant of each message (i.e., the information leakage from each message to the eavesdropper is made vanishing). Building upon Carleial-Hellman's secrecy coding, Wyner's secrecy coding, the frameworks of superposition coding and Marton's coding together with techniques such as rate splitting and indirect decoding, achievable rate regions are developed. The proposed regions are compared with those satisfying joint secrecy and without secrecy constraints, and the individual secrecy capacity regions for special cases are characterized. In particular, capacity region for the deterministic case is established, and for the Gaussian model, a constant gap (i.e., 0.5 bits within the individual secrecy capacity region) result is obtained. Overall, when compared with the joint secrecy constraint, the results allow for trading-off secrecy level and throughput in the system.
Aspect-based Opinion Summarization with Convolutional Neural Networks
Venue: arXiv cs.CL 2015
Year: 2015

This paper considers Aspect-based Opinion Summarization (AOS) of reviews on particular products. To enable real applications, an AOS system needs to address two core subtasks, aspect extraction and sentiment classification. Most existing approaches to aspect extraction, which use linguistic analysis or topic modeling, are general across different products but not precise enough or suitable for particular products. Instead we take a less general but more precise scheme, directly mapping each review sentence into pre-defined aspects. To tackle aspect mapping and sentiment classification, we propose two Convolutional Neural Network (CNN) based methods, cascaded CNN and multitask CNN. Cascaded CNN contains two levels of convolutional networks. Multiple CNNs at level 1 deal with aspect mapping task, and a single CNN at level 2 deals with sentiment classification. Multitask CNN also contains multiple aspect CNNs and a sentiment CNN, but different networks share the same word embeddings. Experimental results indicate that both cascaded and multitask CNNs outperform SVM-based methods by large margins. Multitask CNN generally performs better than cascaded CNN.
Mining Essential Relationships under Multiplex Networks
Venue: arXiv cs.SI 2015
Year: 2015

In big data times, massive datasets often carry different relationships among the same group of nodes, analyzing on these heterogeneous relationships may give us a window to peek the essential relationships among nodes. In this paper, first of all we propose a new metric "similarity rate" in order to capture the changing rate of similarities between node-pairs though all networks; secondly, we try to use this new metric to uncover essential relationships between node-pairs which essential relationships are often hidden and hard to get. From experiments study of Indonesian Terrorists dataset, this new metric similarity rate function well for giving us a way to uncover essential relationships from lots of appearances.
Scaling to 1024 software processes and hardware cores of the distributed simulation of a spiking neural network including up to 20G synapses
Venue: arXiv cs.DC 2015
Year: 2015

This short report describes the scaling, up to 1024 software processes and hardware cores, of a distributed simulator of plastic spiking neural networks. A previous report demonstrated good scalability of the simulator up to 128 processes. Herein we extend the speed-up measurements and strong and weak scaling analysis of the simulator to the range between 1 and 1024 software processes and hardware cores. We simulated two-dimensional grids of cortical columns including up to ~20G synapses connecting ~11M neurons. The neural network was distributed over a set of MPI processes and the simulations were run on a server platform composed of up to 64 dual-socket nodes, each socket equipped with Intel Haswell E5-2630 v3 processors (8 cores @ 2.4 GHz clock). All nodes are interconned through an InfiniBand network. The DPSNN simulator has been developed by INFN in the framework of EURETILE and CORTICONIC European FET Project and will be used by the WaveScalEW tem in the framework of the Human Brain Project (HBP), SubProject 2 - Cognitive and Systems Neuroscience. This report lays the groundwork for a more thorough comparison with the neural simulation tool NEST.
On the Complexity of Multi-Parameterized Cluster Editing
Venue: arXiv cs.DS 2015
Year: 2015

The Cluster Editing problem seeks a transformation of a given undirected graph into a disjoint union of cliques via a minimum number of edge additions or deletions. A multi-parameterized version of the problem is studied, featuring a number of input parameters that bound the amount of both edge-additions and deletions per single vertex, as well as the size of a clique-cluster. We show that the problem remains NP-hard even when only one edge can be deleted and at most two edges can be added per vertex. However, the new formulation allows us to solve Cluster Editing (exactly) in polynomial time when the number of edge-edit operations per vertex is smaller than half the minimum cluster size. In other words, Correlation Clustering can be solved efficiently when the number of false positives/negatives per single data element is expected to be small compared to the minimum cluster size. As a byproduct, we obtain a kernelization algorithm that delivers linear-size kernels when the two edge-edit bounds are small constants.
Proof Relevant Corecursive Resolution
Venue: arXiv cs.LO 2015
Year: 2015

Resolution lies at the foundation of both logic programming and type class context reduction in functional languages. Terminating derivations by resolution have well-defined inductive meaning, whereas some non-terminating derivations can be understood coinductively. Cycle detection is a popular method to capture a small subset of such derivations. We show that in fact cycle detection is a restricted form of coinductive proof, in which the atomic formula forming the cycle plays the role of coinductive hypothesis. This paper introduces a heuristic method for obtaining richer coinductive hypotheses in the form of Horn formulas. Our approach subsumes cycle detection and gives coinductive meaning to a larger class of derivations. For this purpose we extend resolution with Horn formula resolvents and corecursive evidence generation. We illustrate our method on non-terminating type class resolution problems.