OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Venue: arXiv cs.DS 2019
Year: 2019

Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found significant applications in solvers for symmetric diagonally dominant (SDD) linear systems. In this work, we provide the first dynamic algorithm for maintaining such trees under edge insertions and deletions to the input graph. Our algorithm has update time $ n^{1/2 + o(1)} $ and the average stretch of the maintained tree is $ n^{o(1)} $, which matches the stretch in the seminal result of Alon et al. Similar to Alon et al., our dynamic low-stretch tree algorithm employs a dynamic hierarchy of low-diameter decompositions (LDDs). As a major building block we use a dynamic LDD that we obtain by adapting the random-shift clustering of Miller et al. [SPAA 2013] to the dynamic setting. The major technical challenge in our approach is to control the propagation of updates within our hierarchy of LDDs: each update to one level of the hierarchy could potentially induce several insertions and deletions to the next level of the hierarchy. We achieve this goal by a sophisticated amortization approach. We believe that the dynamic random-shift clustering might be useful for independent applications. One of these applications is the dynamic spanner problem. By combining the random-shift clustering with the recent spanner construction of Elkin and Neiman [SODA 2017]. We obtain a fully dynamic algorithm for maintaining a spanner of stretch $ 2k - 1 $ and size $ O (n^{1 + 1/k} \log{n}) $ with amortized update time $ O (k \log^2 n) $ for any integer $ 2 \leq k \leq \log n $. Compared to the state-of-the art in this regime [Baswana et al. TALG '12], we improve upon the size of the spanner and the update time by a factor of $ k $.
Modal Dependent Type Theory and Dependent Right Adjoints
Venue: arXiv cs.LO 2019
Year: 2019

In recent years we have seen several new models of dependent type theory extended with some form of modal necessity operator, including nominal type theory, guarded and clocked type theory, and spatial and cohesive type theory. In this paper we study modal dependent type theory: dependent type theory with an operator satisfying (a dependent version of) the K-axiom of modal logic. We investigate both semantics and syntax. For the semantics, we introduce categories with families with a dependent right adjoint (CwDRA) and show that the examples above can be presented as such. Indeed, we show that any finite limit category with an adjunction of endofunctors gives rise to a CwDRA via the local universe construction. For the syntax, we introduce a dependently typed extension of Fitch-style modal lambda-calculus, show that it can be interpreted in any CwDRA, and build a term model. We extend the syntax and semantics with universes.
Joint Communication and Control for Wireless Autonomous Vehicular Platoon Systems
Venue: arXiv cs.IT 2019
Year: 2019

Autonomous vehicular platoons will play an important role in improving on-road safety in tomorrow's smart cities. Vehicles in an autonomous platoon can exploit vehicle-to-vehicle (V2V) communications to collect information, such as velocity and acceleration, from surrounding vehicles so as to maintain the target velocity and inter-vehicle distance. However, due to the dynamic on-vehicle data processing rate and the uncertainty of the wireless channel, V2V communications within a platoon will experience a delay. Such delay can impair the vehicles' ability to stabilize the operation of the platoon. In this paper, a novel framework is proposed to optimize a platoon's operation while jointly consider the delay of the wireless network and the stability of the vehicle's control system. First, stability analysis for the control system is performed and the maximum wireless system delay requirements which can prevent the instability of the control system are derived. Then, delay analysis is conducted to determine the end-to-end delay, including queuing, processing, and transmission delay for the V2V link in the wireless network. Subsequently, using the derived delay, a lower bound and an approximated expression of the reliability for the wireless system, defined as the probability that the wireless system meets the control system's delay needs, are derived. Then, the control parameters are optimized to maximize the derived wireless system reliability. Simulation results corroborate the analytical derivations and study the impact of parameters, such as the platoon size, on the reliability performance of the vehicular platoon. More importantly, the simulation results disclose the benefits of integrating control system and wireless network design while providing guidelines for designing autonomous platoons so as to realize the required wireless network reliability and control system stability.
Synchronization for Diffusion-based Molecular Communication Systems via Faster Molecules
Venue: arXiv cs.ET 2019
Year: 2019

In this paper, we address the symbol synchronization issue in molecular communication via diffusion (MCvD). Symbol synchronization among chemical sensors and nanomachines is one of the critical challenges to manage complex tasks in the nanonetworks with molecular communication (MC). As in diffusion-based MC, most of the molecules arrive at the receptor closer to the start of the symbol duration, the wrong estimation of the start of the symbol interval leads to a high symbol detection error. By utilizing two types of molecules with different diffusion coefficients we propose a synchronization technique for MCvD. Moreover, we evaluate the symbol-error-rate performance under the proposed symbol synchronization scheme for equal and non-equal symbol duration in MCvD systems.
Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We show that a simple local search gives a PTAS for the Feedback Vertex Set (FVS) problem in minor-free graphs. An efficient PTAS in minor-free graphs was known for this problem by Fomin, Lokshtanov, Raman and Sauraubh. However, their algorithm is a combination of many advanced algorithmic tools such as contraction decomposition framework introduced by Demaine and Hajiaghayi, Courcelle's theorem and the Robertson and Seymour decomposition. In stark contrast, our local search algorithm is very simple and easy to implement. It keeps exchanging a constant number of vertices to improve the current solution until a local optimum is reached. Our main contribution is to show that the local optimum only differs the global optimum by $(1+ε)$ factor.
Reversible Video Data Hiding Using Zero QDCT Coefficient-Pairs
Venue: arXiv cs.MM 2019
Year: 2019

H.264/Advanced Video Coding (AVC) is one of the most commonly used video compression standard currently. In this paper, we propose a Reversible Data Hiding (RDH) method based on H.264/AVC videos. In the proposed method, the macroblocks with intra-frame $4\times 4$ prediction modes in intra frames are first selected as embeddable blocks. Then, the last zero Quantized Discrete Cosine Transform (QDCT) coefficients in all $4\times 4$ blocks of the embeddable macroblocks are paired. In the following, a modification mapping rule based on making full use of modification directions are given. Finally, each zero coefficient-pair is changed by combining the given mapping rule with the to-be-embedded information bits. Since most of last QDCT coefficients in all $4\times 4$ blocks are zero and they are located in high frequency area. Therefore, the proposed method can obtain high embedding capacity and low distortion.
Multi-view Hybrid Embedding: A Divide-and-Conquer Approach
Venue: arXiv cs.CV 2019
Year: 2019

We present a novel cross-view classification algorithm where the gallery and probe data come from different views. A popular approach to tackle this problem is the multi-view subspace learning (MvSL) that aims to learn a latent subspace shared by multi-view data. Despite promising results obtained on some applications, the performance of existing methods deteriorates dramatically when the multi-view data is sampled from nonlinear manifolds or suffers from heavy outliers. To circumvent this drawback, motivated by the Divide-and-Conquer strategy, we propose Multi-view Hybrid Embedding (MvHE), a unique method of dividing the problem of cross-view classification into three subproblems and building one model for each subproblem. Specifically, the first model is designed to remove view discrepancy, whereas the second and third models attempt to discover the intrinsic nonlinear structure and to increase discriminability in intra-view and inter-view samples respectively. The kernel extension is conducted to further boost the representation power of MvHE. Extensive experiments are conducted on four benchmark datasets. Our methods demonstrate overwhelming advantages against the state-of-the-art MvSL based cross-view classification approaches in terms of classification accuracy and robustness.
Neural-Davidsonian Semantic Proto-role Labeling
Venue: arXiv cs.CL 2019
Year: 2019

We present a model for semantic proto-role labeling (SPRL) using an adapted bidirectional LSTM encoding strategy that we call "Neural-Davidsonian": predicate-argument structure is represented as pairs of hidden states corresponding to predicate and argument head tokens of the input sequence. We demonstrate: (1) state-of-the-art results in SPRL, and (2) that our network naturally shares parameters between attributes, allowing for learning new attribute types with limited added supervision.
First Impressions: A Survey on Vision-Based Apparent Personality Trait Analysis
Venue: arXiv cs.CV 2019
Year: 2019

Personality analysis has been widely studied in psychology, neuropsychology, and signal processing fields, among others. From the past few years, it also became an attractive research area in visual computing. From the computational point of view, by far speech and text have been the most considered cues of information for analyzing personality. However, recently there has been an increasing interest from the computer vision community in analyzing personality from visual data. Recent computer vision approaches are able to accurately analyze human faces, body postures and behaviors, and use these information to infer apparent personality traits. Because of the overwhelming research interest in this topic, and of the potential impact that this sort of methods could have in society, we present in this paper an up-to-date review of existing vision-based approaches for apparent personality trait recognition. We describe seminal and cutting edge works on the subject, discussing and comparing their distinctive features and limitations. Future venues of research in the field are identified and discussed. Furthermore, aspects on the subjectivity in data labeling/evaluation, as well as current datasets and challenges organized to push the research on the field are reviewed.
Task Planning in Robotics: an Empirical Comparison of PDDL-based and ASP-based Systems
Venue: arXiv cs.AI 2019
Year: 2019

Robots need task planning algorithms to sequence actions toward accomplishing goals that are impossible through individual actions. Off-the-shelf task planners can be used by intelligent robotics practitioners to solve a variety of planning problems. However, many different planners exist, each with different strengths and weaknesses, and there are no general rules for which planner would be best to apply to a given problem. In this article, we empirically compare the performance of state-of-the-art planners that use either the Planning Domain Description Language (PDDL), or Answer Set Programming (ASP) as the underlying action language. PDDL is designed for task planning, and PDDL-based planners are widely used for a variety of planning problems. ASP is designed for knowledge-intensive reasoning, but can also be used for solving task planning problems. Given domain encodings that are as similar as possible, we find that PDDL-based planners perform better on problems with longer solutions, and ASP-based planners are better on tasks with a large number of objects or in which complex reasoning is required to reason about action preconditions and effects. The resulting analysis can inform selection among general purpose planning systems for particular robot task planning domains.
Obtaining Costly Unverifiable Valuations from a Single Agent
Venue: arXiv cs.GT 2019
Year: 2019

We consider the problem of a principal who needs to elicit the true worth of an object she owns from an agent who has a unique ability to compute this information. The correctness of the information cannot be verified by the principal, so it is important to incentivize the agent to report truthfully. Previous works coped with this unverifiability by employing two or more information agents and awarding them according to the correlation between their reports. In this paper we show that even with only one information agent truthful information can be elicited, as long as the object is valuable for the agent too. In particular the paper introduces a mechanism that, under mild realistic assumptions, is proved to elicit the information truthfully, even when computing the information is costly for the agent. Moreover, using this mechanism, the principal obtains the truthful information incurring an arbitrarily small expense beyond whatever unavoidable costs the setting dictates.
Normal edge-colorings of cubic graphs
Venue: arXiv cs.DM 2019
Year: 2019

A normal $k$-edge-coloring of a cubic graph is an edge-coloring with $k$ colors having the additional property that when looking at the set of colors assigned to any edge $e$ and the four edges adjacent it, we have either exactly five distinct colors or exactly three distinct colors. We denote by $χ'_{N}(G)$ the smallest $k$, for which $G$ admits a normal $k$-edge-coloring. Normal $k$-edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving $χ'_{N}(G)\leq 5$ for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture and then, among others, Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with $χ'_{N}(G)=7$. On the other hand, the known best general upper bound for $χ'_{N}(G)$ was $9$. Here, we improve it by proving that $χ'_{N}(G)\leq7$ for any simple cubic graph $G$, which is best possible. We obtain this result by proving the existence of specific no-where zero $\mathbb{Z}_2^2$-flows in $4$-edge-connected graphs.
Adaptive Transmission in Cellular Networks: Fixed-Rate Codes with Power Control vs Physical Layer Rateless Codes
Venue: arXiv cs.IT 2019
Year: 2019

Adaptive transmission schemes are a crucial aspect of the radio design for future wireless networks. The paper studies the performance of two classes of adaptive transmission schemes in a cellular downlink. One class is based on physical layer rateless codes with constant transmit power and the other uses fixed-rate codes in conjunction with power adaptation. Using a simple stochastic geometry model for the cellular downlink, the focus is to compare the adaptivity of fixed-rate codes with power adaptation to that of physical layer rateless codes only. The performance of both rateless and fixed-rate coded adaptive transmission schemes are compared by evaluating the typical user success probability and rate achievable with the two schemes. Based on both the theoretical analysis and simulation results, it is clearly shown that fixed-rate codes require power control to maintain good performance whereas physical layer rateless codes with constant power can still provide robust performance.
On Euclidean $k$-Means Clustering with $α$-Center Proximity
Venue: arXiv cs.DS 2019
Year: 2019

$k$-means clustering is NP-hard in the worst case but previous work has shown efficient algorithms assuming the optimal $k$-means clusters are \emph{stable} under additive or multiplicative perturbation of data. This has two caveats. First, we do not know how to efficiently verify this property of optimal solutions that are NP-hard to compute in the first place. Second, the stability assumptions required for polynomial time $k$-means algorithms are often unreasonable when compared to the ground-truth clusters in real-world data. A consequence of multiplicative perturbation resilience is \emph{center proximity}, that is, every point is closer to the center of its own cluster than the center of any other cluster, by some multiplicative factor $α> 1$. We study the problem of minimizing the Euclidean $k$-means objective only over clusterings that satisfy $α$-center proximity. We give a simple algorithm to find the optimal $α$-center-proximal $k$-means clustering in running time exponential in $k$ and $1/(α- 1)$ but linear in the number of points and the dimension. We define an analogous $α$-center proximity condition for outliers, and give similar algorithmic guarantees for $k$-means with outliers and $α$-center proximity. On the hardness side we show that for any $α' > 1$, there exists an $α\leq α'$, $(α>1)$, and an $\varepsilon_0 > 0$ such that minimizing the $k$-means objective over clusterings that satisfy $α$-center proximity is NP-hard to approximate within a multiplicative $(1+\varepsilon_0)$ factor.
The idemetric property: when most distances are (almost) the same
Venue: arXiv cs.SI 2019
Year: 2019

We introduce the \emph{idemetric} property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We then consider how satisfaction of the idemetric property is relevant to algorithm design. For idemetric graphs we observe, for example, that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. Since we are able to show that Kleinberg's model is idemetric, these results contrast nicely with the well known negative results of Kleinberg concerning efficient decentralised algorithms for finding short paths: for precisely the same model as Kleinberg's negative results hold, we are able to show that very efficient (and decentralised) algorithms exist if one allows for reasonable preprocessing. For deterministic distributed routing algorithms we are also able to obtain results proving that less routing information is required for idemetric graphs than the worst case in order to achieve stretch less than 3 with high probability: while $Ω(n^2)$ routing information is required in the worst case for stretch strictly less than 3 on almost all pairs, for idemetric graphs the total routing information required is $O(nlog(n))$.
k-Nearest Neighbors by Means of Sequence to Sequence Deep Neural Networks and Memory Networks
Venue: arXiv cs.LG 2019
Year: 2019

k-Nearest Neighbors is one of the most fundamental but effective classification models. In this paper, we propose two families of models built on a sequence to sequence model and a memory network model to mimic the k-Nearest Neighbors model, which generate a sequence of labels, a sequence of out-of-sample feature vectors and a final label for classification, and thus they could also function as oversamplers. We also propose 'out-of-core' versions of our models which assume that only a small portion of data can be loaded into memory. Computational experiments show that our models on structured datasets outperform k-Nearest Neighbors, a feed-forward neural network, XGBoost, lightGBM, random forest and a memory network, due to the fact that our models must produce additional output and not just the label. On image and text datasets, the performance of our model is close to many state-of-the-art deep models. As an oversampler on imbalanced datasets, the sequence to sequence kNN model often outperforms Synthetic Minority Over-sampling Technique and Adaptive Synthetic Sampling.
A General Framework for Counterfactual Learning-to-Rank
Venue: arXiv cs.IR 2019
Year: 2019

Implicit feedback (e.g., click, dwell time) is an attractive source of training data for Learning-to-Rank, but its naive use leads to learning results that are distorted by presentation bias. For the special case of optimizing average rank for linear ranking functions, however, the recently developed SVM-PropRank method has shown that counterfactual inference techniques can be used to provably overcome the distorting effect of presentation bias. Going beyond this special case, this paper provides a general and theoretically rigorous framework for counterfactual learning-to-rank that enables unbiased training for a broad class of additive ranking metrics (e.g., Discounted Cumulative Gain (DCG)) as well as a broad class of models (e.g., deep networks). Specifically, we derive a relaxation for propensity-weighted rank-based metrics which is subdifferentiable and thus suitable for gradient-based optimization. We demonstrate the effectiveness of this general approach by instantiating two new learning methods. One is a new type of unbiased SVM that optimizes DCG -- called SVM PropDCG --, and we show how the resulting optimization problem can be solved via the Convex Concave Procedure (CCP). The other is Deep PropDCG, where the ranking function can be an arbitrary deep network. In addition to the theoretical support, we empirically find that SVM PropDCG significantly outperforms existing linear rankers in terms of DCG. Moreover, the ability to train non-linear ranking functions via Deep PropDCG further improves performance.
Low-complexity separable beamformers for massive antenna array systems
Venue: arXiv cs.IT 2019
Year: 2019

Future cellular systems will likely employ massive bi-dimensional arrays to improve performance by large array gain and more accurate spatial filtering, motivating the design of low-complexity signal processing methods. We propose optimising a Kronecker-separable beamforming filter that takes advantage of the bi-dimensional array geometry to reduce computational costs. The Kronecker factors are obtained using two strategies: alternating optimisation, and sub-array minimum mean square error beamforming with Tikhonov regularization. According to the simulation results, the proposed methods are computationally efficient but come with source recovery degradation, which becomes negligible when the sources are sufficiently separated in space.