OpenRaiser/Intern-Atlas huggingface dataset:
Structured Interactive Music Scores
Venue: arXiv cs.LO 2018
Year: 2018

Interactive Scores is a formalism for the design and performance of interactive scenarios that provides temporal relations (TRs) among the objects of the scenario. We can model TRs among objects in Time Stream Petri nets, but it is difficult to represent global constraints. This can be done explicitly in the Non-deterministic Timed Concurrent Constraint (ntcc) calculus. We want to formalize a heterogeneous system that controls in one subsystem the concurrent execution of the objects using ntcc, and audio and video processing in the other. We also plan to develop an automatic verifier for ntcc.
$n$-permutability and linear Datalog implies symmetric Datalog
Venue: arXiv cs.CC 2018
Year: 2018

We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspace). At the moment, it is not known for which structures $\mathbb A$ will CSP($\mathbb A$) be solvable by a linear Datalog program. However, once somebody obtains a characterization of linear Datalog, our result immediately gives a characterization of symmetric Datalog.
Measuring Partial Balance in Signed Networks
Venue: arXiv cs.SI 2018
Year: 2018

Is the enemy of an enemy necessarily a friend? If not, to what extent does this tend to hold? Such questions were formulated in terms of signed (social) networks and necessary and sufficient conditions for a network to be "balanced" were obtained around 1960. Since then the idea that signed networks tend over time to become more balanced has been widely used in several application areas. However, investigation of this hypothesis has been complicated by the lack of a standard measure of partial balance, since complete balance is almost never achieved in practice. We formalize the concept of a measure of partial balance, discuss various measures, compare the measures on synthetic datasets, and investigate their axiomatic properties. The synthetic data involves Erdős-Rényi and specially structured random graphs. We show that some measures behave better than others in terms of axioms and ability to differentiate between graphs. We also use well-known datasets from the sociology and biology literature, such as Read's New Guinean tribes, gene regulatory networks related to two organisms, and a network involving senate bill co-sponsorship. Our results show that substantially different levels of partial balance is observed under cycle-based, eigenvalue-based, and frustration-based measures. We make some recommendations for measures to be used in future work.
Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics
Venue: arXiv cs.DM 2018
Year: 2018

There is a common theme to some research questions in additive combinatorics and noise stability. Both study the following basic question: Let $\mathcal{P}$ be a probability distribution over a space $Ω^\ell$ with all $\ell$ marginals equal. Let $\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}$ where $\underline{X}^{(j)} = (X_1^{(j)}, \ldots, X_n^{(j)})$ be random vectors such that for every coordinate $i \in [n]$ the tuples $(X_i^{(1)}, \ldots, X_i^{(\ell)})$ are i.i.d. according to $\mathcal{P}$. A central question that is addressed in both areas is: - Does there exist a function $c_{\mathcal{P}}()$ independent of $n$ such that for every $f: Ω^n \to [0, 1]$ with $\mathrm{E}[f(X^{(1)})] = μ> 0$: \begin{align*} \mathrm{E} \left[ \prod_{j=1}^\ell f(X^{(j)}) \right] \ge c(μ) > 0 \, ? \end{align*} Instances of this question include the finite field model version of Roth's and Szemerédi's theorems as well as Borell's result about the optimality of noise stability of half-spaces. Our goal in this paper is to interpolate between the noise stability theory and the finite field additive combinatorics theory and address the question above in further generality than considered before. In particular, we settle the question for $\ell = 2$ and when $\ell > 2$ and $\mathcal{P}$ has bounded correlation $ρ(\mathcal{P}) < 1$. Under the same conditions we also characterize the _obstructions_ for similar lower bounds in the case of $\ell$ different functions. Part of the novelty in our proof is the combination of analytic arguments from the theories of influences and hyper-contraction with arguments from additive combinatorics.
Deterministic Sparse Suffix Sorting in the Restore Model
Venue: arXiv cs.DS 2018
Year: 2018

Given a text $T$ of length $n$, we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of $T$ in $O(c \sqrt{\lg n} + m \lg m \lg n \lg^* n)$ time with $O(m)$ words of space under the premise that the space of $T$ is rewritable, where $m \le n$ is the number of suffixes to be sorted (provided online and arbitrarily), and $c$ is the number of characters with $m \le c \le n$ that must be compared for distinguishing the designated suffixes.
Fixpoint Node Selection Query Languages for Trees
Venue: arXiv cs.DB 2018
Year: 2018

The study of node selection query languages for (finite) trees has been a major topic in the recent research on query languages for Web documents. On one hand, there has been an extensive study of XPath and its various extensions. On the other hand, query languages based on classical logics, such as first-order logic (FO) or Monadic Second-Order Logic (MSO), have been considered. Results in this area typically relate an XPath-based language to a classical logic. What has yet to emerge is an XPath-related language that is as expressive as MSO, and at the same time enjoys the computational properties of XPath, which are linear time query evaluation and exponential time query-containment test. In this paper we propose muXPath, which is the alternation-free fragment of XPath extended with fixpoint operators. Using two-way alternating automata, we show that this language does combine desired expressiveness and computational properties, placing it as an attractive candidate for the definite node-selection query language for trees.
Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality
Venue: arXiv cs.FL 2018
Year: 2018

We exhaustively explore the reprogrammability capabilities and the intrinsic universality of the Cartesian product $P \times C$ of the space $P$ of all possible computer programs of increasing size and the space $C$ of all possible compilers of increasing length such that $p \in P$ emulates $p^\prime \in P$ with $T|p^\prime|=|p|$ under a coarse-graining transformation $T$. Our approach yields a novel perspective on the complexity, controllability, causality and (re)programmability discrete dynamical systems. We find evidence that the density of (qualitatively different) computer programs that can be reprogrammed grows asymptotically as a function of program and compiler size. To illustrate these findings we show a series of behavioural boundary crossing results, including emulations (for all initial conditions) of Wolfram class 2 Elementary Cellular Automata (ECA) by Class 1 ECA, emulations of Classes 1, 2 and 3 ECA by Class 2 and 3 ECA, and of Classes 1, 2 and 3 by Class 3 ECA, along with results of even greater emulability for general CA (neighbourhood $r=3/2$), including Class 1 CA emulating Classes 2 and 3, and Classes 3 and 4 emulating all other classes (1, 2, 3 and 4). The emulations occur with only a linear overhead and can be considered computationally efficient. We also found that there is no hacking strategy to compress the search space based on compiler profiling in terms of e.g. similarity or complexity, suggesting that no strategy other than exhaustive search is viable. We also introduce emulation networks, derive a topologically-based measure of complexity based upon out- and in-degree connectivity, and establish bridges to fundamental ideas of complexity, universality, causality and dynamical systems.
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
Venue: arXiv cs.CC 2018
Year: 2018

In this short note, we reduce lower bounds on monotone projections of polynomials to lower bounds on extended formulations of polytopes. Applying our reduction to the seminal extended formulation lower bounds of Fiorini, Massar, Pokutta, Tiwari, & de Wolf (STOC 2012; J. ACM, 2015) and Rothvoss (STOC 2014; J. ACM, 2017), we obtain the following interesting consequences. 1. The Hamiltonian Cycle polynomial is not a monotone subexponential-size projection of the permanent; this both rules out a natural attempt at a monotone lower bound on the Boolean permanent, and shows that the permanent is not complete for non-negative polynomials in VNP$_{\mathbb R}$ under monotone p-projections. 2. The cut polynomials and the perfect matching polynomial (or "unsigned Pfaffian") are not monotone p-projections of the permanent. The latter, over the Boolean and-or semi-ring, rules out monotone reductions in one of the natural approaches to reducing perfect matchings in general graphs to perfect matchings in bipartite graphs. As the permanent is universal for monotone formulas, these results also imply exponential lower bounds on the monotone formula size and monotone circuit size of these polynomials.
Beating the Harmonic lower bound for online bin packing
Venue: arXiv cs.DS 2018
Year: 2018

In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. In this paper, we present an online bin packing algorithm with asymptotic competitive ratio of 1.5813. This is the first improvement in fifteen years and reduces the gap to the lower bound by 15%. Within the well-known SuperHarmonic framework, no competitive ratio below 1.58333 can be achieved. We make two crucial changes to that framework. First, some of our algorithm's decisions depend on exact sizes of items, instead of only their types. In particular, for each item with size in (1/3,1/2], we use its exact size to determine if it can be packed together with an item of size greater than 1/2. Second, we add constraints to the linear programs considered by Seiden, in order to better lower bound the optimal solution. These extra constraints are based on marks that we give to items based on how they are packed by our algorithm. We show that for each input, a single weighting function can be constructed to upper bound the competitive ratio on it. We use this idea to simplify the analysis of SuperHarmonic, and show that the algorithm Harmonic++ is in fact 1.58880-competitive (Seiden proved 1.58889), and that 1.5884 can be achieved within the SuperHarmonic framework. Finally, we give a lower bound of 1.5762 for our new framework.
The Game of Phishing
Venue: arXiv cs.CR 2018
Year: 2018

The current implementation of TLS involves your browser displaying a padlock, and a green bar, after successfully verifying the digital signature on the TLS certificate. Proposed is a solution where your browser's response to successful verification of a TLS certificate is to display a login window. That login window displays the identity credentials from the TLS certificate, to allow the user to authenticate Bob. It also displays a 'user-browser' shared secret i.e. a specific picture from your hard disk. This is not SiteKey, the image is shared between the computer user and their browser. It is never transmitted over the internet. Since sandboxed websites cannot access your hard disk this image cannot be counterfeited by phishing websites. Basically if you view the installed software component of your browser as an actor in the cryptography protocol, then the solution to phishing attacks is classic cryptography, as documented in any cryptography textbook.
Heterogeneous Knowledge Transfer in Video Emotion Recognition, Attribution and Summarization
Venue: arXiv cs.CV 2018
Year: 2018

Emotion is a key element in user-generated videos. However, it is difficult to understand emotions conveyed in such videos due to the complex and unstructured nature of user-generated content and the sparsity of video frames expressing emotion. In this paper, for the first time, we study the problem of transferring knowledge from heterogeneous external sources, including image and textual data, to facilitate three related tasks in understanding video emotion: emotion recognition, emotion attribution and emotion-oriented summarization. Specifically, our framework (1) learns a video encoding from an auxiliary emotional image dataset in order to improve supervised video emotion recognition, and (2) transfers knowledge from an auxiliary textual corpora for zero-shot recognition of emotion classes unseen during training. The proposed technique for knowledge transfer facilitates novel applications of emotion attribution and emotion-oriented summarization. A comprehensive set of experiments on multiple datasets demonstrate the effectiveness of our framework.
Loss Functions for Neural Networks for Image Processing
Venue: arXiv cs.CV 2018
Year: 2018

Neural networks are becoming central in several areas of computer vision and image processing and different architectures have been proposed to solve specific problems. The impact of the loss layer of neural networks, however, has not received much attention in the context of image processing: the default and virtually only choice is L2. In this paper, we bring attention to alternative choices for image restoration. In particular, we show the importance of perceptually-motivated losses when the resulting image is to be evaluated by a human observer. We compare the performance of several losses, and propose a novel, differentiable error function. We show that the quality of the results improves significantly with better loss functions, even when the network architecture is left unchanged.
Prototypical Priors: From Improving Classification to Zero-Shot Learning
Venue: arXiv cs.CV 2018
Year: 2018

Recent works on zero-shot learning make use of side information such as visual attributes or natural language semantics to define the relations between output visual classes and then use these relationships to draw inference on new unseen classes at test time. In a novel extension to this idea, we propose the use of visual prototypical concepts as side information. For most real-world visual object categories, it may be difficult to establish a unique prototype. However, in cases such as traffic signs, brand logos, flags, and even natural language characters, these prototypical templates are available and can be leveraged for an improved recognition performance. The present work proposes a way to incorporate this prototypical information in a deep learning framework. Using prototypes as prior information, the deepnet pipeline learns the input image projections into the prototypical embedding space subject to minimization of the final classification loss. Based on our experiments with two different datasets of traffic signs and brand logos, prototypical embeddings incorporated in a conventional convolutional neural network improve the recognition performance. Recognition accuracy on the Belga logo dataset is especially noteworthy and establishes a new state-of-the-art. In zero-shot learning scenarios, the same system can be directly deployed to draw inference on unseen classes by simply adding the prototypical information for these new classes at test time. Thus, unlike earlier approaches, testing on seen and unseen classes is handled using the same pipeline, and the system can be tuned for a trade-off of seen and unseen class performance as per task requirement. Comparison with one of the latest works in the zero-shot learning domain yields top results on the two datasets mentioned above.
Exploiting a Geometrically Sampled Grid in the SRP-PHAT for Localization Improvement and Power Response Sensitivity Analysis
Venue: arXiv cs.SD 2018
Year: 2018

The steered response power phase transform (SRP-PHAT) is a beamformer method very attractive in acoustic localization applications due to its robustness in reverberant environments. This paper presents a spatial grid design procedure, called the geometrically sampled grid (GSG), which aims at computing the spatial grid by taking into account the discrete sampling of time difference of arrival (TDOA) functions and the desired spatial resolution. A new SRP-PHAT localization algorithm based on the GSG method is also introduced. The proposed method exploits the intersections of the discrete hyperboloids representing the TDOA information domain of the sensor array, and projects the whole TDOA information on the space search grid. The GSG method thus allows to design the sampled spatial grid which represents the best search grid for a given sensor array, it allows to perform a sensitivity analysis of the array and to characterize its spatial localization accuracy, and it may assist the system designer in the reconfiguration of the array. Experimental results using both simulated data and real recordings show that the localization accuracy is substantially improved both for high and for low spatial resolution, and that it is closely related to the proposed power response sensitivity measure.
ABCNN: Attention-Based Convolutional Neural Network for Modeling Sentence Pairs
Venue: arXiv cs.CL 2018
Year: 2018

How to model a pair of sentences is a critical issue in many NLP tasks such as answer selection (AS), paraphrase identification (PI) and textual entailment (TE). Most prior work (i) deals with one individual task by fine-tuning a specific system; (ii) models each sentence's representation separately, rarely considering the impact of the other sentence; or (iii) relies fully on manually designed, task-specific linguistic features. This work presents a general Attention Based Convolutional Neural Network (ABCNN) for modeling a pair of sentences. We make three contributions. (i) ABCNN can be applied to a wide variety of tasks that require modeling of sentence pairs. (ii) We propose three attention schemes that integrate mutual influence between sentences into CNN; thus, the representation of each sentence takes into consideration its counterpart. These interdependent sentence pair representations are more powerful than isolated sentence representations. (iii) ABCNN achieves state-of-the-art performance on AS, PI and TE tasks.
Eigenlogic in the spirit of George Boole
Venue: arXiv cs.LO 2018
Year: 2018

This work presents an operational and geometric approach to logic. It starts from the multilinear elective decomposition of binary logical functions in the original form introduced by George Boole. A justification on historical grounds is presented bridging Boole's theory and the use of his arithmetical logical functions with the axioms of Boolean algebra using sets and quantum logic. It is shown that this algebraic polynomial formulation can be naturally extended to operators in finite vector spaces. Logical operators will appear as commuting projection operators and the truth values, which take the binary values {0,1}, are the respective eigenvalues. In this view the solution of a logical proposition resulting from the operation on a combination of arguments will appear as a selection where the outcome can only be one of the eigenvalues. In this way propositional logic can be formalized in linear algebra by using elective developments which correspond here to combinations of tensored elementary projection operators. The original and principal motivation of this work is for applications in the new field of quantum information, differences are outlined with more traditional quantum logic approaches.
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic $(1+ε)$-approximation algorithms whose amortized time (over some number of link changes) is sublinear in $D$, the maximum diameter of the network. Our technique also leads to a deterministic $(1+ε)$-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach [JACM 1981] that is optimal under some assumptions [Roditty and Zwick ESA 2004, Henzinger et al. STOC 2015]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.
Algebraic File Synchronization: Adequacy and Completeness
Venue: arXiv cs.DC 2018
Year: 2018

With distributed computing and mobile applications, synchronizing diverging replicas of data structures is a more and more common problem. We use algebraic methods to reason about filesystem operations, and introduce a simplified definition of conflicting updates to filesystems. We also define algorithms for update detection and reconciliation and present rigorous proofs that they not only work as intended, but also cannot be improved on. To achieve this, we introduce a novel, symmetric set of filesystem commands with higher information content, which removes edge cases and increases the predictive powers of our algebraic model. We also present a number of generally useful classes and properties of sequences of commands. While these results are often intuitive, providing exact proofs for them is far from trivial. They contribute to our understanding of this special type of algebraic model, and toward building more complete algebras of filesystem trees and extending algebraic approaches to other data storage protocols. They also form a theoretical basis for specifying and guaranteeing the error-free operation of applications that implement an algebraic approach to synchronization.
Differentially Private Oblivious RAM
Venue: arXiv cs.CR 2018
Year: 2018

In this work, we investigate if statistical privacy can enhance the performance of ORAM mechanisms while providing rigorous privacy guarantees. We propose a formal and rigorous framework for developing ORAM protocols with statistical security viz., a differentially private ORAM (DP-ORAM). We present Root ORAM, a family of DP-ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, local storage and system security. We theoretically analyze Root ORAM to quantify both its security and performance. We experimentally demonstrate the benefits of Root ORAM and find that (1) Root ORAM can reduce local storage overhead by about 2x for a reasonable values of privacy budget, significantly enhancing performance in memory limited platforms such as trusted execution environments, and (2) Root ORAM allows tunable trade-offs between bandwidth, storage, and privacy, reducing bandwidth overheads by up to 2x-10x (at the cost of increased storage/statistical privacy), enabling significant reductions in ORAM access latencies for cloud environments. We also analyze the privacy guarantees of DP-ORAMs through the lens of information theoretic metrics of Shannon entropy and Min-entropy [16]. Finally, Root ORAM is ideally suited for applications which have a similar access pattern, and we showcase its utility via the application of Private Information Retrieval.