OpenRaiser/Intern-Atlas huggingface dataset:
Strong Converse Exponent for State Dependent Channels With Full State Information at the Sender
Venue: arXiv cs.IT 2020
Year: 2020

We consider the state dependent channels with full state information with at the sender. For this state dependent channel, the channel capacity was determined by Gel'fand and Pinsker. In this paper, we study the correct probability of decoding at rates above the capacity. We prove that when the transmission rate is above the capacity this probability goes to zero exponentially and derive an explicit lower bound of this exponent function.
The Parameterized Hardness of Art Gallery Problems
Venue: arXiv cs.CG 2020
Year: 2020

Given a simple polygon $\mathcal{P}$ on $n$ vertices, two points $x,y$ in $\mathcal{P}$ are said to be visible to each other if the line segment between $x$ and $y$ is contained in $\mathcal{P}$. The Point Guard Art Gallery problem asks for a minimum set $S$ such that every point in $\mathcal{P}$ is visible from a point in $S$. The Vertex Guard Art Gallery problem asks for such a set $S$ subset of the vertices of $\mathcal{P}$. A point in the set $S$ is referred to as a guard. For both variants, we rule out any $f(k)n^{o(k / \log k)}$ algorithm, where $k := |S|$ is the number of guards, for any computable function $f$, unless the Exponential Time Hypothesis fails. These lower bounds almost match the $n^{O(k)}$ algorithms that exist for both problems.
Bridging the Gaps Between Residual Learning, Recurrent Neural Networks and Visual Cortex
Venue: arXiv cs.LG 2020
Year: 2020

We discuss relations between Residual Networks (ResNet), Recurrent Neural Networks (RNNs) and the primate visual cortex. We begin with the observation that a special type of shallow RNN is exactly equivalent to a very deep ResNet with weight sharing among the layers. A direct implementation of such a RNN, although having orders of magnitude fewer parameters, leads to a performance similar to the corresponding ResNet. We propose 1) a generalization of both RNN and ResNet architectures and 2) the conjecture that a class of moderately deep RNNs is a biologically-plausible model of the ventral stream in visual cortex. We demonstrate the effectiveness of the architectures by testing them on the CIFAR-10 and ImageNet dataset.
New Results on Linear Size Distance Preservers
Venue: arXiv cs.DS 2020
Year: 2020

Given $p$ node pairs in an $n$-node graph, a distance preserver is a sparse subgraph that agrees with the original graph on all of the given pairwise distances. We prove the following bounds on the number of edges needed for a distance preserver: - Any $p$ node pairs in a directed weighted graph have a distance preserver on $O(n + n^{2/3} p)$ edges. - Any $p = Ω\left(\frac{n^2}{rs(n)}\right)$ node pairs in an undirected unweighted graph have a distance preserver on $O(p)$ edges, where $rs(n)$ is the Ruzsa-Szemerédi function from combinatorial graph theory. - As a lower bound, there are examples where one needs $ω(σ^2)$ edges to preserve all pairwise distances within a subset of $σ= o(n^{2/3})$ nodes in an undirected weighted graph. If we additionally require that the graph is unweighted, then the range of this lower bound falls slightly to $σ\le n^{2/3 - o(1)}$.
Option Discovery in Hierarchical Reinforcement Learning using Spatio-Temporal Clustering
Venue: arXiv cs.LG 2020
Year: 2020

This paper introduces an automated skill acquisition framework in reinforcement learning which involves identifying a hierarchical description of the given task in terms of abstract states and extended actions between abstract states. Identifying such structures present in the task provides ways to simplify and speed up reinforcement learning algorithms. These structures also help to generalize such algorithms over multiple tasks without relearning policies from scratch. We use ideas from dynamical systems to find metastable regions in the state space and associate them with abstract states. The spectral clustering algorithm PCCA+ is used to identify suitable abstractions aligned to the underlying structure. Skills are defined in terms of the sequence of actions that lead to transitions between such abstract states. The connectivity information from PCCA+ is used to generate these skills or options. These skills are independent of the learning task and can be efficiently reused across a variety of tasks defined over the same model. This approach works well even without the exact model of the environment by using sample trajectories to construct an approximate estimate. We also present our approach to scaling the skill acquisition framework to complex tasks with large state spaces for which we perform state aggregation using the representation learned from an action conditional video prediction network and use the skill acquisition framework on the aggregated state space.
How to Fake Multiply by a Gaussian Matrix
Venue: arXiv cs.DS 2020
Year: 2020

Have you ever wanted to multiply an $n \times d$ matrix $X$, with $n \gg d$, on the left by an $m \times n$ matrix $\tilde G$ of i.i.d. Gaussian random variables, but could not afford to do it because it was too slow? In this work we propose a new randomized $m \times n$ matrix $T$, for which one can compute $T \cdot X$ in only $O(\text{nnz}(X)) + \tilde O(m^2 \cdot d^{3})$ time, for which the total variation distance between the distributions $T \cdot X$ and $\tilde G \cdot X$ is as small as desired, i.e., less than any positive constant. Here $\text{nnz}(X)$ denotes the number of non-zero entries of $X$. Assuming $\text{nnz}(X) \gg m^2 \cdot d^{3}$, this is a significant savings over the naïve $O(\text{nnz}(X) m)$ time to compute $\tilde G \cdot X$. Moreover, since the total variation distance is small, we can provably use $T \cdot X$ in place of $\tilde G \cdot X$ in any application and have the same guarantees as if we were using $\tilde G \cdot X$, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).
Robust Massively Parallel Sorting
Venue: arXiv cs.DC 2020
Year: 2020

We investigate distributed memory parallel sorting algorithms that scale to the largest available machines and are robust with respect to input size and distribution of the input elements. The main outcome is that four sorting algorithms cover the entire range of possible input sizes. For three algorithms we devise new low overhead mechanisms to make them robust with respect to duplicate keys and skewed input distributions. One of these, designed for medium sized inputs, is a new variant of quicksort with fast high-quality pivot selection. At the same time asymptotic analysis provides performance guarantees and guides the selection and configuration of the algorithms. We validate these hypotheses using extensive experiments on 7 algorithms, 10 input distributions, up to 262144 cores, and varying input sizes over 9 orders of magnitude. For difficult input distributions, our algorithms are the only ones that work at all. For all but the largest input sizes, we are the first to perform experiments on such large machines at all and our algorithms significantly outperform the ones one would conventionally have considered.
On the complexity of automatic complexity
Venue: arXiv cs.FL 2020
Year: 2020

Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity $A(E)$ of an equivalence relation $E$ on a finite set $S$ of strings. We prove that the problem of determining whether $A(E)$ equals the number $|E|$ of equivalence classes of $E$ is $\mathsf{NP}$-complete. The problem of determining whether $A(E) = |E| + k$ for a fixed $k\ge 1$ is complete for the second level of the Boolean hierarchy for $\mathsf{NP}$, i.e., $\mathsf{BH}_2$-complete. Let $L$ be the language consisting of all strings of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of $L$ by showing that they can be co-context-free but not context-free, i.e., $L$ is $\mathsf{CFL}$-immune, but not $\mathsf{coCFL}$-immune. We show that for each $ε>0$, $L_ε\not\in\mathsf{coCFL}$, where $L_ε$ is the set of all strings whose deterministic automatic complexity $A(x)$ satisfies $A(x)\ge |x|^{1/2-ε}$.
Automatic complexity of shift register sequences
Venue: arXiv cs.FL 2020
Year: 2020

Let $x$ be an $m$-sequence, a maximal length sequence produced by a linear feedback shift register. We show that $x$ has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity $A_N(x)$ is close to maximal: $n/2-A_N(x)=O(\log^2n)$, where $n$ is the length of $x$. In contrast, Hyde has shown $A_N(y)\le n/2+1$ for all sequences $y$ of length $n$.
TweeTime: A Minimally Supervised Method for Recognizing and Normalizing Time Expressions in Twitter
Venue: arXiv cs.IR 2020
Year: 2020

We describe TweeTIME, a temporal tagger for recognizing and normalizing time expressions in Twitter. Most previous work in social media analysis has to rely on temporal resolvers that are designed for well-edited text, and therefore suffer from the reduced performance due to domain mismatch. We present a minimally supervised method that learns from large quantities of unlabeled data and requires no hand-engineered rules or hand-annotated training corpora. TweeTIME achieves 0.68 F1 score on the end-to-end task of resolving date expressions, outperforming a broad range of state-of-the-art systems.
Well-Rounded Lattices: Towards Optimal Coset Codes for Gaussian and Fading Wiretap Channels
Venue: arXiv cs.IT 2020
Year: 2020

The design of lattice coset codes for wiretap channels is considered. Bounds on the eavesdropper's correct decoding probability and information leakage are first revisited. From these bounds, it is explicit that both the information leakage and error probability are controlled by the average flatness factor of the eavesdropper's lattice, which we further interpret geometrically. It is concluded that the minimization of the (average) flatness factor of the eavesdropper's lattice leads to the study of well-rounded lattices, which are shown to be among the optimal in order to achieve these minima. Constructions of some well-rounded lattices are also provided.
Salt Reconstruction in Full Waveform Inversion with a Parametric Level-Set Method
Venue: arXiv cs.CE 2020
Year: 2020

Seismic full-waveform inversion tries to estimate subsurface medium parameters from seismic data. Areas with subsurface salt bodies are of particular interest because they often have hydrocarbon reservoirs on their sides or underneath. Accurate reconstruction of their geometry is a challenge for current techniques. This paper presents a parametric level-set method for the reconstruction of salt-bodies in seismic full-waveform inversion. We split the subsurface model in two parts: a background velocity model and the salt body with known velocity but undetermined shape. The salt geometry is represented by a level-set function that evolves during the inversion. We choose radial basis functions to represent the level-set function, leading to an optimization problem with a modest number of parameters. A common problem with level-set methods is to fine tune the width of the level-set boundary for optimal sensitivity. We propose a robust algorithm that dynamically adapts the width of the level-set boundary to ensure faster convergence. Tests on a suite of idealized salt geometries show that the proposed method is stable against a modest amount of noise. We also extend the method to joint inversion of both the background velocity model and the salt-geometry.
A Theoretical Model for Understanding the Dynamics of Online Social Networks Decay
Venue: arXiv cs.SI 2020
Year: 2020

Online social networks represent a main source of communication and information exchange in today's life. They facilitate exquisitely news sharing, knowledge elicitation, and forming groups of same interests. Researchers in the last two decades studied the growth dynamics of the online social networks extensively questing a clear understanding of the behavior of humans in online social networks that helps in many directions, like engineering better recommendation systems and attracting new members. However, not all of social networks achieved the desired growth, for example, online social networks like MySpace, Orkut, and Friendster are out of service today. In this work, we present a probabilistic theoretical model that captures the dynamics of the social decay due to the inactivity of the members of a social network. The model is proved to have some interesting mathematical properties, namely \textit{submodularity}, which imply achieving the model optimization in a reasonable performance. That means the maximization problem can be approximated within a factor of $(1-1/e)$ and the minimization problem can be achieved in polynomial time.
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Venue: arXiv cs.DS 2020
Year: 2020

We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $Γ$ and a degree bound $Δ$, we study the complexity of #CSP$_Δ(Γ)$, which is the problem of counting satisfying assignments to CSP instances with constraints from $Γ$ and whose variables can appear at most $Δ$ times. Our main result shows that: (i) if every function in $Γ$ is affine, then #CSP$_Δ(Γ)$ is in FP for all $Δ$, (ii) otherwise, if every function in $Γ$ is in a class called IM$_2$, then for all sufficiently large $Δ$, #CSP$_Δ(Γ)$ is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large $Δ$, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP$_Δ(Γ)$, even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.
Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions
Venue: arXiv cs.FL 2020
Year: 2020

Multi-valued partial CFL functions are functions computed along accepting computation paths by one-way nondeterministic pushdown automata, equipped with write-only output tapes, which are allowed to reject an input, in comparison with single-valued partial CFL functions. We give an answer to a fundamental question, raised by Konstantinidis, Santean, and Yu [Act. Inform. 43 (2007) 395-417], of whether all such multi-valued partial CFL functions can be refined by single-valued partial CFL functions. We negatively solve this open question by presenting a special multi-valued partial CFL function as an example function and by proving that no refinement of this particular function becomes a single-valued partial CFL function. This contrasts an early result of Kobayashi [Inform. Control 15 (1969) 95-109] that multi-valued partial NFA functions are always refined by single-valued NFA functions, where NFA functions are computed by one-way nondeterministic finite automata with output tapes. Our example function turns out to be unambiguously 2-valued, and thus we obtain a stronger separation result, in which no refinement of unambiguously 2-valued partial CFL functions can be single-valued. For the proof of this fact, we first introduce a new concept of colored automata having no output tapes but having "colors," which can simulate pushdown automata equipped with constant-space output tapes. We then conduct an extensive combinatorial analysis on the behaviors of transition records of stack contents (called stack histories) of these colored automata.
Target Set Selection in Dense Graph Classes
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so-called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We also show the Target Set Selection problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

We consider a search problem on trees in which the goal is to find an adversarially placed treasure, while relying on local, partial information. Specifically, each node in the tree holds a pointer to one of its neighbors, termed \emph{advice}. A node is faulty with probability $q$. The advice at a non-faulty node points to the neighbor that is closer to the treasure, and the advice at a faulty node points to a uniformly random neighbor. Crucially, the advice is {\em permanent}, in the sense that querying the same node again would yield the same answer. Let $Δ$ denote the maximal degree. Roughly speaking, when considering the expected number of {\em moves}, i.e., edge traversals, we show that a phase transition occurs when the {\em noise parameter} $q$ is about $1/\sqrtΔ$. Below the threshold, there exists an algorithm with expected move complexity $O(D\sqrtΔ)$, where $D$ is the depth of the treasure, whereas above the threshold, every search algorithm has expected number of moves which is both exponential in $D$ and polynomial in the number of nodes~$n$. In contrast, if we require to find the treasure with probability at least $1-δ$, then for every fixed $\varepsilon > 0$, if $q<1/Δ^{\varepsilon}$ then there exists a search strategy that with probability $1-δ$ finds the treasure using $(δ^{-1}D)^{O(\frac 1 \varepsilon)}$ moves. Moreover, we show that $(δ^{-1}D)^{Ω(\frac 1 \varepsilon)}$ moves are necessary. Besides the number of moves, we also study the number of advice {\em queries} required to find the treasure. Roughly speaking, for this complexity, we show similar threshold results to those previously stated, where the parameter $D$ is replaced by $\log n$.
AutoGain: Gain Function Adaptation with Submovement Efficiency Optimization
Venue: arXiv cs.HC 2020
Year: 2020

A well-designed control-to-display gain function can improve pointing performance with indirect pointing devices like trackpads. However, the design of gain functions is challenging and mostly based on trial and error. AutoGain is a novel method to individualize a gain function for indirect pointing devices in contexts where cursor trajectories can be tracked. It gradually improves pointing efficiency by using a novel submovement-level tracking+optimization technique that minimizes aiming error (undershooting/overshooting) for each submovement. We first show that AutoGain can produce, from scratch, gain functions with performance comparable to commercial designs, in less than a half-hour of active use. Second, we demonstrate AutoGain's applicability to emerging input devices (here, a Leap Motion controller) with no reference gain functions. Third, a one-month longitudinal study of normal computer use with AutoGain showed performance improvements from participants' default functions.
Determining Optimal Rates for Communication for Omniscience
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers the communication for omniscience (CO) problem: A set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum-rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum-rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity (CoordSatCap) algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum-rate, so that the problem can be solved more efficiently.
A generalized priority-based model for smartphone screen touches
Venue: arXiv cs.SI 2020
Year: 2020

The distribution of intervals between human actions such as email posts or keyboard strokes demonstrates distinct properties at short vs long time scales. For instance, at long time scales, which are presumably controlled by complex process such as planning and decision making, it has been shown that those inter-event intervals follow a scale-invariant (or power-law) distribution. In contrast, at shorter time-scales - which are governed by different process such as sensorimotor skill - they do not follow the same distribution and little do we know how they relate to the scale-invariant pattern. Here, we analyzed 9 millions intervals between smartphone screen touches of 84 individuals which span several orders of magnitudes (from milliseconds to hours). To capture these intervals, we extend a priority-based generative model to smartphone touching events. At short-time scale, the model is governed by refractory effects, while at longer time scales, the inter-touch intervals are governed by the priority difference between smartphone tasks and other tasks. The flexibility of the model allows to capture inter-individual variations at short and long time scales while its tractability enables efficient model fitting. According to our model, each individual has a specific power-low exponent which is tightly related to the effective refractory time constant suggesting that motor processes which influence the fast actions are related to the higher cognitive processes governing the longer inter-event intervals.
Salient Object Detection with Convex Hull Overlap
Venue: arXiv cs.CV 2020
Year: 2020

Salient object detection plays an important part in a vision system to detect important regions. Convolutional neural network (CNN) based methods directly train their models with large-scale datasets, but what is the crucial feature for saliency is still a problem. In this paper, we establish a novel bottom-up feature named convex hull overlap (CHO), combining with appearance contrast features, to detect salient objects. CHO feature is a kind of enhanced Gestalt cue. Psychologists believe that surroundedness reflects objects overlap relationship. An object which is on the top of the others is attractive. Our method significantly differs from other earlier works in (1) We set up a hand-crafted feature to detect salient object that our model does not need to be trained by large-scale datasets; (2) Previous works only focus on appearance features, while our CHO feature makes up the gap between the spatial object covering and the object's saliency. Our experiments on a large number of public datasets have obtained very positive results.