OpenRaiser/Intern-Atlas huggingface dataset:
Fast algorithmic self-assembly of simple shapes using random agitation
Venue: arXiv cs.DS 2014
Year: 2014

We study the power of uncontrolled random molecular movement in the nubot model of self-assembly. The nubot model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on the nubot model showed how to build simple shapes such as lines and squares quickly---in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to control the movement of a large objects quickly, and only at a time and place of the programmers' choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.
Going Deeper with Convolutions
Venue: arXiv cs.CV 2014
Year: 2014

We propose a deep convolutional neural network architecture codenamed "Inception", which was responsible for setting the new state of the art for classification and detection in the ImageNet Large-Scale Visual Recognition Challenge 2014 (ILSVRC 2014). The main hallmark of this architecture is the improved utilization of the computing resources inside the network. This was achieved by a carefully crafted design that allows for increasing the depth and width of the network while keeping the computational budget constant. To optimize quality, the architectural decisions were based on the Hebbian principle and the intuition of multi-scale processing. One particular incarnation used in our submission for ILSVRC 2014 is called GoogLeNet, a 22 layers deep network, the quality of which is assessed in the context of classification and detection.
Rank Maximal Matchings -- Structure and Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

Let G = (A U P, E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem.
Exact Least Squares Algorithm for Signal Matched Multirate Whitening Filter Bank: Part I
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we define a concept of signal matched multirate whitening filter bank which provides an optimum coding gain. This is achieved by whitening the outputs, of the analysis filter bank, within as well as across the channels, by solving a constrained projection problem. We also present a fast time and order recursive least squares algorithm to obtain the vector output of the proposed analysis filter bank. The recursive algorithm, developed here, gives rise to a lattice-like structure. Since the proposed signal matched analysis filter bank coefficients are not available directly, an order recursive algorithm is also presented for estimating these from the lattice parameters. Simulation results are presented to validate the theory. It is also observed that the proposed algorithm can be used to whiten Gaussian/non-Gaussian processes with minimum as well as non-minimum phase.
Communities and Hierarchical Structures in Dynamic Social Networks: Analysis and Visualization
Venue: arXiv cs.SI 2014
Year: 2014

Detection of community structures in social networks has attracted lots of attention in the domain of sociology and behavioral sciences. Social networks also exhibit dynamic nature as these networks change continuously with the passage of time. Social networks might also present a hierarchical structure led by individuals that play important roles in a society such as Managers and Decision Makers. Detection and Visualization of these networks changing over time is a challenging problem where communities change as a function of events taking place in the society and the role people play in it. In this paper we address these issues by presenting a system to analyze dynamic social networks. The proposed system is based on dynamic graph discretization and graph clustering. The system allows detection of major structural changes taking place in social communities over time and reveals hierarchies by identifying influential people in a social networks. We use two different data sets for the empirical evaluation and observe that our system helps to discover interesting facts about the social and hierarchical structures present in these social networks.
Exact Least Squares Algorithm for Signal Matched Synthesis Filter Bank: Part II
Venue: arXiv cs.IT 2014
Year: 2014

In the companion paper, we proposed a concept of signal matched whitening filter bank and developed a time and order recursive, fast least squares algorithm for the same. Objective of part II of the paper is two fold: first is to define a concept of signal matched synthesis filter bank, hence combining definitions of part I and part II we obtain a filter bank matched to a given signal. We also develop a fast time and order recursive, least squares algorithm for obtaining the same. The synthesis filters, obtained here, reconstruct the given signal only and not every signal from the finite energy signal space (i.e. belonging to L^2(R)), as is usually done. The recursions, so obtained, result in a lattice-like structure. Since the filter parameters are not directly available, we also present an order recursive algorithm for the computation of signal matched synthesis filter bank coefficients from the lattice parameters. The second objective is to explore the possibility of using synthesis side for modeling of a given stochastic process. Simulation results have also been presented to validate the theory.
The ADMM penalized decoder for LDPC codes
Venue: arXiv cs.IT 2014
Year: 2014

Linear programming (LP) decoding for low-density parity-check (LDPC) codes proposed by Feldman et al. is shown to have theoretical guarantees in several regimes and empirically is not observed to suffer from an error floor. However at low signal-to-noise ratios (SNRs), LP decoding is observed to have worse error performance than belief propagation (BP) decoding. In this paper, we seek to improve LP decoding at low SNRs while still achieving good high SNR performance. We first present a new decoding framework obtained by trying to solve a non-convex optimization problem using the alternating direction method of multipliers (ADMM). This non-convex problem is constructed by adding a penalty term to the LP decoding objective. The goal of the penalty term is to make "pseudocodewords", which are the non-integer vertices of the LP relaxation to which the LP decoder fails, more costly. We name this decoder class the "ADMM penalized decoder". In our simulation results, the ADMM penalized decoder with $\ell_1$ and $\ell_2$ penalties outperforms both BP and LP decoding at all SNRs. For high SNR regimes where it is infeasible to simulate, we use an instanton analysis and show that the ADMM penalized decoder has better high SNR performance than BP decoding. We also develop a reweighted LP decoder using linear approximations to the objective with an $\ell_1$ penalty. We show that this decoder has an improved theoretical recovery threshold compared to LP decoding. In addition, we show that the empirical gain of the reweighted LP decoder is significant at low SNRs.
Why Local Search Excels in Expression Simplification
Venue: arXiv cs.AI 2014
Year: 2014

Simplifying expressions is important to make numerical integration of large expressions from High Energy Physics tractable. To this end, Horner's method can be used. Finding suitable Horner schemes is assumed to be hard, due to the lack of local heuristics. Recently, MCTS was reported to be able to find near optimal schemes. However, several parameters had to be fine-tuned manually. In this work, we investigate the state space properties of Horner schemes and find that the domain is relatively flat and contains only a few local minima. As a result, the Horner space is appropriate to be explored by Stochastic Local Search (SLS), which has only two parameters: the number of iterations (computation time) and the neighborhood structure. We found a suitable neighborhood structure, leaving only the allowed computation time as a parameter. We performed a range of experiments. The results obtained by SLS are similar or better than those obtained by MCTS. Furthermore, we show that SLS obtains the good results at least 10 times faster. Using SLS, we can speed up numerical integration of many real-world large expressions by at least a factor of 24. For High Energy Physics this means that numerical integrations that took weeks can now be done in hours.
An improvement of a cryptanalysis algorithm
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we present experiments in order to show how some pseudo random number generators can improve the effectiveness of a statistical cryptanalysis algorithm. We deduce mainly that a better generator enhance the accuracy of the cryptanalysis algorithm.
Fast and deterministic computation of the determinant of a polynomial matrix
Venue: arXiv cs.SC 2014
Year: 2014

Given a square, nonsingular matrix of univariate polynomials $\mathbf{F}\in\mathbb{K}[x]^{n\times n}$ over a field $\mathbb{K}$, we give a deterministic algorithm for finding the determinant of $\mathbf{F}$. The complexity of the algorithm is $\bigO \left(n^ωs\right)$ field operations where $s$ is the average column degree or the average row degree of $\mathbf{F}$. Here $\bigO$ notation is Big-$O$ with log factors omitted and $ω$ is the exponent of matrix multiplication.
Low-Dimensional Topology of Information Fusion
Venue: arXiv cs.IT 2014
Year: 2014

We provide an axiomatic characterization of information fusion, on the basis of which we define an information fusion network. Our construction is reminiscent of tangle diagrams in low dimensional topology. Information fusion networks come equipped with a natural notion of equivalence. Equivalent networks `contain the same information', but differ locally. When fusing streams of information, an information fusion network may adaptively optimize itself inside its equivalence class. This provides a fault tolerance mechanism for such networks.
IMAGINARY Math Exhibition using Low-cost 3D Printers
Venue: arXiv cs.CY 2014
Year: 2014

We have made an attempt to reproduce 17 objects of the IMAGINARY Open Mathematics Exhibition (www.imaginary.org) using low-cost, desktop 3D printers. The IMAGINARY open math is an international project by the Mathematisches Forschungsinstitut Oberwolfach in Germany and includes galleries of volumetric objects that are unique, have aesthetic appeal and mathematical meaning. We illustrate here the printing of these diverse learning materials using new 3D affordable printing technologies based on Fused Deposition Modelling (FDM) and the use of biodegradable plastic PLA. The final goal is to support museums, schools and higher education institutions in countries with lower scientific infrastructure.
Distance based (DBCP) Cluster Protocol for Heterogeneous Wireless Sensor Network
Venue: arXiv cs.NI 2014
Year: 2014

Clustering is an important concept to reduce the energy consumption and prolonging the life of a wireless sensor network. In heterogeneous wireless sensor network some of the nodes are equipped with more energy than the other nodes. Many routing algorithms are proposed for heterogeneous wireless sensor network. Stable Election Protocol (SEP) is one of the important protocol in this category. In this research paper a novel energy efficient distance based cluster protocol (DBCP) is proposed for single hop heterogeneous wireless sensor network to increase the life and energy efficiency of a sensor network. DBCP use the average distance of the sensor from the base station as the major issue for the selection of a cluster head in the sensor network.
1-String CZ-Representation of Planar Graphs
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we prove that every planar 4-connected graph has a CZ-representation---a string representation using paths in a rectangular grid that contain at most one vertical segment. Furthermore, two paths representing vertices $u,v$ intersect precisely once whenever there is an edge between $u$ and $v$. The required size of the grid is $n \times 2n$.
Incremental Bounded Model Checking for Embedded Software (extended version)
Venue: arXiv cs.SE 2014
Year: 2014

Program analysis is on the brink of mainstream in embedded systems development. Formal verification of behavioural requirements, finding runtime errors and automated test case generation are some of the most common applications of automated verification tools based on Bounded Model Checking. Existing industrial tools for embedded software use an off-the-shelf Bounded Model Checker and apply it iteratively to verify the program with an increasing number of unwindings. This approach unnecessarily wastes time repeating work that has already been done and fails to exploit the power of incremental SAT solving. This paper reports on the extension of the software model checker CBMC to support incremental Bounded Model Checking and its successful integration with the industrial embedded software verification tool BTC EmbeddedTester. We present an extensive evaluation over large industrial embedded programs, which shows that incremental Bounded Model Checking cuts runtimes by one order of magnitude in comparison to the standard non-incremental approach, enabling the application of formal verification to large and complex embedded software.
An Energy Efficiency policy for Communications with C-RAN, ICN and Transition Smooth
Venue: arXiv cs.IT 2014
Year: 2014

Towards next generation communications, Energy Efficiency (EE) attracts lots of attentions nowadays. Some innovative techniques have been proposed in prior literatures, especially the sleep mechanism of base station (BS). Yet how to sleep and when to sleep are still vague concepts. Another, most of the studies focus on the cellular section or core networks separately while integral and comprehensive version is neglected in prior literatures. In this paper,the integral optimization structure is studied based on cloud radio network (C-RAN) and information centric network (ICN) that raised latest combined with the sleep mode. The original C-RAN and ICN structures are amended in terms of reality application of sleep techniques. While adopting the sleep techniques both in core and cellular, apart from previous works, a transition smooth method that solve the current surge problems which is ignored before is further proposed. Based on the new method, it will be much more feasible to adopt the sleep techniques by knowing the appropriate occasion for transition between sleep and idle mode. Comprehensive computer based simulation results demonstrate that this integer proposal achieves better EE feature with negligible impact on quality of service (QoS) of user equipments (UEs).
On the strengths of connectivity and robustness in general random intersection graphs
Venue: arXiv cs.DM 2014
Year: 2014

Random intersection graphs have received much attention for nearly two decades, and currently have a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. In this paper, we investigate the strengths of connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for $k$-connectivity and $k$-robustness, as well as the asymptotically exact probability of $k$-connectivity, for any positive integer $k$. The $k$-connectivity property quantifies how resilient is the connectivity of a graph against node or edge failures. On the other hand, $k$-robustness measures the effectiveness of local diffusion strategies (that do not use global graph topology information) in spreading information over the graph in the presence of misbehaving nodes. In addition to presenting the results under the general random intersection graph model, we consider two special cases of the general model, a binomial random intersection graph and a uniform random intersection graph, which both have numerous applications as well. For these two specialized graphs, our results on asymptotically exact probabilities of $k$-connectivity and asymptotic zero-one laws for $k$-robustness are also novel in the literature.
Domain Adaptive Neural Networks for Object Recognition
Venue: arXiv cs.CV 2014
Year: 2014

We propose a simple neural network model to deal with the domain adaptation problem in object recognition. Our model incorporates the Maximum Mean Discrepancy (MMD) measure as a regularization in the supervised learning to reduce the distribution mismatch between the source and target domains in the latent space. From experiments, we demonstrate that the MMD regularization is an effective tool to provide good domain adaptation models on both SURF features and raw image pixels of a particular image data set. We also show that our proposed model, preceded by the denoising auto-encoder pretraining, achieves better performance than recent benchmark models on the same data sets. This work represents the first study of MMD measure in the context of neural networks.
Spatially-sparse convolutional neural networks
Venue: arXiv cs.CV 2014
Year: 2014

Convolutional neural networks (CNNs) perform well on problems such as handwriting recognition and image classification. However, the performance of the networks is often limited by budget and time constraints, particularly when trying to train deep networks. Motivated by the problem of online handwriting recognition, we developed a CNN for processing spatially-sparse inputs; a character drawn with a one-pixel wide pen on a high resolution grid looks like a sparse matrix. Taking advantage of the sparsity allowed us more efficiently to train and test large, deep CNNs. On the CASIA-OLHWDB1.1 dataset containing 3755 character classes we get a test error of 3.82%. Although pictures are not sparse, they can be thought of as sparse by adding padding. Applying a deep convolutional network using sparsity has resulted in a substantial reduction in test error on the CIFAR small picture datasets: 6.28% on CIFAR-10 and 24.30% for CIFAR-100.
1-HKUST: Object Detection in ILSVRC 2014
Venue: arXiv cs.CV 2014
Year: 2014

The Imagenet Large Scale Visual Recognition Challenge (ILSVRC) is the one of the most important big data challenges to date. We participated in the object detection track of ILSVRC 2014 and received the fourth place among the 38 teams. We introduce in our object detection system a number of novel techniques in localization and recognition. For localization, initial candidate proposals are generated using selective search, and a novel bounding boxes regression method is used for better object localization. For recognition, to represent a candidate proposal, we adopt three features, namely, RCNN feature, IFV feature, and DPM feature. Given these features, category-specific combination functions are learned to improve the object recognition rate. In addition, object context in the form of background priors and object interaction priors are learned and applied in our system. Our ILSVRC 2014 results are reported alongside with the results of other participating teams.
Detecting People in Cubist Art
Venue: arXiv cs.CV 2014
Year: 2014

Although the human visual system is surprisingly robust to extreme distortion when recognizing objects, most evaluations of computer object detection methods focus only on robustness to natural form deformations such as people's pose changes. To determine whether algorithms truly mirror the flexibility of human vision, they must be compared against human vision at its limits. For example, in Cubist abstract art, painted objects are distorted by object fragmentation and part-reorganization, to the point that human vision often fails to recognize them. In this paper, we evaluate existing object detection methods on these abstract renditions of objects, comparing human annotators to four state-of-the-art object detectors on a corpus of Picasso paintings. Our results demonstrate that while human perception significantly outperforms current methods, human perception and part-based models exhibit a similarly graceful degradation in object detection performance as the objects become increasingly abstract and fragmented, corroborating the theory of part-based object representation in the brain.
Engineering Autonomous Driving Software
Venue: arXiv cs.SE 2014
Year: 2014

A larger number of people with heterogeneous knowledge and skills running a project together needs an adaptable, target, and skill-specific engineering process. This especially holds for a project to develop a highly innovative, autonomously driving vehicle to participate in the 2007 DARPA Urban Challenge. In this contribution, we present essential elements of a software and systems engineering process to develop a so-called artificial intelligence capable of driving autonomously in complex urban situations. The process itself includes agile concepts, like a test first approach, continuous integration of all software modules, and a reliable release and configuration management assisted by software tools in integrated development environments. However, one of the most important elements for an efficient and stringent development is the ability to efficiently test the behavior of the developed system in a flexible and modular system simulation for urban situations both interactively and unattendedly. We call this the simulate first approach.
System Model-Based Definition of Modeling Language Semantics
Venue: arXiv cs.SE 2014
Year: 2014

In this paper, we present an approach to define the semantics for object-oriented modeling languages. One important property of this semantics is to support underspecified and incomplete models. To this end, semantics is given as predicates over elements of the semantic domain. This domain is called the system model which is a general declarative characterization of object systems. The system model is very detailed since it captures various relevant structural, behavioral, and interaction aspects. This allows us to re-use the system model as a domain for various kinds of object-oriented modeling languages. As a major consequence the integration of language semantics is straight-forward. The whole approach is supported by tools that do not constrain the semantics definition's expressiveness and flexibility while making it machinecheckable.