OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Staged Self-Assembly of General Shapes
Venue: arXiv cs.CG 2016
Year: 2016

We analyze the number of tile types $t$, bins $b$, and stages necessary to assemble $n \times n$ squares and scaled shapes in the staged tile assembly model. For $n \times n$ squares, we prove $\mathcal{O}(\frac{\log{n} - tb - t\log t}{b^2} + \frac{\log \log b}{\log t})$ stages suffice and $Ω(\frac{\log{n} - tb - t\log t}{b^2})$ are necessary for almost all $n$. For shapes $S$ with Kolmogorov complexity $K(S)$, we prove $\mathcal{O}(\frac{K(S) - tb - t\log t}{b^2} + \frac{\log \log b}{\log t})$ stages suffice and $Ω(\frac{K(S) - tb - t\log t}{b^2})$ are necessary to assemble a scaled version of $S$, for almost all $S$. We obtain similarly tight bounds when the more powerful flexible glues are permitted.
On Equilibria of N-seller and N-buyer Bargaining Games
Venue: arXiv cs.GT 2016
Year: 2016

A group of players which contain n sellers and n buyers bargain over the partitions of n pies. A seller(/buyer) has to reach an agreement with a buyer (/seller) on the division of a pie. The players bargain in a system like the stock market: each seller(buyer) can either offer a selling(buying) price to all buyers(sellers) or accept a price offered by another buyer(seller). The offered prices are known to all. Once a player accepts a price offered by another one, the division of a pie between them is determined. Each player has a constant discounting factor and the discounting factors of all players are common knowledge. In this article, we prove that the equilibrium of this bargaining problem is a unanimous division rate, which is equivalent to Nash bargaining equilibrium of a two-player bargaining game in which the discounting factors of two players are the average of n buyers and the average of n sellers respectively. This result shows the relevance between bargaining equilibrium and general equilibrium of markets.
Benchmarking Fast Data Platforms for the Aadhaar Biometric Database
Venue: arXiv cs.DC 2016
Year: 2016

Aadhaar is the world's largest biometric database with a billion records, being compiled as an identity platform to deliver social services to residents of India.Aadhaar processes streams of biometric data as residents are enrolled and updated.Besides 1 million enrolments and updates per day,up to 100 million daily biometric authentications are expected during delivery of various public services.These form critical Big Data applications,with large volumes and high velocity of data.
A Semantic Theory of the Internet of Things
Venue: arXiv cs.LO 2016
Year: 2016

We propose a process calculus for modelling systems in the Internet of Things paradigm. Our systems interact both with the physical environment, via sensors and actuators, and with smart devices, via short-range and Internet channels. The calculus is equipped with a standard notion of bisimilarity which is a fully abstract characterisation of a well-known contextual equivalence. We use our semantic proof-methods to prove run-time properties as well as system equalities of non-trivial IoT systems.
From F to DOT: Type Soundness Proofs with Definitional Interpreters
Venue: arXiv cs.PL 2016
Year: 2016

Scala's type system unifies ML modules, object-oriented, and functional programming. The Dependent Object Types (DOT) family of calculi has been proposed as a new foundation for Scala and similar languages. Unfortunately, it is not clear how DOT relates to any well-known type systems, and type soundness has only been established for very restricted subsets. In fact, important Scala features are known to break at least one key metatheoretic property such as environment narrowing or subtyping transitivity, which are usually required for a type soundness proof. First, and, perhaps surprisingly, we show how rich DOT calculi can still be proved sound. The key insight is that narrowing and subtyping transitivity only need to hold for runtime objects, but not for code that is never executed. Alas, the dominant method of proving type soundness, Wright and Felleisen's syntactic approach, is based on term rewriting, which does not a priori make a distinction between runtime and type assignment time. Second, we demonstrate how type soundness can be proved for advanced, polymorphic, type systems with respect to high-level, definitional interpreters, implemented in Coq. We present the first mechanized soundness proof in this style for System F<: and several extensions, including mutable references. Our proofs use only simple induction: another surprising result, as the combination of big-step semantics, mutable references, and polymorphism is commonly believed to require co-inductive proof techniques. Third, we show how DOT-like calculi emerge as generalizations of F<:, exposing a rich design space of calculi with path-dependent types which we collectively call System D. Armed with insights from the definitional interpreter semantics, we also show how equivalent small-step semantics and soundness proofs in Wright-Felleisen-style can be derived for these systems.
Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs
Venue: arXiv cs.CC 2016
Year: 2016

It is known that there are classes of 2-CNFs requiring exponential size non-deterministic read-once branching programs to compute them. However, to the best of our knowledge, there are no superpolynomial lower bounds for branching programs of a higher repetition computing a class of 2-CNFs. This work is an attempt to make a progress in this direction. We consider a class of monotone 3-CNFs that are almost 2-CNFs in the sense that in each clause there is a literal occurring in this clause only. We prove exponential lower bounds for two classes of non-deterministic branching programs. The first class significantly generalizes monotone read-$k$-times {\sc nbp}s and the second class generalizes oblivious read $k$ times branching programs. The lower bounds remain exponential for $k \leq \log n/a$ where $a$ is a sufficiently large constant.
The complexity of signed graph and edge-coloured graph homomorphisms
Venue: arXiv cs.DM 2016
Year: 2016

We study homomorphism problems of signed graphs from a computational point of view. A signed graph $(G,Σ)$ is a graph $G$ where each edge is given a sign, positive or negative; $Σ\subseteq E(G)$ denotes the set of negative edges. Thus, $(G, Σ)$ is a $2$-edge-coloured graph with the property that the edge-colours, $\{+, -\}$, form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph $(G,Σ)$ to a signed graph $(H,Π)$: ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of $G$ to $H$ with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of $G$. We prove a dichotomy theorem for s-homomorphism problems for a large class of (fixed) target signed graphs $(H,Π)$. Specifically, as long as $(H,Π)$ does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of $(H,Π)$ has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if $(H,Π)$ has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of Feder and Vardi.
Arithmetic for Rooted Trees
Venue: arXiv cs.DM 2016
Year: 2016

We propose a new arithmetic for non-empty rooted unordered trees simply called trees. After discussing tree representation and enumeration, we define the operations of tree addition, multiplication and stretch, prove their properties, and show that all trees can be generated from a starting tree of one vertex. We then show how a given tree can be obtained as the sum or product of two trees, thus defining prime trees with respect to addition and multiplication. In both cases we show how primality can be decided in time polynomial in the number of vertices and we prove that factorization is unique. We then define negative trees and suggest dealing with tree equations, giving some preliminary results. Finally we comment on how our arithmetic might be useful, and discuss preceding studies that have some relations with our. To the best of our knowledge our approach and results are completely new aside for an earlier version of this work submitte as an arXiv manuscript.
Unsupervised Ensemble Learning with Dependent Classifiers
Venue: arXiv cs.LG 2016
Year: 2016

In unsupervised ensemble learning, one obtains predictions from multiple sources or classifiers, yet without knowing the reliability and expertise of each source, and with no labeled data to assess it. The task is to combine these possibly conflicting predictions into an accurate meta-learner. Most works to date assumed perfect diversity between the different sources, a property known as conditional independence. In realistic scenarios, however, this assumption is often violated, and ensemble learners based on it can be severely sub-optimal. The key challenges we address in this paper are:\ (i) how to detect, in an unsupervised manner, strong violations of conditional independence; and (ii) construct a suitable meta-learner. To this end we introduce a statistical model that allows for dependencies between classifiers. Our main contributions are the development of novel unsupervised methods to detect strongly dependent classifiers, better estimate their accuracies, and construct an improved meta-learner. Using both artificial and real datasets, we showcase the importance of taking classifier dependencies into account and the competitive performance of our approach.
Many Access for Small Packets Based on Precoding and Sparsity-aware Recovery
Venue: arXiv cs.IT 2016
Year: 2016

Modern mobile terminals produce massive small data packets. For these short-length packets, it is inefficient to follow the current multiple access schemes to allocate transmission resources due to heavy signaling overhead. We propose a non-orthogonal many-access scheme that is well suited for the future communication systems equipped with many receive antennas. The system is modeled as having a block-sparsity pattern with unknown sparsity level (i.e., unknown number of transmitted messages). Block precoding is employed at each single-antenna transmitter to enable the simultaneous transmissions of many users. The number of simultaneously served active users is allowed to be even more than the number of receive antennas. Sparsity-aware recovery is designed at the receiver for joint user detection and symbol demodulation. To reduce the effects of channel fading on signal recovery, normalized block orthogonal matching pursuit (BOMP) algorithm is introduced, and based on its approximate performance analysis, we develop interference cancellation based BOMP (ICBOMP) algorithm. The ICBOMP performs error correction and detection in each iteration of the normalized BOMP. Simulation results demonstrate the effectiveness of the proposed scheme in small packet services, as well as the advantages of ICBOMP in improving signal recovery accuracy and reducing computational cost.
Know Your Phish: Novel Techniques for Detecting Phishing Sites and their Targets
Venue: arXiv cs.CR 2016
Year: 2016

Phishing is a major problem on the Web. Despite the significant attention it has received over the years, there has been no definitive solution. While the state-of-the-art solutions have reasonably good performance, they require a large amount of training data and are not adept at detecting phishing attacks against new targets. In this paper, we begin with two core observations: (a) although phishers try to make a phishing webpage look similar to its target, they do not have unlimited freedom in structuring the phishing webpage; and (b) a webpage can be characterized by a small set of key terms; how these key terms are used in different parts of a webpage is different in the case of legitimate and phishing webpages. Based on these observations, we develop a phishing detection system with several notable properties: it is language-independent, can be implemented entirely on client-side, has excellent classification performance and is fast. In addition, we developed a target identification component that can identify the target website that a phishing webpage is attempting to mimic. The target detection component is faster than previously reported systems and can help minimize false positives in our phishing detection system.
Throughput Analysis of Proportional Fair Scheduling For Sparse and Ultra-Dense Interference-Limited OFDMA/LTE Networks
Venue: arXiv cs.NI 2016
Year: 2016

Various system tasks like interference coordination, handover decisions, admission control etc. in current cellular networks require precise mid-term (spanning over a few seconds) performance models. Due to channel-dependent scheduling at the base station, these performance models are not simple to obtain. Furthermore, LTE cellular systems are interference-limited, hence, the way interference is modelled is crucial for the accuracy. In this paper we present a closed-form analytical performance model for proportional fair scheduling in OFDMA/LTE networks. The model takes into account a precise SINR distribution into account. We refine our model with respect to uniform modulation and coding, as applied in LTE networks. Furthermore, the analytical analysis is extended also for ultra-dense deployments likely to happen in the 5-th generation of cellular networks. The resulting analytical performance model is validated by means of simulations considering realistic network deployments. Compared with related work, our model demonstrates a significantly higher accuracy for long-term throughput estimation.
A 'Gibbs-Newton' Technique for Enhanced Inference of Multivariate Polya Parameters and Topic Models
Venue: arXiv cs.LG 2016
Year: 2016

Hyper-parameters play a major role in the learning and inference process of latent Dirichlet allocation (LDA). In order to begin the LDA latent variables learning process, these hyper-parameters values need to be pre-determined. We propose an extension for LDA that we call 'Latent Dirichlet allocation Gibbs Newton' (LDA-GN), which places non-informative priors over these hyper-parameters and uses Gibbs sampling to learn appropriate values for them. At the heart of LDA-GN is our proposed 'Gibbs-Newton' algorithm, which is a new technique for learning the parameters of multivariate Polya distributions. We report Gibbs-Newton performance results compared with two prominent existing approaches to the latter task: Minka's fixed-point iteration method and the Moments method. We then evaluate LDA-GN in two ways: (i) by comparing it with standard LDA in terms of the ability of the resulting topic models to generalize to unseen documents; (ii) by comparing it with standard LDA in its performance on a binary classification task.
Type-checking Liveness for Collaborative Processes with Bounded and Unbounded Recursion
Venue: arXiv cs.LO 2016
Year: 2016

We present the first session typing system guaranteeing request-response liveness properties for possibly non-terminating communicating processes. The types augment the branch and select types of the standard binary session types with a set of required responses, indicating that whenever a particular label is selected, a set of other labels, its responses, must eventually also be selected. We prove that these extended types are strictly more expressive than standard session types. We provide a type system for a process calculus similar to a subset of collaborative BPMN processes with internal (data-based) and external (event-based) branching, message passing, bounded and unbounded looping. We prove that this type system is sound, i.e., it guarantees request-response liveness for dead-lock free processes. We exemplify the use of the calculus and type system on a concrete example of an infinite state system.
Order-Fractal transition in abstract paintings
Venue: arXiv cs.CV 2016
Year: 2016

We report the degree of order of twenty-two Jackson Pollock's paintings using \emph{Hausdorff-Besicovitch fractal dimension}. Through the maximum value of each multi-fractal spectrum, the artworks are classify by the year in which they were painted. It has been reported that Pollock's paintings are fractal and it increased on his latest works. However our results show that fractal dimension of the paintings are on a range of fractal dimension with values close to two. We identify this behavior as a fractal-order transition. Based on the study of disorder-order transition in physical systems, we interpreted the fractal-order transition through its dark paint strokes in Pollocks' paintings, as structured lines following a power law measured by fractal dimension. We obtain self-similarity in some specific Pollock's paintings, that reveal an important dependence on the scale of observation. We also characterize by its fractal spectrum, the called \emph{Teri's Find}. We obtained similar spectrums between \emph{Teri's Find} and \emph{Number 5} from Pollock, suggesting that fractal dimension cannot be completely rejected as a quantitative parameter to authenticate this kind of artworks.
Prodirect Manipulation: Bidirectional Programming for the Masses
Venue: arXiv cs.SE 2016
Year: 2016

Software interfaces today generally fall at either end of a spectrum. On one end are programmable systems, which allow expert users (i.e. programmers) to write software artifacts that describe complex abstractions, but programs are disconnected from their eventual output. On the other end are domain-specific graphical user interfaces (GUIs), which allow end users (i.e. non-programmers) to easily create varied content but present insurmountable walls when a desired feature is not built-in. Both programmatic and direct manipulation have distinct strengths, but users must typically choose one over the other or use some ad-hoc combination of systems. Our goal, put simply, is to bridge this divide. We envision novel software systems that tightly couple programmatic and direct manipulation --- a combination we dub prodirect manipulation --- for a variety of use cases. This will require advances in a broad range of software engineering disciplines, from program analysis and program synthesis technology to user interface design and evaluation. In this extended abstract, we propose two general strategies --- real-time program synthesis and domain-specific synthesis of general-purpose programs --- that may prove fruitful for overcoming the technical challenges. We also discuss metrics that will be important in evaluating the usability and utility of prodirect manipulation systems.
Dynamic Hierarchical Reactive Controller Synthesis
Venue: arXiv cs.SY 2016
Year: 2016

In the formal approach to reactive controller synthesis, a symbolic controller for a possibly hybrid system is obtained by algorithmically computing a winning strategy in a two-player game. Such game-solving algorithms scale poorly as the size of the game graph increases. However, in many applications, the game graph has a natural hierarchical structure. In this paper, we propose a modeling formalism and a synthesis algorithm that exploits this hierarchical structure for more scalable synthesis. We define local games on hierarchical graphs as a modeling formalism which decomposes a large-scale reactive synthesis problem in two dimensions. First, the construction of a hierarchical game graph introduces abstraction layers, where each layer is again a two-player game graph. Second, every such layer is decomposed into multiple local game graphs, each corresponding to a node in the higher level game graph. While local games have the potential to reduce the state space for controller synthesis, they lead to more complex synthesis problems where strategies computed for one local game can impose additional requirements on lower-level local games. Our second contribution is a procedure to construct a dynamic controller for local game graphs over hierarchies. The controller computes assume-admissible winning strategies that satisfy local specifications in the presence of environment assumptions, and dynamically updates specifications and strategies due to interactions between games at different abstraction layers at each step of the play. We show that our synthesis procedure is sound: the controller constructs a play which satisfies all local specifications. We illustrate our results through an example controlling an autonomous robot in a known, multistory building.
Modeling and Analysis of SiNW FET-Based Molecular Communication Receiver
Venue: arXiv cs.ET 2016
Year: 2016

Molecular Communication (MC) is a bio-inspired communication method based on the exchange of molecules for information transfer among nanoscale devices. MC has been extensively studied from various aspects in the literature; however, the physical design of MC transceiving units is largely neglected with the assumption that network nodes are entirely biological devices, e.g., engineered bacteria, which are intrinsically capable of receiving and transmitting molecular messages. However, the low information processing capacity of biological devices and the challenge to interface them with macroscale networks hinder the true application potential of nanonetworks. To overcome this problem, recently, we proposed a nanobioelectronic MC receiver architecture exploiting the nanoscale field effect transistor-based biosensor (bioFET) technology, which provides noninvasive and sensitive molecular detection while producing electrical signals as the output. In this paper, we introduce a comprehensive model for silicon nanowire (SiNW) FET-based MC receivers by integrating the underlying processes in MC and bioFET to provide a unified analysis framework. We derive closed-form expressions for noise statistics, signal-to-noise ratio (SNR) at the receiver output, and symbol error probability (SEP). Performance evaluation in terms of SNR and SEP reveals the effects of individual system parameters on the detection performance of the proposed MC receiver.
Multiple binomial sums
Venue: arXiv cs.SC 2016
Year: 2016

Multiple binomial sums form a large class of multi-indexed sequences, closed under partial summation, which contains most of the sequences obtained by multiple summation of products of binomial coefficients and also all the sequences with algebraic generating function. We study the representation of the generating functions of binomial sums by integrals of rational functions. The outcome is twofold. Firstly, we show that a univariate sequence is a multiple binomial sum if and only if its generating function is the diagonal of a rational function. Secondly, we propose algorithms that decide the equality of multiple binomial sums and that compute recurrence relations for them. In conjunction with geometric simplifications of the integral representations, this approach behaves well in practice. The process avoids the computation of certificates and the problem of the appearance of spurious singularities that afflicts discrete creative telescoping, both in theory and in practice.