OpenRaiser/Intern-Atlas huggingface dataset:
Secure Broadcasting Using Independent Secret Keys
Venue: arXiv cs.IT 2018
Year: 2018

The problem of secure broadcasting with independent secret keys is studied. The particular scenario is analyzed in which a common message has to be broadcast to two legitimate receivers, while keeping an external eavesdropper ignorant of it. The transmitter shares independent secret keys of sufficiently high rates with both legitimate receivers, which can be used in different ways: they can be used as one-time pads to encrypt the common message, as fictitious messages for wiretap coding, or as a hybrid of these. In this paper, capacity results are established when the broadcast channels involving the three receivers are degraded. If both legitimate channels are degraded versions of the eavesdropper's channel, it is shown that the one-time pad approach is optimal for several cases, yielding corresponding capacity expressions. Alternatively, the wiretap coding approach is shown to be optimal if the eavesdropper's channel is degraded with respect to both legitimate channels, establishing capacity in this case as well. If the eavesdropper's channel is neither the strongest nor the weakest, an intricate scheme that carefully combines both concepts of one-time pad and wiretap coding with fictitious messages turns out to be capacity-achieving. Finally we also obtain some results for the general non-degraded broadcast channel.
Code-based Key Encapsulation from McEliece's Cryptosystem
Venue: arXiv cs.CR 2018
Year: 2018

In this paper we show that it is possible to extend the framework of Persichetti's code-based framework and create a secure KEM based on the McEliece protocol. This provides greater flexibility in the application of coding theory as a basis for cryptographic purposes.
Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint
Venue: arXiv cs.LG 2018
Year: 2018

Symmetric nonnegative matrix factorization has found abundant applications in various domains by providing a symmetric low-rank decomposition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial constraint, which has recently been proposed for probabilistic clustering. Compared with existing solutions, this algorithm is simple to implement, and has no hyperparameters to be tuned. Building on the recent advances of FW algorithms in nonconvex optimization, we prove an $O(1/\varepsilon^2)$ convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $Θ(n^2)$ on the curvature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demonstrate the effectiveness of our algorithm. As a side contribution, we construct a simple nonsmooth convex problem where the FW algorithm fails to converge to the optimum. This result raises an interesting question about necessary conditions of the success of the FW algorithm on convex problems.
Concept Drift and Anomaly Detection in Graph Streams
Venue: arXiv cs.LG 2018
Year: 2018

Graph representations offer powerful and intuitive ways to describe data in a multitude of application domains. Here, we consider stochastic processes generating graphs and propose a methodology for detecting changes in stationarity of such processes. The methodology is general and considers a process generating attributed graphs with a variable number of vertices/edges, without the need to assume one-to-one correspondence between vertices at different time steps. The methodology acts by embedding every graph of the stream into a vector domain, where a conventional multivariate change detection procedure can be easily applied. We ground the soundness of our proposal by proving several theoretical results. In addition, we provide a specific implementation of the methodology and evaluate its effectiveness on several detection problems involving attributed graphs representing biological molecules and drawings. Experimental results are contrasted with respect to suitable baseline methods, demonstrating the effectiveness of our approach.
Statistical Inferences for Polarity Identification in Natural Language
Venue: arXiv cs.CL 2018
Year: 2018

Information forms the basis for all human behavior, including the ubiquitous decision-making that people constantly perform in their every day lives. It is thus the mission of researchers to understand how humans process information to reach decisions. In order to facilitate this task, this work proposes a novel method of studying the reception of granular expressions in natural language. The approach utilizes LASSO regularization as a statistical tool to extract decisive words from textual content and draw statistical inferences based on the correspondence between the occurrences of words and an exogenous response variable. Accordingly, the method immediately suggests significant implications for social sciences and Information Systems research: everyone can now identify text segments and word choices that are statistically relevant to authors or readers and, based on this knowledge, test hypotheses from behavioral research. We demonstrate the contribution of our method by examining how authors communicate subjective information through narrative materials. This allows us to answer the question of which words to choose when communicating negative information. On the other hand, we show that investors trade not only upon facts in financial disclosures but are distracted by filler words and non-informative language. Practitioners - for example those in the fields of investor communications or marketing - can exploit our insights to enhance their writings based on the true perception of word choice.
A Computer Vision Pipeline for Automated Determination of Cardiac Structure and Function and Detection of Disease by Two-Dimensional Echocardiography
Venue: arXiv cs.CV 2018
Year: 2018

Automated cardiac image interpretation has the potential to transform clinical practice in multiple ways including enabling low-cost serial assessment of cardiac function in the primary care and rural setting. We hypothesized that advances in computer vision could enable building a fully automated, scalable analysis pipeline for echocardiogram (echo) interpretation. Our approach entailed: 1) preprocessing; 2) convolutional neural networks (CNN) for view identification, image segmentation, and phasing of the cardiac cycle; 3) quantification of chamber volumes and left ventricular mass; 4) particle tracking to compute longitudinal strain; and 5) targeted disease detection. CNNs accurately identified views (e.g. 99% for apical 4-chamber) and segmented individual cardiac chambers. Cardiac structure measurements agreed with study report values (e.g. mean absolute deviations (MAD) of 7.7 mL/kg/m2 for left ventricular diastolic volume index, 2918 studies). We computed automated ejection fraction and longitudinal strain measurements (within 2 cohorts), which agreed with commercial software-derived values [for ejection fraction, MAD=5.3%, N=3101 studies; for strain, MAD=1.5% (n=197) and 1.6% (n=110)], and demonstrated applicability to serial monitoring of breast cancer patients for trastuzumab cardiotoxicity. Overall, we found that, compared to manual measurements, automated measurements had superior performance across seven internal consistency metrics with an average increase in the Spearman correlation coefficient of 0.05 (p=0.02). Finally, we developed disease detection algorithms for hypertrophic cardiomyopathy and cardiac amyloidosis, with C-statistics of 0.93 and 0.84, respectively. Our pipeline lays the groundwork for using automated interpretation to support point-of-care handheld cardiac ultrasound and large-scale analysis of the millions of echos archived within healthcare systems.
Optimal Art Gallery Localization is NP-hard
Venue: arXiv cs.CG 2018
Year: 2018

Art Gallery Localization (AGL) is the problem of placing a set $T$ of broadcast towers in a simple polygon $P$ in order for a point to locate itself in the interior. For any point $p \in P$: for each tower $t \in T \cap V(p)$ (where $V(p)$ denotes the visibility polygon of $p$) the point $p$ receives the coordinates of $t$ and the Euclidean distance between $t$ and $p$. From this information $p$ can determine its coordinates. We study the computational complexity of AGL problem. We show that the problem of determining the minimum number of broadcast towers that can localize a point anywhere in a simple polygon $P$ is NP-hard. We show a reduction from Boolean Three Satisfiability problem to our problem and give a proof that the reduction takes polynomial time.
A note on first-order spectra with binary relations
Venue: arXiv cs.LO 2018
Year: 2018

The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $Φ$, there is a sentence $Φ'$ that uses the same number of variables, but only one symmetric binary relation, such that its spectrum is linearly proportional to the spectrum of $Φ$. Moreover, the models of $Φ'$ are all bipartite graphs. As a corollary, we obtain that to settle Asser's conjecture, i.e., whether the class of spectra is closed under complement, it is sufficient to consider only sentences using only three variables whose models are restricted to undirected bipartite graphs.
Lossy Kernels for Connected Dominating Set on Sparse Graphs
Venue: arXiv cs.DS 2018
Year: 2018

For $α> 1$, an $α$-approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance $(I, k)$ of a problem $\mathcal{Q}$ and outputs an instance $(I',k')$ (of a problem $\mathcal{Q}'$) of size bounded by a function of $k$ such that, for every $c\geq 1$, a $c$-approximate solution for the new instance can be turned into a $(c\cdotα)$-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distance-$r$ variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every $α>1$, Connected Dominating Set admits a polynomial-size $α$-approximate (bi-)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on $2$-degenerate graphs and graphs of bounded expansion, unless $\textsf{NP} \subseteq \textsf{coNP/poly}$. We complement our results by the following conditional lower bound. We show that if a class $\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\in\mathbb{N}$ there cannot exist an $α$-approximate bi-kernel for the (Connected) Distance-$r$ Dominating Set problem on $\mathcal{C}$ for any $α>1$ (assuming the Gap Exponential Time Hypothesis).
Path planning for Robotic Mobile Fulfillment Systems
Venue: arXiv cs.AI 2018
Year: 2018

This paper presents a collection of path planning algorithms for real-time movement of multiple robots across a Robotic Mobile Fulfillment System (RMFS). Robots are assigned to move storage units to pickers at working stations instead of requiring pickers to go to the storage area. Path planning algorithms aim to find paths for the robots to fulfill the requests without collisions or deadlocks. The state-of-the-art path planning algorithms, including WHCA*, FAR, BCP, OD&ID and CBS, were adapted to suit path planning in RMFS and integrated within a simulation tool to guide the robots from their starting points to their destinations during the storage and retrieval processes. Ten different layouts with a variety of numbers of robots, floors, pods, stations and the sizes of storage areas were considered in the simulation study. Performance metrics of throughput, path length and search time were monitored. Simulation results demonstrate the best algorithm based on each performance metric.
Unconstrained and Curvature-Constrained Shortest-Path Distances and their Approximation
Venue: arXiv cs.CG 2018
Year: 2018

We study shortest paths and their distances on a subset of a Euclidean space, and their approximation by their equivalents in a neighborhood graph defined on a sample from that subset. In particular, we recover and extend the results of Bernstein et al. (2000). We do the same with curvature-constrained shortest paths and their distances, establishing what we believe are the first approximation bounds for them.
Robust Face Tracking using Multiple Appearance Models and Graph Relational Learning
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the problem of appearance matching across different challenges while doing visual face tracking in real-world scenarios. In this paper, FaceTrack is proposed that utilizes multiple appearance models with its long-term and short-term appearance memory for efficient face tracking. It demonstrates robustness to deformation, in-plane and out-of-plane rotation, scale, distractors and background clutter. It capitalizes on the advantages of the tracking-by-detection, by using a face detector that tackles drastic scale appearance change of a face. The detector also helps to reinitialize FaceTrack during drift. A weighted score-level fusion strategy is proposed to obtain the face tracking output having the highest fusion score by generating candidates around possible face locations. The tracker showcases impressive performance when initiated automatically by outperforming many state-of-the-art trackers, except Struck by a very minute margin: 0.001 in precision and 0.017 in success respectively.
Agglomerative Clustering of Growing Squares
Venue: arXiv cs.DS 2018
Year: 2018

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(nα(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms.
Penalizing Unfairness in Binary Classification
Venue: arXiv cs.LG 2018
Year: 2018

We present a new approach for mitigating unfairness in learned classifiers. In particular, we focus on binary classification tasks over individuals from two populations, where, as our criterion for fairness, we wish to achieve similar false positive rates in both populations, and similar false negative rates in both populations. As a proof of concept, we implement our approach and empirically evaluate its ability to achieve both fairness and accuracy, using datasets from the fields of criminal risk assessment, credit, lending, and college admissions.
Simultaneous Consecutive Ones Submatrix and Editing Problems : Classical Complexity \& Fixed-Parameter Tractable Results
Venue: arXiv cs.DS 2018
Year: 2018

A binary matrix $M$ has the consecutive ones property ($C1P$) for rows (resp. columns) if there is a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If $M$ has the $C1P$ for rows and columns, then $M$ is said to have the simultaneous consecutive ones property ($SC1P$). In this article, we consider the classical complexity and fixed-parameter tractability of $(a)$ Simultaneous Consecutive Ones Submatrix ($SC1S$) and $(b)$ Simultaneous Consecutive Ones Editing ($SC1E$) [Oswald et al., Theoretical Comp. Sci. 410(21-23):1986-1992, \hyperref[references]{2009}] problems. We show that the decision versions of $SC1S$ and $SC1E$ problems are NP-complete. We consider the parameterized versions of $SC1S$ and $SC1E$ problems with $d$, being the solution size, as the parameter. Given a binary matrix $M$ and a positive integer $d$, $d$-$SC1S$-$R$, $d$-$SC1S$-$C$, and $d$-$SC1S$-$RC$ problems decide whether there exists a set of rows, columns, and rows as well as columns, respectively, of size at most $d$, whose deletion results in a matrix with the $SC1P$. The $d$-$SC1P$-$0E$, $d$-$SC1P$-$1E$, and $d$-$SC1P$-$01E$ problems decide whether there exists a set of $0$-entries, $1$-entries, and $0$-entries as well as $1$-entries, respectively, of size at most $d$, whose flipping results in a matrix with the \vspace{0.095 in} $SC1P$.
A Channel-Based Perspective on Conjugate Priors
Venue: arXiv cs.LO 2018
Year: 2018

A desired closure property in Bayesian probability is that an updated posterior distribution be in the same class of distributions --- say Gaussians --- as the prior distribution. When the updating takes place via a statistical model, one calls the class of prior distributions the `conjugate priors' of the model. This paper gives (1) an abstract formulation of this notion of conjugate prior, using channels, in a graphical language, (2) a simple abstract proof that such conjugate priors yield Bayesian inversions, and (3) a logical description of conjugate priors that highlights the required closure of the priors under updating. The theory is illustrated with several standard examples, also covering multiple updating.
A new algorithm for fast generalized DFTs
Venue: arXiv cs.DS 2018
Year: 2018

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups $G$. The new algorithm uses $O(|G|^{ω/2 + o(1)})$ operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here $ω$ is the exponent of matrix multiplication, so the exponent $ω/2$ is optimal if $ω= 2$. Previously, "exponent one" algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known (even under the assumption $ω= 2$) for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for $SL_2(F_q)$ had exponent $4/3$ despite being the focus of significant effort. We unconditionally achieve exponent at most $1.19$ for this group, and exponent one if $ω= 2$. Our algorithm also yields an improved exponent for computing the generalized DFT over general finite groups $G$, which beats the longstanding previous best upper bound, for any $ω$. In particular, assuming $ω= 2$, we achieve exponent $\sqrt{2}$, while the previous best was $3/2$.
What happens when software developers are (un)happy
Venue: arXiv cs.SE 2018
Year: 2018

The growing literature on affect among software developers mostly reports on the linkage between happiness, software quality, and developer productivity. Understanding happiness and unhappiness in all its components -- positive and negative emotions and moods -- is an attractive and important endeavor. Scholars in industrial and organizational psychology have suggested that understanding happiness and unhappiness could lead to cost-effective ways of enhancing working conditions, job performance, and to limiting the occurrence of psychological disorders. Our comprehension of the consequences of (un)happiness among developers is still too shallow, being mainly expressed in terms of development productivity and software quality. In this paper, we study what happens when developers are happy and unhappy while developing software. Qualitative data analysis of responses given by 317 questionnaire participants identified 42 consequences of unhappiness and 32 of happiness. We found consequences of happiness and unhappiness that are beneficial and detrimental for developers' mental well-being, the software development process, and the produced artifacts. Our classification scheme, available as open data enables new happiness research opportunities of cause-effect type, and it can act as a guideline for practitioners for identifying damaging effects of unhappiness and for fostering happiness on the job.
An In-Depth Analysis of Visual Tracking with Siamese Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

This survey presents a deep analysis of the learning and inference capabilities in nine popular trackers. It is neither intended to study the whole literature nor is it an attempt to review all kinds of neural networks proposed for visual tracking. We focus instead on Siamese neural networks which are a promising starting point for studying the challenging problem of tracking. These networks integrate efficiently feature learning and the temporal matching and have so far shown state-of-the-art performance. In particular, the branches of Siamese networks, their layers connecting these branches, specific aspects of training and the embedding of these networks into the tracker are highlighted. Quantitative results from existing papers are compared with the conclusion that the current evaluation methodology shows problems with the reproducibility and the comparability of results. The paper proposes a novel Lisp-like formalism for a better comparison of trackers. This assumes a certain functional design and functional decomposition of trackers. The paper tries to give foundation for tracker design by a formulation of the problem based on the theory of machine learning and by the interpretation of a tracker as a decision function. The work concludes with promising lines of research and suggests future work.
Symmetries of weight enumerators and applications to Reed-Muller codes
Venue: arXiv cs.IT 2018
Year: 2018

Gleason's 1970 theorem on weight enumerators of self-dual codes has played a crucial role for research in coding theory during the last four decades. Plenty of generalizations have been proved but, to our knowledge, they are all based on the symmetries given by MacWilliams' identities. This paper is intended to be a first step towards a more general investigation of symmetries of weight enumerators. We list the possible groups of symmetries, dealing both with the finite and infinite case, we develop a new algorithm to compute the group of symmetries of a given weight enumerator and apply these methods to the family of Reed-Muller codes, giving, in the binary case, an analogue of Gleason's theorem for all parameters.
Vision and Challenges for Knowledge Centric Networking (KCN)
Venue: arXiv cs.NI 2018
Year: 2018

In the creation of a smart future information society, Internet of Things (IoT) and Content Centric Networking (CCN) break two key barriers for both the front-end sensing and back-end networking. However, we still observe the missing piece of the research that dominates the current networking traffic control and system management, e.g., lacking of the knowledge penetrated into both sensing and networking to glue them holistically. In this paper, we envision to leverage emerging machine learning or deep learning techniques to create aspects of knowledge for facilitating the designs. In particular, we can extract knowledge from collected data to facilitate reduced data volume, enhanced system intelligence and interactivity, improved service quality, communication with better controllability and lower cost. We name such a knowledge-oriented traffic control and networking management paradigm as the Knowledge Centric Networking (KCN). This paper presents KCN rationale, KCN benefits, related works and research opportunities.