OpenRaiser/Intern-Atlas huggingface dataset:
Temporal Network Optimization Subject to Connectivity Constraints
Venue: arXiv cs.DM 2018
Year: 2018

In this work we consider \emph{temporal networks}, i.e. networks defined by a \emph{labeling} $λ$ assigning to each edge of an \emph{underlying graph} $G$ a set of \emph{discrete} time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on \emph{path problems} of temporal networks. In particular, we consider \emph{time-respecting} paths, i.e. paths whose edges are assigned by $λ$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a \emph{natural analogue of Menger's theorem} holding for arbitrary temporal networks. Finally, we propose two \emph{cost minimization parameters} for temporal network design. One is the \emph{temporality} of $G$, in which the goal is to minimize the maximum number of labels of an edge, and the other is the \emph{temporal cost} of $G$, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some \emph{connectivity constraint}. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.
Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
Venue: arXiv cs.FL 2018
Year: 2018

Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions.
The Fallacy of Favoring Gradual Replacement Mind Uploading Over Scan-and-Copy
Venue: arXiv cs.OH 2018
Year: 2018

Mind uploading speculation and debate often concludes that a procedure described as gradual in-place replacement preserves personal identity while a procedure described as destructive scan-and-copy produces some other identity in the target substrate such that personal identity is lost along with the biological brain. This paper demonstrates a chain of reasoning that establishes metaphysical equivalence between these two methods in terms of preserving personal identity.
Sampling Correctors
Venue: arXiv cs.DS 2018
Year: 2018

In many situations, sample data is obtained from a noisy or imperfect source. In order to address such corruptions, this paper introduces the concept of a sampling corrector. Such algorithms use structure that the distribution is purported to have, in order to allow one to make "on-the-fly" corrections to samples drawn from probability distributions. These algorithms then act as filters between the noisy data and the end user. We show connections between sampling correctors, distribution learning algorithms, and distribution property testing algorithms. We show that these connections can be utilized to expand the applicability of known distribution learning and property testing algorithms as well as to achieve improved algorithms for those tasks. As a first step, we show how to design sampling correctors using proper learning algorithms. We then focus on the question of whether algorithms for sampling correctors can be more efficient in terms of sample complexity than learning algorithms for the analogous families of distributions. When correcting monotonicity, we show that this is indeed the case when also granted query access to the cumulative distribution function. We also obtain sampling correctors for monotonicity without this stronger type of access, provided that the distribution be originally very close to monotone (namely, at a distance $O(1/\log^2 n)$). In addition to that, we consider a restricted error model that aims at capturing "missing data" corruptions. In this model, we show that distributions that are close to monotone have sampling correctors that are significantly more efficient than achievable by the learning approach. We also consider the question of whether an additional source of independent random bits is required by sampling correctors to implement the correction process.
Weihrauch-completeness for layerwise computability
Venue: arXiv cs.LO 2018
Year: 2018

We introduce the notion of being Weihrauch-complete for layerwise computability and provide several natural examples related to complex oscillations, the law of the iterated logarithm and Birkhoff's theorem. We also consider hitting time operators, which share the Weihrauch degree of the former examples but fail to be layerwise computable.
$k$-center Clustering under Perturbation Resilience
Venue: arXiv cs.DS 2018
Year: 2018

The $k$-center problem is a canonical and long-studied facility location and clustering problem with many applications in both its symmetric and asymmetric forms. Both versions of the problem have tight approximation factors on worst case instances. Therefore to improve on these ratios, one must go beyond the worst case. In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric $k$-center problems under a natural input stability (promise) condition called $α$-perturbation resilience [Bilu and Linia 2012], which states that the optimal solution does not change under any alpha-factor perturbation to the input distances. We provide algorithms that give strong guarantees simultaneously for stable and non-stable instances: our algorithms always inherit the worst-case guarantees of clustering approximation algorithms, and output the optimal solution if the input is $2$-perturbation resilient. Furthermore, we prove our result is tight by showing symmetric $k$-center under $(2-ε)$-perturbation resilience is hard unless $NP=RP$. The impact of our results are multifaceted. This is the first tight result for any problem under perturbation resilience. Furthermore, our results illustrate a surprising relationship between symmetric and asymmetric $k$-center instances under perturbation resilience. Unlike approximation ratio, for which symmetric $k$-center is easily solved to a factor of 2 but asymmetric $k$-center cannot be approximated to any constant factor, both symmetric and asymmetric $k$-center can be solved optimally under resilience to 2-perturbations. Finally, our guarantees in the setting where only part of the data satisfies perturbation resilience makes these algorithms more applicable to real-life instances.
Synthesising Executable Gene Regulatory Networks from Single-cell Gene Expression Data
Venue: arXiv cs.CE 2018
Year: 2018

Recent experimental advances in biology allow researchers to obtain gene expression profiles at single-cell resolution over hundreds, or even thousands of cells at once. These single-cell measurements provide snapshots of the states of the cells that make up a tissue, instead of the population-level averages provided by conventional high-throughput experiments. This new data therefore provides an exciting opportunity for computational modelling. In this paper we introduce the idea of viewing single-cell gene expression profiles as states of an asynchronous Boolean network, and frame model inference as the problem of reconstructing a Boolean network from its state space. We then give a scalable algorithm to solve this synthesis problem. We apply our technique to both simulated and real data. We first apply our technique to data simulated from a well established model of common myeloid progenitor differentiation. We show that our technique is able to recover the original Boolean network rules. We then apply our technique to a large dataset taken during embryonic development containing thousands of cell measurements. Our technique synthesises matching Boolean networks, and analysis of these models yields new predictions about blood development which our experimental collaborators were able to verify.
Fuzzy Least Squares Twin Support Vector Machines
Venue: arXiv cs.AI 2018
Year: 2018

Least Squares Twin Support Vector Machine (LST-SVM) has been shown to be an efficient and fast algorithm for binary classification. It combines the operating principles of Least Squares SVM (LS-SVM) and Twin SVM (T-SVM); it constructs two non-parallel hyperplanes (as in T-SVM) by solving two systems of linear equations (as in LS-SVM). Despite its efficiency, LST-SVM is still unable to cope with two features of real-world problems. First, in many real-world applications, labels of samples are not deterministic; they come naturally with their associated membership degrees. Second, samples in real-world applications may not be equally important and their importance degrees affect the classification. In this paper, we propose Fuzzy LST-SVM (FLST-SVM) to deal with these two characteristics of real-world data. Two models are introduced for FLST-SVM: the first model builds up crisp hyperplanes using training samples and their corresponding membership degrees. The second model, on the other hand, constructs fuzzy hyperplanes using training samples and their membership degrees. Numerical evaluation of the proposed method with synthetic and real datasets demonstrate significant improvement in the classification accuracy of FLST-SVM when compared to well-known existing versions of SVM.
Coalgebraic Infinite Traces and Kleisli Simulations
Venue: arXiv cs.LO 2018
Year: 2018

Kleisli simulation is a categorical notion introduced by Hasuo to verify finite trace inclusion. They allow us to give definitions of forward and backward simulation for various types of systems. A generic categorical theory behind Kleisli simulation has been developed and it guarantees the soundness of those simulations with respect to finite trace semantics. Moreover, those simulations can be aided by forward partial execution (FPE)---a categorical transformation of systems previously introduced by the authors. In this paper, we give Kleisli simulation a theoretical foundation that assures its soundness also with respect to infinitary traces. There, following Jacobs' work, infinitary trace semantics is characterized as the "largest homomorphism." It turns out that soundness of forward simulations is rather straightforward; that of backward simulation holds too, although it requires certain additional conditions and its proof is more involved. We also show that FPE can be successfully employed in the infinitary trace setting to enhance the applicability of Kleisli simulations as witnesses of trace inclusion. Our framework is parameterized in the monad for branching as well as in the functor for linear-time behaviors; for the former we mainly use the powerset monad (for nondeterminism), the sub-Giry monad (for probability), and the lift monad (for exception).
Compressing Communication in Distributed Protocols
Venue: arXiv cs.DC 2018
Year: 2018

We show how to compress communication in selection protocols, where the goal is to agree on a sequence of random bits using only a broadcast channel. More specifically, we present a generic method for converting any selection protocol, into another selection protocol where each message is ``short'' while preserving the same number of rounds, the same output distribution, and the same resilience to error. Assuming that the output of the protocol lies in some universe of size $M$, in our resulting protocol each message consists of only $\mathsf{polylog}(M,n,d)$ many bits, where $n$ is the number of parties and $d$ is the number of rounds. Our transformation works in the presence of either static or adaptive Byzantine faults. As a corollary, we conclude that for any $\mathsf{poly}(n)$-round collective coin-flipping protocol, leader election protocol, or general selection protocols, messages of length $\mathsf{polylog}(n)$ suffice (in the presence of either static or adaptive Byzantine faults).
Soft Computing Techniques for Change Detection in remotely sensed images : A Review
Venue: arXiv cs.NE 2018
Year: 2018

With the advent of remote sensing satellites, a huge repository of remotely sensed images is available. Change detection in remotely sensed images has been an active research area as it helps us understand the transitions that are taking place on the Earths surface. This paper discusses the methods and their classifications proposed by various researchers for change detection. Since use of soft computing based techniques are now very popular among research community, this paper also presents a classification based on learning techniques used in soft-computing methods for change detection.
Multi-View Factorization Machines
Venue: arXiv cs.LG 2018
Year: 2018

For a learning task, data can usually be collected from different sources or be represented from multiple views. For example, laboratory results from different medical examinations are available for disease diagnosis, and each of them can only reflect the health state of a person from a particular aspect/view. Therefore, different views provide complementary information for learning tasks. An effective integration of the multi-view information is expected to facilitate the learning performance. In this paper, we propose a general predictor, named multi-view machines (MVMs), that can effectively include all the possible interactions between features from multiple views. A joint factorization is embedded for the full-order interaction parameters which allows parameter estimation under sparsity. Moreover, MVMs can work in conjunction with different loss functions for a variety of machine learning tasks. A stochastic gradient descent method is presented to learn the MVM model. We further illustrate the advantages of MVMs through comparison with other methods for multi-view classification, including support vector machines (SVMs), support tensor machines (STMs) and factorization machines (FMs).
A note on patch-based low-rank minimization for fast image denoising
Venue: arXiv cs.CV 2018
Year: 2018

Patch-based low-rank minimization for image processing attracts much attention in recent years. The minimization of the matrix rank coupled with the Frobenius norm data fidelity can be solved by the hard thresholding filter with principle component analysis (PCA) or singular value decomposition (SVD). Based on this idea, we propose a patch-based low-rank minimization method for image denoising. The main denoising process is stated in three equivalent way: PCA, SVD and low-rank minimization. Compared to recent patch-based sparse representation methods, experiments demonstrate that the proposed method is rather rapid, and it is effective for a variety of natural grayscale images and color images, especially for texture parts in images. Further improvements of this method are also given. In addition, due to the simplicity of this method, we could provide an explanation of the choice of the threshold parameter, estimation of PSNR values, and give other insights into this method.
The Complexity of Non-Iterated Probabilistic Justification Logic
Venue: arXiv cs.LO 2018
Year: 2018

The logic PJ is a probabilistic logic defined by adding (non-iterated) probability operators to the basic justification logic J. In this paper we establish upper and lower bounds for the complexity of the derivability problem in the logic PJ. The main result of the paper is that the complex- ity of the derivability problem in PJ remains the same as the complexity of the derivability problem in the underlying logic J, which is Πp2-complete. This implies hat the probability operators do not increase the complex- ity of the logic, although they arguably enrich the expressiveness of the language.
On Identifying Anomalies in Tor Usage with Applications in Detecting Internet Censorship
Venue: arXiv cs.CY 2018
Year: 2018

We develop a means to detect ongoing per-country anomalies in the daily usage metrics of the Tor anonymous communication network, and demonstrate the applicability of this technique to identifying likely periods of internet censorship and related events. The presented approach identifies contiguous anomalous periods, rather than daily spikes or drops, and allows anomalies to be ranked according to deviation from expected behaviour. The developed method is implemented as a running tool, with outputs published daily by mailing list. This list highlights per-country anomalous Tor usage, and produces a daily ranking of countries according to the level of detected anomalous behaviour. This list has been active since August 2016, and is in use by a number of individuals, academics, and NGOs as an early warning system for potential censorship events. We focus on Tor, however the presented approach is more generally applicable to usage data of other services, both individually and in combination. We demonstrate that combining multiple data sources allows more specific identification of likely Tor blocking events. We demonstrate the our approach in comparison to existing anomaly detection tools, and against both known historical internet censorship events and synthetic datasets. Finally, we detail a number of significant recent anomalous events and behaviours identified by our tool.
Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
Venue: arXiv cs.DS 2018
Year: 2018

We consider construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection $\mathcal{T}$ of texts, where a new symbol may be appended to any text in $\mathcal{T} = \{T_1, \ldots, T_K\}$, at any time. This fully-online scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved semi-online text indexing problem, where texts $T_1, \ldots, T_{k}$ are permanently fixed before the next text $T_{k+1}$ is processed for each $1 \leq k < K$. We present fully-online algorithms that construct the suffix tree and the DAWG for $\mathcal{T}$ in $O(N \log σ)$ time and $O(N)$ space, where $N$ is the total lengths of the strings in $\mathcal{T}$ and $σ$ is their alphabet size. The standard explicit representation of the suffix tree leaf edges and some DAWG edges must be relaxed in our fully-online scenario, since too many updates on these edges are required in the worst case. Instead, we provide access to the updated suffix tree leaf edge labels and the DAWG edges to be redirected via auxiliary data structures, in $O(\log σ)$ time per added character.
Mobile Multi-View Object Image Search
Venue: arXiv cs.MM 2018
Year: 2018

High user interaction capability of mobile devices can help improve the accuracy of mobile visual search systems. At query time, it is possible to capture multiple views of an object from different viewing angles and at different scales with the mobile device camera to obtain richer information about the object compared to a single view and hence return more accurate results. Motivated by this, we developed a mobile multi-view object image search system, using a client-server architecture. Multi-view images of objects acquired by the mobile clients are processed and local features are sent to the server, which combines the query image representations with early/late fusion methods based on bag-of-visual-words and sends back the query results. We performed a comprehensive analysis of early and late fusion approaches using various similarity functions, on an existing single view and a new multi-view object image database. The experimental results show that multi-view search provides significantly better retrieval accuracy compared to single view search.
Proving the Turing Universality of Oritatami Co-Transcriptional Folding (Full Text)
Venue: arXiv cs.CG 2018
Year: 2018

We study the oritatami model for molecular co-transcriptional folding. In oritatami systems, the transcript (the "molecule") folds as it is synthesized (transcribed), according to a local energy optimisation process, which is similar to how actual biomolecules such as RNA fold into complex shapes and functions as they are transcribed. We prove that there is an oritatami system embedding universal computation in the folding process itself. Our result relies on the development of a generic toolbox, which is easily reusable for future work to design complex functions in oritatami systems. We develop "low-level" tools that allow to easily spread apart the encoding of different "functions" in the transcript, even if they are required to be applied at the same geometrical location in the folding. We build upon these low-level tools, a programming framework with increasing levels of abstraction, from encoding of instructions into the transcript to logical analysis. This framework is similar to the hardware-to-algorithm levels of abstractions in standard algorithm theory. These various levels of abstractions allow to separate the proof of correctness of the global behavior of our system, from the proof of correctness of its implementation. Thanks to this framework, we were able to computerize the proof of correctness of its implementation and produce certificates, in the form of a relatively small number of proof trees, compact and easily readable and checkable by human, while encapsulating huge case enumerations. We believe this particular type of certificates can be generalized to other discrete dynamical systems, where proofs involve large case enumerations as well.
Offline and Online Models of Budget Allocation for Maximizing Influence Spread
Venue: arXiv cs.DS 2018
Year: 2018

The research of influence propagation in social networks via word-of-mouth processes has been given considerable attention in recent years. Arguably, the most fundamental problem in this domain is influence maximization, where the goal is to identify a seed set of individuals that can trigger a large cascade of influence in the network. While there has been significant progress regarding this problem and its variants, one basic shortcoming of the models is that they lack the flexibility in the way the budget is allocated to individuals. Indeed, budget allocation is a critical issue in advertising and viral marketing. Taking the other point of view, known models allowing flexible budget allocation do not take into account the influence spread in the network. We introduce a generalized model that captures both budgets and influence propagation simultaneously. For the offline setting, we identify a large family of budget-based propagation functions that admit tight approximation guarantee. This family extends most of the previously studied influence models, including the well-known Triggering model. We establish that any function in this family implies an instance of a monotone submodular function maximization over the integer lattice subject to a knapsack constraint. This problem is known to admit an optimal (1-1/e)-approximation. We also study the price of anarchy of the multi-player game that extends the model and establish tight results. For the online setting, in which an unknown subset of agents arrive in a random order and the algorithm needs to make an irrevocable budget allocation in each step, we develop a 1/(15e)-competitive algorithm. This setting extends the secretary problem, and its variant, the submodular knapsack secretary problem. Notably, our algorithm improves over the best known approximation for the latter problem, even though it applies to a more general setting.