OpenRaiser/Intern-Atlas huggingface dataset:
Keeping Authorities "Honest or Bust" with Decentralized Witness Cosigning
Venue: arXiv cs.CR 2016
Year: 2016

The secret keys of critical network authorities - such as time, name, certificate, and software update services - represent high-value targets for hackers, criminals, and spy agencies wishing to use these keys secretly to compromise other hosts. To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S's exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients' privacy, and offers the first transparency mechanism effective against persistent man-in-the-middle attackers who control a victim's Internet access, the authority's secret key, and several witnesses' secret keys. CoSi builds on existing cryptographic multisignature methods, scaling them to support thousands of witnesses via signature aggregation over efficient communication trees. A working prototype demonstrates CoSi in the context of timestamping and logging authorities, enabling groups of over 8,000 distributed witnesses to cosign authoritative statements in under two seconds.
Understanding SAT is in P
Venue: arXiv cs.CC 2016
Year: 2016

We introduce the idea of an understanding with respect to a set of clauses as a satisfying truth assignment explained by the contexts of the literals in the clauses. Following this idea, we present a mechanical process that obtains, if it exists, an understanding with respect to a 3-SAT problem instance based on the contexts of each literal in the instance, otherwise it determines that none exists. We demonstrate that our process is correct and efficient in solving 3-SAT.
The Minimum Wiener Connector
Venue: arXiv cs.SI 2016
Year: 2016

The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph $G=(V,E)$ and a set $Q\subseteq V$ of query vertices, find a subgraph of $G$ that connects all query vertices and has minimum Wiener index. We show that The Minimum Wiener Connector admits a polynomial-time (albeit impractical) exact algorithm for the special case where the number of query vertices is bounded. We show that in general the problem is NP-hard, and has no PTAS unless $\mathbf{P} = \mathbf{NP}$. Our main contribution is a constant-factor approximation algorithm running in time $\widetilde{O}(|Q||E|)$. A thorough experimentation on a large variety of real-world graphs confirms that our method returns smaller and denser solutions than other methods, and does so by adding to the query set $Q$ a small number of important vertices (i.e., vertices with high centrality).
Information-Theoretic Caching: Sequential Coding for Computing
Venue: arXiv cs.IT 2016
Year: 2016

Under the paradigm of caching, partial data is delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users' requests. For the single-user case, a single-letter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyner's common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray--Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.
A Query Language for Multi-version Data Web Archives
Venue: arXiv cs.DB 2016
Year: 2016

The Data Web refers to the vast and rapidly increasing quantity of scientific, corporate, government and crowd-sourced data published in the form of Linked Open Data, which encourages the uniform representation of heterogeneous data items on the web and the creation of links between them. The growing availability of open linked datasets has brought forth significant new challenges regarding their proper preservation and the management of evolving information within them. In this paper, we focus on the evolution and preservation challenges related to publishing and preserving evolving linked data across time. We discuss the main problems regarding their proper modelling and querying and provide a conceptual model and a query language for modelling and retrieving evolving data along with changes affecting them. We present in details the syntax of the query language and demonstrate its functionality over a real-world use case of evolving linked dataset from the biological domain.
Fully bordered words
Venue: arXiv cs.FL 2016
Year: 2016

We characterize binary words that have exactly two unbordered conjugates and show that they can be expressed as a product of two palindromes.
Explicit Model Checking of Very Large MDP using Partitioning and Secondary Storage
Venue: arXiv cs.LO 2016
Year: 2016

The applicability of model checking is hindered by the state space explosion problem in combination with limited amounts of main memory. To extend its reach, the large available capacities of secondary storage such as hard disks can be exploited. Due to the specific performance characteristics of secondary storage technologies, specialised algorithms are required. In this paper, we present a technique to use secondary storage for probabilistic model checking of Markov decision processes. It combines state space exploration based on partitioning with a block-iterative variant of value iteration over the same partitions for the analysis of probabilistic reachability and expected-reward properties. A sparse matrix-like representation is used to store partitions on secondary storage in a compact format. All file accesses are sequential, and compression can be used without affecting runtime. The technique has been implemented within the Modest Toolset. We evaluate its performance on several benchmark models of up to 3.5 billion states. In the analysis of time-bounded properties on real-time models, our method neutralises the state space explosion induced by the time bound in its entirety.
Unit Interval Editing is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2016
Year: 2016

Given a graph~$G$ and integers $k_1$, $k_2$, and~$k_3$, the unit interval editing problem asks whether $G$ can be transformed into a unit interval graph by at most $k_1$ vertex deletions, $k_2$ edge deletions, and $k_3$ edge additions. We give an algorithm solving this problem in time $2^{O(k\log k)}\cdot (n+m)$, where $k := k_1 + k_2 + k_3$, and $n, m$ denote respectively the numbers of vertices and edges of $G$. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed-parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time $O(4^k \cdot (n + m))$. Another result is an $O(6^k \cdot (n + m))$-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time $O(6^k \cdot n^6)$.
Coding Schemes for Discrete Memoryless Multicast Networks with Rate-limited Feedback
Venue: arXiv cs.IT 2016
Year: 2016

Coding schemes for discrete memoryless multicast networks (DM-MN) with rate-limited feedback from the receivers and relays to the transmitter are proposed. The schemes improve over the noisy network coding proposed by Lim et al.. For the single relay channel with relay-transmitter feedback, our coding schemes recover Gabbai and Bross's results, and strictly improve on noisy network coding, distributed decode-forward coding proposed by Lim et al., and all known lower bounds on the achievable rates proposed for the setup without feedback. The coding schemes are based on block-Markov coding, superposition coding, sliding-window/backward decoding and hybrid relaying strategies. In our Scheme 1A, the relays and receivers use compress-forward strategy and send the compression indices to the transmitter through the feedback pipes. After obtaining the compression indices through feedback, the transmitter sends them together with the source message. Each receiver uses backward decoding to jointly decode the source message and all compression indices. Our Scheme 1B is similar, except that here each relay not only uses compress forward to compress its channel outputs, but also performs partial decode forward to decode a common part of source message. Our Scheme 1C allows different relays to decode different parts of the source message (in Scheme 1A, no relay decodes any part of the source message; in Scheme 1B, all relays decode the same part of source message), which can achieve higher rates than Scheme 1A and Scheme 1B. Motivated by the feedback coding scheme, we propose a new coding scheme for DM-MN without feedback, where the transmitter decodes the compression indices instead of obtaining them directly through feedback. It is shown that the scheme still improves noisy network coding and distributed decode-forward coding for some channels.
Integrating Abstractions to Enhance the Execution of Distributed Applications
Venue: arXiv cs.DC 2016
Year: 2016

One of the factors that limits the scale, performance, and sophistication of distributed applications is the difficulty of concurrently executing them on multiple distributed computing resources. In part, this is due to a poor understanding of the general properties and performance of the coupling between applications and dynamic resources. This paper addresses this issue by integrating abstractions representing distributed applications, resources, and execution processes into a pilot-based middleware. The middleware provides a platform that can specify distributed applications, execute them on multiple resource and for different configurations, and is instrumented to support investigative analysis. We analyzed the execution of distributed applications using experiments that measure the benefits of using multiple resources, the late-binding of scheduling decisions, and the use of backfill scheduling.
Composite Correlation Quantization for Efficient Multimodal Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

Efficient similarity retrieval from large-scale multimodal database is pervasive in modern search engines and social networks. To support queries across content modalities, the system should enable cross-modal correlation and computation-efficient indexing. While hashing methods have shown great potential in achieving this goal, current attempts generally fail to learn isomorphic hash codes in a seamless scheme, that is, they embed multiple modalities in a continuous isomorphic space and separately threshold embeddings into binary codes, which incurs substantial loss of retrieval accuracy. In this paper, we approach seamless multimodal hashing by proposing a novel Composite Correlation Quantization (CCQ) model. Specifically, CCQ jointly finds correlation-maximal mappings that transform different modalities into isomorphic latent space, and learns composite quantizers that convert the isomorphic latent features into compact binary codes. An optimization framework is devised to preserve both intra-modal similarity and inter-modal correlation through minimizing both reconstruction and quantization errors, which can be trained from both paired and partially paired data in linear time. A comprehensive set of experiments clearly show the superior effectiveness and efficiency of CCQ against the state of the art hashing methods for both unimodal and cross-modal retrieval.
Compression and the origins of Zipf's law of abbreviation
Venue: arXiv cs.IT 2016
Year: 2016

Languages across the world exhibit Zipf's law of abbreviation, namely more frequent words tend to be shorter. The generalized version of the law - an inverse relationship between the frequency of a unit and its magnitude - holds also for the behaviours of other species and the genetic code. The apparent universality of this pattern in human language and its ubiquity in other domains calls for a theoretical understanding of its origins. To this end, we generalize the information theoretic concept of mean code length as a mean energetic cost function over the probability and the magnitude of the types of the repertoire. We show that the minimization of that cost function and a negative correlation between probability and the magnitude of types are intimately related.
Parameterized complexity dichotomy for $(r,\ell)$-Vertex Deletion
Venue: arXiv cs.DS 2016
Year: 2016

For two integers $r, \ell \geq 0$, a graph $G = (V, E)$ is an $(r,\ell)$-graph if $V$ can be partitioned into $r$ independent sets and $\ell$ cliques. In the parameterized $(r,\ell)$-Vertex Deletion problem, given a graph $G$ and an integer $k$, one has to decide whether at most $k$ vertices can be removed from $G$ to obtain an $(r,\ell)$-graph. This problem is NP-hard if $r+\ell \geq 1$ and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of $(r,\ell)$-Vertex Deletion was known for all values of $(r,\ell)$ except for $(2,1)$, $(1,2)$, and $(2,2)$. We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of $k$. We consider as well the version of $(r,\ell)$-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.
Combining local regularity estimation and total variation optimization for scale-free texture segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Texture segmentation constitutes a standard image processing task, crucial to many applications. The present contribution focuses on the particular subset of scale-free textures and its originality resides in the combination of three key ingredients: First, texture characterization relies on the concept of local regularity ; Second, estimation of local regularity is based on new multiscale quantities referred to as wavelet leaders ; Third, segmentation from local regularity faces a fundamental bias variance trade-off: In nature, local regularity estimation shows high variability that impairs the detection of changes, while a posteriori smoothing of regularity estimates precludes from locating correctly changes. Instead, the present contribution proposes several variational problem formulations based on total variation and proximal resolutions that effectively circumvent this trade-off. Estimation and segmentation performance for the proposed procedures are quantified and compared on synthetic as well as on real-world textures.
On-the-fly Approximation of Multivariate Total Variation Minimization
Venue: arXiv cs.LG 2016
Year: 2016

In the context of change-point detection, addressed by Total Variation minimization strategies, an efficient on-the-fly algorithm has been designed leading to exact solutions for univariate data. In this contribution, an extension of such an on-the-fly strategy to multivariate data is investigated. The proposed algorithm relies on the local validation of the Karush-Kuhn-Tucker conditions on the dual problem. Showing that the non-local nature of the multivariate setting precludes to obtain an exact on-the-fly solution, we devise an on-the-fly algorithm delivering an approximate solution, whose quality is controlled by a practitioner-tunable parameter, acting as a trade-off between quality and computational cost. Performance assessment shows that high quality solutions are obtained on-the-fly while benefiting of computational costs several orders of magnitude lower than standard iterative procedures. The proposed algorithm thus provides practitioners with an efficient multivariate change-point detection on-the-fly procedure.
Object Detection Networks on Convolutional Feature Maps
Venue: arXiv cs.CV 2016
Year: 2016

Most object detectors contain two important components: a feature extractor and an object classifier. The feature extractor has rapidly evolved with significant research efforts leading to better deep convolutional architectures. The object classifier, however, has not received much attention and many recent systems (like SPPnet and Fast/Faster R-CNN) use simple multi-layer perceptrons. This paper demonstrates that carefully designing deep networks for object classification is just as important. We experiment with region-wise classifier networks that use shared, region-independent convolutional features. We call them "Networks on Convolutional feature maps" (NoCs). We discover that aside from deep feature maps, a deep and convolutional per-region classifier is of particular importance for object detection, whereas latest superior image classification models (such as ResNets and GoogLeNets) do not directly lead to good detection accuracy without using such a per-region classifier. We show by experiments that despite the effective ResNets and Faster R-CNN systems, the design of NoCs is an essential element for the 1st-place winning entries in ImageNet and MS COCO challenges 2015.
A One-step Approach to Computing a Polytopic Robust Positively Invariant Set
Venue: arXiv cs.SY 2016
Year: 2016

A procedure and theoretical results are presented for the problem of determining a minimal robust positively invariant (RPI) set for a linear discrete-time system subject to unknown, bounded disturbances. The procedure computes, via the solving of a single LP, a polytopic RPI set that is minimal with respect to the family of RPI sets generated from a finite number of inequalities with pre-defined normal vectors.
Aashiyana: Design and Evaluation of a Smart Demand-Response System for Highly-stressed Grids
Venue: arXiv cs.OH 2016
Year: 2016

This paper targets the unexplored problem of demand response within the context of power-grids that are allowed to regularly enforce blackouts as a mean to balance supply with demand:highly-stressed grids. Currently these utilities use as a cyclic and binary (power/no-power) schedule over consumer groups leading to significant wastage of capacity and long hours of no-power. We present here a novel building DLC system, Aashiyana, that can enforce several user-defined low-power states. We evaluate distributed and centralized load-shedding schemes using Aashiyana that can, compared to current load-shedding strategy, reduce the number of homes with no power by 80% for minor change in the fraction of homes with full-power.
Homophily and Triadic Closure in Evolving Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

We present a new network model accounting for multidimensional assortativity. Each node is characterized by a number of features and the probability of a link between two nodes depends on common features. We do not fix a priori the total number of possible features. The bipartite network of the nodes and the features evolves according to a stochastic dynamics that depends on three parameters that respectively regulate the preferential attachment in the transmission of the features to the nodes, the number of new features per node, and the power-law behavior of the total number of observed features. Our model also takes into account a mechanism of triadic closure. We provide theoretical results and statistical estimators for the parameters of the model. We validate our approach by means of simulations and an empirical analysis of a network of scientific collaborations.
MultiAspect Graphs: Algebraic representation and algorithms
Venue: arXiv cs.DM 2016
Year: 2016

We present the algebraic representation and basic algorithms for MultiAspect Graphs (MAGs). A MAG is a structure capable of representing multilayer and time-varying networks, as well as higher-order networks, while also having the property of being isomorphic to a directed graph. In particular, we show that, as a consequence of the properties associated with the MAG structure, a MAG can be represented in matrix form. Moreover, we also show that any possible MAG function (algorithm) can be obtained from this matrix-based representation. This is an important theoretical result since it paves the way for adapting well-known graph algorithms for application in MAGs. We present a set of basic MAG algorithms, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Therefore, such examples can be seen as guidelines on how to properly derive MAG algorithms from basic algorithms on directed graph. We also make available Python implementations of all the algorithms presented in this paper.
Reward Processes and Performance Simulation in Supermarket Models with Different Servers
Venue: arXiv cs.PF 2016
Year: 2016

Supermarket models with different servers become a key in modeling resource management of stochastic networks, such as, computer networks, manufacturing systems and transportation networks. While these different servers always make analysis of such a supermarket model more interesting, difficult and challenging. This paper provides a new novel method for analyzing the supermarket model with different servers through a multi-dimensional continuous-time Markov reward processes. Firstly, the utility functions are constructed for expressing a routine selection mechanism that depends on queue lengths, on service rates, and on some probabilities of individual preference. Then applying the continuous-time Markov reward processes, some segmented stochastic integrals of the random reward function are established by means of an event-driven technique. Based on this, the mean of the random reward function in a finite time period is effectively computed by means of the state jump points of the Markov reward process, and also the mean of the discounted random reward function in an infinite time period can be calculated through the same event-driven technique. Finally, some simulation experiments are given to indicate how the expected queue length of each server depends on the main parameters of this supermarket model.