OpenRaiser/Intern-Atlas huggingface dataset:
Strong Connectivity in Directed Graphs under Failures, with Application
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we investigate some basic connectivity problems in directed graphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, and let $G\setminus e$ be the digraph obtained after deleting edge $e$ from $G$. As a first result, we show how to compute in $O(m+n)$ worst-case time: $(i)$ The total number of strongly connected components in $G\setminus e$, for all edges $e$ in $G$. $(ii)$ The size of the largest and of the smallest strongly connected components in $G\setminus e$, for all edges $e$ in $G$. Let $G$ be strongly connected. We say that edge $e$ separates two vertices $x$ and $y$, if $x$ and $y$ are no longer strongly connected in $G\setminus e$. As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: $(i)$ Report in $O(n)$ worst-case time all the strongly connected components of $G\setminus e$, for a query edge $e$. $(ii)$ Test whether an edge separates two query vertices in $O(1)$ worst-case time. $(iii)$ Report all edges that separate two query vertices in optimal worst-case time, i.e., in time $O(k)$, where $k$ is the number of separating edges. (For $k=0$, the time is $O(1)$). All of the above results extend to vertex failures. All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by the $1$-connectivity (i.e., $1$-edge and $1$-vertex) cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$ edges that maintains the $1$-connectivity cuts of $G$ and the decompositions induced by those cuts.
Channel Simulation and Coded Source Compression
Venue: arXiv cs.IT 2019
Year: 2019

Coded source compression, also known as source compression with helpers, has been a major variant of distributed source compression, but has hitherto received little attention in the quantum regime. This work treats and solves the corresponding quantum coded source compression through an observation that connects coded source compression with channel simulation. First, we consider classical source coding with quantum side information where the quantum side information is observed by a helper and sent to the decoder via a classical channel. We derive a single-letter characterization of the achievable rate region for this problem. The direct coding theorem of our result is proved via the measurement compression theory of Winter, a quantum-to-classical channel simulation. Our result reveals that a helper's scheme which separately conducts a measurement and a compression is suboptimal, and measurement compression seems necessary to achieve the optimal rate region. We then study coded source compression in the fully quantum regime, where two different scenarios are considered depending on the types of communication channels between the legitimate source and the receiver. We further allow entanglement assistance from the quantum helper in both scenarios. We characterize the involved quantum resources, and derive single-letter expressions of the achievable rate region. The direct coding proofs are based on well-known quantum protocols, the quantum state merging protocol and the fully quantum Slepian-Wolf protocol, together with the quantum reverse Shannon theorem.
Bootstrapping Ternary Relation Extractors
Venue: arXiv cs.CL 2019
Year: 2019

Binary relation extraction methods have been widely studied in recent years. However, few methods have been developed for higher n-ary relation extraction. One limiting factor is the effort required to generate training data. For binary relations, one only has to provide a few dozen pairs of entities per relation, as training data. For ternary relations (n=3), each training instance is a triplet of entities, placing a greater cognitive load on people. For example, many people know that Google acquired Youtube but not the dollar amount or the date of the acquisition and many people know that Hillary Clinton is married to Bill Clinton by not the location or date of their wedding. This makes higher n-nary training data generation a time consuming exercise in searching the Web. We present a resource for training ternary relation extractors. This was generated using a minimally supervised yet effective approach. We present statistics on the size and the quality of the dataset.
Right-jumps and pattern avoiding permutations
Venue: arXiv cs.DM 2019
Year: 2019

We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of this class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we show that their asymptotics involves a rather unusual algebraic exponent (the golden ratio $(1+\sqrt 5)/2$) and some unusual closed-form constants. We end by proving a limit law: a forbidden pattern of length $n$ has typically $(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations.
Well-Stratified Linked Data for Well-Behaved Data Citation
Venue: arXiv cs.DL 2019
Year: 2019

In this paper we analyse the functional requirements of linked data citation and identify a minimal set of operations and primitives needed to realize such task. Citing linked data implies solving a series of data provenance issues and finding a way to identify data subsets. Those two tasks can be handled defining a simple type system inside data and verifying it with a type checker, which is significantly less complex than interpreting reified RDF statements and can be implemented in a non data invasive way. Finally we suggest that data citation should be handled outside of the data, possibly with an ad-hoc language.
Coherence for Frobenius pseudomonoids and the geometry of linear proofs
Venue: arXiv cs.LO 2019
Year: 2019

We prove coherence theorems for Frobenius pseudomonoids and snakeorators in monoidal bicategories. As a consequence we obtain a 3d notation for proofs in nonsymmetric multiplicative linear logic, with a geometrical notion of equivalence, and without the need for a global correctness criterion or thinning links. We argue that traditional proof nets are the 2d projections of these 3d diagrams.
Ant-Inspired Density Estimation via Random Walks
Venue: arXiv cs.DC 2019
Year: 2019

Many ant species employ distributed population density estimation in applications ranging from quorum sensing [Pra05], to task allocation [Gor99], to appraisal of enemy colony strength [Ada90]. It has been shown that ants estimate density by tracking encounter rates -- the higher the population density, the more often the ants bump into each other [Pra05,GPT93]. We study distributed density estimation from a theoretical perspective. We prove that a group of anonymous agents randomly walking on a grid are able to estimate their density within a small multiplicative error in few steps by measuring their rates of encounter with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), our bound nearly matches what would be required to estimate density by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis provides new tools for understanding complex dependencies in the collision probabilities of multiple random walks. We bound the strength of these dependencies using $local\ mixing\ properties$ of the underlying graph. Our results extend beyond the grid to more general graphs and we discuss applications to size estimation for social networks and density estimation for robot swarms.
On Optimal Policies in Full-Duplex Wireless Powered Communication Networks
Venue: arXiv cs.IT 2019
Year: 2019

The optimal resource allocation scheme in a full-duplex Wireless Powered Communication Network (WPCN) composed of one Access Point (AP) and two wireless devices is analyzed and derived. AP operates in a full-duplex mode and is able to broadcast wireless energy signals in downlink and receive information data in uplink simultaneously. On the other hand, each wireless device is assumed to be equipped with Radio-Frequency (RF) energy harvesting circuitry which gathers the energy sent by AP and stores it in a finite capacity battery. The harvested energy is then used for performing uplink data transmission tasks. In the literature, the main focus so far has been on slot-oriented optimization. In this context, all the harvested RF energy in a given slot is also consumed in the same slot. However, this approach leads to sub-optimal solutions because it does not take into account the Channel State Information (CSI) variations over future slots. Differently from most of the prior works, in this paper we focus on the long-term weighted throughput maximization problem. This approach significantly increases the complexity of the optimization problem since it requires to consider both CSI variations over future slots and the evolution of the batteries when deciding the optimal resource allocation. We formulate the problem using the Markov Decision Process (MDP) theory and show how to solve it. Our numerical results emphasize the superiority of our proposed full-duplex WPCN compared to the half-duplex WPCN and reveal interesting insights about the effects of perfect as well as imperfect self-interference cancellation techniques on the network performance.
Learning Local Descriptors by Optimizing the Keypoint-Correspondence Criterion: Applications to Face Matching, Learning from Unlabeled Videos and 3D-Shape Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

Current best local descriptors are learned on a large dataset of matching and non-matching keypoint pairs. However, data of this kind is not always available since detailed keypoint correspondences can be hard to establish. On the other hand, we can often obtain labels for pairs of keypoint bags. For example, keypoint bags extracted from two images of the same object under different views form a matching pair, and keypoint bags extracted from images of different objects form a non-matching pair. On average, matching pairs should contain more corresponding keypoints than non-matching pairs. We describe an end-to-end differentiable architecture that enables the learning of local keypoint descriptors from such weakly-labeled data. Additionally, we discuss how to improve the method by incorporating the procedure of mining hard negatives. We also show how can our approach be used to learn convolutional features from unlabeled video signals and 3D models. Our implementation is available at https://github.com/nenadmarkus/wlrn
Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex
Venue: arXiv cs.IT 2019
Year: 2019

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is $d=Θ({q})$, where $q$ is the code alphabet size (in fact, $d$ can be as big as $q/4$ in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing \cite{C11,CCX12}), we are able to locally recover arbitrarily large number $k$ of coordinates of a Reed-Muller code simultaneously at the cost of querying $O(q^2k)$ coordinates. It turns out that our local decoding of Reed-Muller codes shows ({\it perhaps surprisingly}) that accessing $k$ locations is in fact cheaper than repeating the procedure for accessing a single location for $k$ times. Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.
On the mediation of program allocation in high-demand environments
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we challenge the widely accepted premise that, in order to carry out a distributed computation, say on the cloud, users have to inform, along with all the inputs that the algorithm in use requires, the number of processors to be used. We discuss the complicated nature of deciding the value of such parameter, should it be chosen optimally, and propose the alternative scenario in which this choice is passed on to the server side for automatic determination. We show that the allocation problem arising from this alternative is NP-hard only weakly, being therefore solvable in pseudo-polynomial time. In our proposal, one key component on which the automatic determination of the number of processors is based is the cost model. The one we use, which is being increasingly adopted in the wake of the cloud-computing movement, posits that each single execution of a program is to be subject to current circumstances on both user and server side, and as such be priced independently of all others. Running through our proposal is thus a critique of the established common sense that sizing a set of processors to handle a submission to some provider is entirely up to the user.
Optimal Rates for Multi-pass Stochastic Gradient Methods
Venue: arXiv cs.LG 2019
Year: 2019

We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. We study how regularization properties are controlled by the step-size, the number of passes and the mini-batch size. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases. As a byproduct, we derive optimal convergence results for batch gradient methods (even in the non-attainable cases).
Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms
Venue: arXiv cs.SY 2019
Year: 2019

We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend the state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.
On the Complexity and Decidability of Some Problems Involving Shuffle
Venue: arXiv cs.FL 2019
Year: 2019

The complexity and decidability of various decision problems involving the shuffle operation are studied. The following three problems are all shown to be $NP$-complete: given a nondeterministic finite automaton (NFA) $M$, and two words $u$ and $v$, is $L(M)$ not a subset of $u$ shuffled with $v$, is $u$ shuffled with $v$ not a subset of $L(M)$, and is $L(M)$ not equal to $u$ shuffled with $v$? It is also shown that there is a polynomial-time algorithm to determine, for $NFA$s $M_1, M_2$ and a deterministic pushdown automaton $M_3$, whether $L(M_1)$ shuffled with $L(M_2)$ is a subset of $L(M_3)$. The same is true when $M_1, M_2,M_3$ are one-way nondeterministic $l$-reversal-bounded $k$-counter machines, with $M_3$ being deterministic. Other decidability and complexity results are presented for testing whether given languages $L_1, L_2$ and $R$ from various languages families satisfy $L_1$ shuffled with $L_2$ is a subset of $R$, and $R$ is a subset of $L_1$ shuffled with $L_2$. Several closure results on shuffle are also shown.
Device and Circuit Interaction Analysis of Stochastic Behaviors in Cross-Point RRAM Arrays
Venue: arXiv cs.ET 2019
Year: 2019

Stochastic behaviors of resistive random access memory (RRAM) play an important role in the design of cross-point memory arrays. A Monte Carlo compact model of oxide RRAM is developed and calibrated with experiments on various device stack configurations. With Monte Carlo SPICE simulations, we show that an increase in array size and interconnect wire resistance will statistically deteriorate write functionality. Write failure probability (WFP) has an exponential dependency on device uniformity and supply voltage (VDD), and the array bias scheme is a key knob. Lowering array VDD leads to higher effective energy consumption (EEC) due to the increase in WFP when the variation statistics are included in the analysis. Random-access simulations indicate that data sparsity statistically benefits write functionality and energy consumption. Finally, we show that a pseudo-sub-array topology with uniformly distributed pre-forming cells in the pristine high resistance state is able to reduce both WFP and EEC, enabling higher net capacity for memory circuits due to improved variation tolerance.
Machine-based Multimodal Pain Assessment Tool for Infants: A Review
Venue: arXiv cs.CV 2019
Year: 2019

Bedside caregivers assess infants' pain at constant intervals by observing specific behavioral and physiological signs of pain. This standard has two main limitations. The first limitation is the intermittent assessment of pain, which might lead to missing pain when the infants are left unattended. Second, it is inconsistent since it depends on the observer's subjective judgment and differs between observers. The intermittent and inconsistent assessment can induce poor treatment and, therefore, cause serious long-term consequences. To mitigate these limitations, the current standard can be augmented by an automated system that monitors infants continuously and provides quantitative and consistent assessment of pain. Several automated methods have been introduced to assess infants' pain automatically based on analysis of behavioral or physiological pain indicators. This paper comprehensively reviews the automated approaches (i.e., approaches to feature extraction) for analyzing infants' pain and the current efforts in automatic pain recognition. In addition, it reviews the databases available to the research community and discusses the current limitations of the automated pain assessment.
Singular persistent homology with geometrically parallelizable computation
Venue: arXiv cs.CG 2019
Year: 2019

Persistent homology is a popular tool in Topological Data Analysis. It provides numerical characteristics of data sets which reflect global geometric properties. In order to be useful in practice, for example for feature generation in machine learning, it needs to be effectively computable. Classical homology is a computable topological invariant because of the Mayer-Vietoris exact and spectral sequences associated to coverings of a space. We state and prove versions of the Mayer-Vietoris theorem for persistent homology under mild and commonplace assumptions. This is done through the use of a new theory, the singular persistent homology, better suited for handling coverings of data sets. As an application, we create a distributed computational workflow where the advantage is not only or even primarily in speed improvement but in sheer feasibility for large data sets.
Hazelnut: A Bidirectionally Typed Structure Editor Calculus
Venue: arXiv cs.PL 2019
Year: 2019

Structure editors allow programmers to edit the tree structure of a program directly. This can have cognitive benefits, particularly for novice and end-user programmers. It also simplifies matters for tool designers, because they do not need to contend with malformed program text. This paper defines Hazelnut, a structure editor based on a small bidirectionally typed lambda calculus extended with holes and a cursor. Hazelnut goes one step beyond syntactic well-formedness: its edit actions operate over statically meaningful incomplete terms. Naively, this would force the programmer to construct terms in a rigid "outside-in" manner. To avoid this problem, the action semantics automatically places terms assigned a type that is inconsistent with the expected type inside a hole. This safely defers the type consistency check until the term inside the hole is finished. Hazelnut is a foundational type-theoretic account of typed structure editing, rather than an end-user tool itself. To that end, we describe how Hazelnut's rich metatheory, which we have mechanized in Agda, guides the definition of an extension to the calculus. We also discuss various plausible evaluation strategies for terms with holes, and in so doing reveal connections with gradual typing and contextual modal type theory, the Curry-Howard interpretation of contextual modal logic. Finally, we discuss how Hazelnut's semantics lends itself to implementation as a functional reactive program. Our reference implementation is written using js_of_ocaml.
Streaming k-mismatch with error correcting and applications
Venue: arXiv cs.DS 2019
Year: 2019

We present a new streaming algorithm for the $k$-Mismatch problem, one of the most basic problems in pattern matching. Given a pattern and a text, the task is to find all substrings of the text that are at the Hamming distance at most $k$ from the pattern. Our algorithm is enhanced with an important new feature called Error Correcting, and its complexities for $k=1$ and for a general $k$ are comparable to those of the solutions for the $k$-Mismatch problem by Porat and Porat (FOCS 2009) and Clifford et al. (SODA 2016). In parallel to our research, a yet more efficient algorithm for the $k$-Mismatch problem with the Error Correcting feature was developed by Clifford et al. (SODA 2019). Using the new feature and recent work on streaming Multiple Pattern Matching we develop a series of streaming algorithms for pattern matching on weighted strings, which are a commonly used representation of uncertain sequences in molecular biology. We also show that these algorithms are space-optimal up to polylog factors. A preliminary version of this work was published at DCC 2017 conference.