# Computer Science (cs)

• Aug 22 2017 quant-ph cs.DS arXiv:1708.06002v1
We consider the problem of quantum state certification, where one is given $n$ copies of an unknown $d$-dimensional quantum mixed state $\rho$, and one wants to test whether $\rho$ is equal to some known mixed state $\sigma$ or else is $\epsilon$-far from $\sigma$. The goal is to use notably fewer copies than the $\Omega(d^2)$ needed for full tomography on $\rho$ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using $n = O(d/\epsilon)$ copies, and one with respect to trace distance using $n = O(d/\epsilon^2)$ copies. The latter algorithm also applies when $\sigma$ is unknown as well. These copy complexities are optimal up to constant factors.
• A pure multipartite quantum state is called absolutely maximally entangled (AME), if all reductions obtained by tracing out at least half of its parties are maximally mixed. However, the existence of such states is in many cases unclear. With the help of the weight enumerator machinery known from quantum error correcting codes and the generalized shadow inequalities, we obtain new bounds on the existence of AME states in higher dimensions. To complete the treatment on the weight enumerator machinery, the quantum MacWilliams identity is derived in the Bloch representation.
• We give an adaptive algorithm which tests whether an unknown Boolean function $f\colon \{0, 1\}^n \to\{0, 1\}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-increasing, or $\epsilon$-far from unate with one-sided error using $\widetilde{O}(n^{3/4}/\epsilon^2)$ queries. This improves on the best adaptive $O(n/\epsilon)$-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri when $1/\epsilon \ll n^{1/4}$. Combined with the $\widetilde{\Omega}(n)$-query lower bound for non-adaptive algorithms with one-sided error of [CWX17, BCPRS17], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.
• To efficiently establish training databases for machine learning methods, collaborative and crowdsourcing platforms have been investigated to collectively tackle the annotation effort. However, when this concept is ported to the medical imaging domain, reading expertise will have a direct impact on the annotation accuracy. In this study, we examine the impact of expertise and the amount of available annotations on the accuracy outcome of a liver segmentation problem in an abdominal computed tomography (CT) image database. In controlled experiments, we study this impact for different types of weak annotations. To address the decrease in accuracy associated with lower expertise, we propose a method for outlier correction making use of a weakly labelled atlas. Using this approach, we demonstrate that weak annotations subject to high error rates can achieve a similarly high accuracy as state-of-the-art multi-atlas segmentation approaches relying on a large amount of expert manual segmentations. Annotations of this nature can realistically be obtained from a non-expert crowd and can potentially enable crowdsourcing of weak annotation tasks for medical image analysis.
• Aug 22 2017 cs.NE arXiv:1708.06008v1
We review Boltzmann machines and energy-based models. A Boltzmann machine defines a probability distribution over binary-valued patterns. One can learn parameters of a Boltzmann machine via gradient based approaches in a way that log likelihood of data is increased. The gradient and Laplacian of a Boltzmann machine admit beautiful mathematical representations, although computing them is in general intractable. This intractability motivates approximate methods, including Gibbs sampler and contrastive divergence, and tractable alternatives, namely energy-based models.
• Training large vocabulary Neural Network Language Models (NNLMs) is a difficult task due to the explicit requirement of the output layer normalization, which typically involves the evaluation of the full softmax function over the complete vocabulary. This paper proposes a Batch Noise Contrastive Estimation (B-NCE) approach to alleviate this problem. This is achieved by reducing the vocabulary, at each time step, to the target words in the batch and then replacing the softmax by the noise contrastive estimation approach, where these words play the role of targets and noise samples at the same time. In doing so, the proposed approach can be fully formulated and implemented using optimal dense matrix operations. Applying B-NCE to train different NNLMs on the Large Text Compression Benchmark (LTCB) and the One Billion Word Benchmark (OBWB) shows a significant reduction of the training time with no noticeable degradation of the models performance. This paper also presents a new baseline comparative study of different standard NNLMs on the large OBWB on a single Titan-X GPU.
• We present a novel end-to-end trainable neural network model for task-oriented dialog systems. The model is able to track dialog state, issue API calls to knowledge base (KB), and incorporate structured KB query results into system responses to successfully complete task-oriented dialogs. The proposed model produces well-structured system responses by jointly learning belief tracking and KB result processing conditioning on the dialog history. We evaluate the model in a restaurant search domain using a dataset that is converted from the second Dialog State Tracking Challenge (DSTC2) corpus. Experiment results show that the proposed model can robustly track dialog state given the dialog history. Moreover, our model demonstrates promising results in producing appropriate system responses, outperforming prior end-to-end trainable neural network models using per-response accuracy evaluation metrics.
• In recent years, Unmanned Aerial Vehicle (UAV) technology has been introduced into the mining industry to conduct terrain surveying. This work investigates the application of UAVs with artificial lighting for measurement of rock fragmentation under poor lighting conditions, representing night shifts in surface mines or working conditions in underground mines. The study relies on indoor and outdoor experiments for rock fragmentation analysis using a quadrotor UAV. Comparison of the rock size distributions in both cases show that adequate artificial lighting enables similar accuracy to ideal lighting conditions.
• We propose a simple, yet powerful regularization technique that can be used to significantly improve both the pairwise and triplet losses in learning local feature descriptors. The idea is that in order to fully utilize the expressive power of the descriptor space, good local feature descriptors should be sufficiently "spread-out" over the space. In this work, we propose a regularization term to maximize the spread in feature descriptor inspired by the property of uniform distribution. We show that the proposed regularization with triplet loss outperforms existing Euclidean distance based descriptor learning techniques by a large margin. As an extension, the proposed regularization technique can also be used to improve image-level deep feature embedding.
• Optical communication systems represent the backbone of modern communication networks. Since their deployment, different fiber technologies have been used to deal with optical fiber impairments such as dispersion-shifted fibers and dispersion-compensation fibers. In recent years, thanks to the introduction of coherent detection based systems, fiber impairments can be mitigated using digital signal processing (DSP) algorithms. Coherent systems are used in the current 100 Gbps wavelength-division multiplexing (WDM) standard technology. They allow the increase of spectral efficiency by using multi-level modulation formats, and are combined with DSP techniques to combat the linear fiber distortions. In addition to linear impairments, the next generation 400 Gbps/1 Tbps WDM systems are also more affected by the fiber nonlinearity due to the Kerr effect. At high input power, the fiber nonlinear effects become more important and their compensation is required to improve the transmission performance. Several approaches have been proposed to deal with the fiber nonlinearity. In this paper, after a brief description of the Kerr-induced nonlinear effects, a survey on the fiber nonlinearity compensation (NLC) techniques is provided. We focus on the well-known NLC techniques and discuss their performance, as well as their implementation and complexity. An extension of the inter-subcarrier nonlinear interference canceler approach is also proposed. A performance evaluation of the well-known NLC techniques and the proposed approach is provided in the context of Nyquist and super-Nyquist superchannel systems.
• In this paper we present a translation from the quantum programming language Quipper to the QPMC model checker, with the main aim of verifying Quipper programs. Quipper is an embedded functional programming language for quantum computation. It is above all a circuit description language, for this reason it uses the vector state formalism and its main purpose is to make circuit implementation easy providing high level operations for circuit manipulation. Quipper provides both an high-level circuit building interface and a simulator. QPMC is a model checker for quantum protocols based on the density matrix formalism. QPMC extends the probabilistic model checker IscasMC allowing to formally verify properties specified in the temporal logic QCTL on Quantum Markov Chains. We implemented and tested our translation on several quantum algorithms, including Grover's quantum search.
• Manual annotations are a prerequisite for many applications of machine learning. However, weaknesses in the annotation process itself are easy to overlook. In particular, scholars often choose what information to give to annotators without examining these decisions empirically. For subjective tasks such as sentiment analysis, sarcasm, and stance detection, such choices can impact results. Here, for the task of political stance detection on Twitter, we show that providing too little context can result in noisy and uncertain annotations, whereas providing too strong a context may cause it to outweigh other signals. To characterize and reduce these biases, we develop ConStance, a general model for reasoning about annotations across information conditions. Given conflicting labels produced by multiple annotators seeing the same instances with different contexts, ConStance simultaneously estimates gold standard labels and also learns a classifier for new instances. We show that the classifier learned by ConStance outperforms a variety of baselines at predicting political stance, while the model's interpretable parameters shed light on the effects of each context.
• Mobile crowdsensing allows a large number of mobile devices to measure phenomena of common interests and form a body of knowledge about natural and social environments. In order to get location annotations for indoor mobile crowdsensing, reference tags are usually deployed which are susceptible to tampering and compromises by attackers. In this work, we consider three types of location-related attacks including tag forgery, tag misplacement, and tag removal. Different detection algorithms are proposed to deal with these attacks. First, we introduce location-dependent fingerprints as supplementary information for better location identification. A truth discovery algorithm is then proposed to detect falsified data. Moreover, visiting patterns are utilized for the detection of tag misplacement and removal. Experiments on both crowdsensed and emulated dataset show that the proposed algorithms can detect all three types of attacks with high accuracy.
• Networks are models representing relationships between entities. Often these relationships are explicitly given, or we must learn a representation which generalizes and predicts observed behavior in underlying individual data (e.g. attributes or labels). Whether given or inferred, choosing the best representation affects subsequent tasks and questions on the network. This work focuses on model selection to evaluate network representations from data, focusing on fundamental predictive tasks on networks. We present a modular methodology using general, interpretable network models, task neighborhood functions found across domains, and several criteria for robust model selection. We demonstrate our methodology on three online user activity datasets and show that network model selection for the appropriate network task vs. an alternate task increases performance by an order of magnitude in our experiments.
• Depth estimation from stereo images remains a challenge even though studied for decades. The KITTI benchmark shows that the state-of-the-art solutions offer accurate depth estimation, but are still computationally complex and often require a GPU or FPGA implementation. In this paper we aim at increasing the accuracy of depth map estimation and reducing the computational complexity by using information from previous frames. We propose to transform the disparity map of the previous frame into the current frame, relying on the estimated ego-motion, and use this map as the prediction for the Kalman filter in the disparity space. Then, we update the predicted disparity map using the newly matched one. This way we reduce disparity search space and flickering between consecutive frames, thus increasing the computational efficiency of the algorithm. In the end, we validate the proposed approach on real-world data from the KITTI benchmark suite and show that the proposed algorithm yields more accurate results, while at the same time reducing the disparity search space.
• This paper proposes a combination of a hybrid CPU--GPU and a pure GPU software implementation of a direct algorithm for solving shifted linear systems $(A - \sigma I)X = B$ with large number of complex shifts $\sigma$ and multiple right-hand sides. Such problems often appear e.g. in control theory when evaluating the transfer function, or as a part of an algorithm performing interpolatory model reduction, as well as when computing pseudospectra and structured pseudospectra, or solving large linear systems of ordinary differential equations. The proposed algorithm first jointly reduces the general full $n\times n$ matrix $A$ and the $n\times m$ full right-hand side matrix $B$ to the controller Hessenberg canonical form that facilitates efficient solution: $A$ is transformed to a so-called $m$-Hessenberg form and $B$ is made upper-triangular. This is implemented as blocked highly parallel CPU--GPU hybrid algorithm; individual blocks are reduced by the CPU, and the necessary updates of the rest of the matrix are split among the cores of the CPU and the GPU. To enhance parallelization, the reduction and the updates are overlapped. In the next phase, the reduced $m$-Hessenberg--triangular systems are solved entirely on the GPU, with shifts divided into batches. The benefits of such load distribution are demonstrated by numerical experiments. In particular, we show that our proposed implementation provides an excellent basis for efficient implementations of computational methods in systems and control theory, from evaluation of transfer function to the interpolatory model reduction.
• The nursing literature shows that cultural competence is an important requirement for effective healthcare. We claim that personal assistive robots should likewise be culturally competent, that is, they should be aware of general cultural characteristics and of the different forms they take in different individuals, and take these into account while perceiving, reasoning, and acting. The CARESSES project is an Europe-Japan collaborative effort that aims at designing, developing and evaluating culturally competent assistive robots. These robots will be able to adapt the way they behave, speak and interact to the cultural identity of the person they assist. This paper describes the approach taken in the CARESSES project, its initial steps, and its future plans.
• Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with $\Delta+1$ colors, where $\Delta$ denotes the maximum degree. Using $\Delta+1$ colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned. We present simple randomized distributed algorithms that, with high probability, color any $n$-node $\alpha$-arboricity graph: - using $(2+\varepsilon)\cdot \alpha$ colors, for constant $\varepsilon>0$, in $O(\log n)$ rounds, if $\alpha=\tilde{\Omega}(\log n)$, or - using $O(\alpha \log \alpha )$ colors, in $O(\log n)$ rounds, or - using $O(\alpha)$ colors, in $O(\log n \cdot \min\{\log\log n,\; \log \alpha\})$ rounds. These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with $\Theta(\alpha)$ colors, or even poly$(\alpha)$ colors, requires $\Omega(\log_{\alpha} n)$ rounds. The previously best-known $O(\log n)$-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses $\Theta(\alpha ^2)$ colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.
• In this paper, we address the problem of controlling the workspace of a 3-DoF mobile robot. This problem arises due to the emerging coexistence between humans and robots resulting in a shared space. In such an environment, robots should navigate in a human-acceptable way according to the users' demands. For this purpose, we propose a method that gives a non-expert user the possibility to intuitively define virtual borders by means of a laser pointer. In detail, we contribute a method and implementation based on a previously developed framework using a laser pointer as human-robot interface to change the robot's navigational behavior. Furthermore, we extend the framework to increase the flexibility by considering different types of virtual borders, i.e. polygons and curves separating an area. We qualitatively and quantitatively evaluated our method concerning correctness, accuracy and teaching effort. The experimental results revealed a high accuracy and low teaching effort while correctly incorporating the virtual borders into the robot's navigational map.
• We propose a novel mode of operation for Amplify-and-Forward relays in which the spectra of the relay input and output signals partially overlap. This partial-duplex relaying mode encompasses half-duplex and full-duplex as particular cases. By viewing the partial-duplex relay as a bandwidth-preserving Linear Periodic Time-Varying system, an analysis of the spectral efficiency in the presence of self-interference is developed. In contrast with previous works, self-interference is regarded as a useful information-bearing component rather than simply assimilated to noise. This approach reveals that previous results regarding the impact of self-interference on (full-duplex) relay performance are overly pessimistic. Based on a frequency-domain interpretation of the effect of self-interference, a number of suboptimal decoding architectures at the destination node are also discussed. It is found that the partial-duplex relaying mode may provide an attractive tradeoff between spectral efficiency and receiver complexity.
• Word embeddings have been found to capture a surprisingly rich amount of syntactic and semantic knowledge. However, it is not yet sufficiently well-understood how the relational knowledge that is implicitly encoded in word embeddings can be extracted in a reliable way. In this paper, we propose two probabilistic models to address this issue. The first model is based on the common relations-as-translations view, but is cast in a probabilistic setting. Our second model is based on the much weaker assumption that there is a linear relationship between the vector representations of related words. Compared to existing approaches, our models lead to more accurate predictions, and they are more explicit about what can and cannot be extracted from the word embedding.
• In this series of notes, we try to model neural networks as as discretizations of continuous flows on the space of data, which can be called flow model. The idea comes from an observation of their similarity in mathematical structures. This conceptual analogy has not been proven useful yet, but it seems interesting to explore. In this part, we start with a linear transport equation (with nonlinear transport velocity field) and obtain a class of residual type neural networks. If the transport velocity field has a special form, the obtained network is found similar to the original ResNet. This neural network can be regarded as a discretization of the continuous flow defined by the transport flow. In the end, a summary of the correspondence between neural networks and transport equations is presented, followed by some general discussions.
• This paper presents GRAPHR, the first ReRAM-based graph processing accelerator. GRAPHR follows the principle of near-data processing but explores the opportunity of per-forming massive parallel operations with low hardware and energy cost. Compared to recent works in applying ReRAM to more regular neural computations, we are faced with several challenges: 1) The graph data are stored in the com-pressed format, instead of matrix forms, making it impossible to perform direct in-situ computations in memory; 2) It is less intuitive to map various graph algorithms to ReRAM with hardware constrains; 3) Coordinating data movements among ReRAM crossbars and memory to achieve high throughput. GRAPHR is a novel accelerator architecture consisting of two major components: memory ReRAM and graph engine (GE). The core graph computations are performed in sparse matrix format in GEs (ReRAM crossbars), which perform efficient matrix-vector multiplications. The vector/matrix-based graph computation is not new, but ReRAM offers the unique opportunity to realize the massive parallelism with unprecedented energy efficiency and low hardware cost. Due to the same cost/performance tradeoff, with ReRAM, the gain of performing parallel operations overshadows the wastes due to sparsity in matrix view within a small subgraph. Moreover, it naturally enables near data processing with reduced data movements. The experiment results show that GRAPHR achieves a16.01x (up to132.67x) speedup and an33.82x energy saving on geometric mean compared to a CPU baseline system.
• The potential benefit of open access (OA) in relation to citation impact has been discussed in the literature in depth. The methodology used to test the OA citation advantage includes comparing OA vs. non-OA journal impact factors and citations of OA versus non-OA articles published in the same non-OA journals. However, one problem with many studies is that they are small -restricted to a discipline or set of journals-. Moreover, conclusions are not entirely consistent among research areas and 'early view' and 'selection bias' have been suggested as possible explications. In the present paper, an analysis of gold OA from across all areas of research -the 27 subject areas of the Scopus database- is realized. As a novel contribution, this paper takes a journal-level approach to assessing the OA citation advantage, whereas many others take a paper-level approach. Data were obtained from Scimago Lab, sorted using Scopus database, and tagged as OA/non-OA using the DOAJ list. Jointly with the OA citation advantage, the OA prevalence as well as the differences between access types (OA vs. non-OA) in production and referencing are tested. A total of 3,737 OA journals (16.8%) and 18,485 non-OA journals (83.2%) published in 2015 are considered. As the main conclusion, there is no generalizable gold OA citation advantage at journal level.
• This paper provides an initial investigation on the application of convolutional neural networks (CNNs) for fingerprint-based positioning using measured massive MIMO channels. When represented in appropriate domains, massive MIMO channels have a sparse structure which can be efficiently learned by CNNs for positioning purposes. We evaluate the positioning accuracy of state-of-the-art CNNs with channel fingerprints generated from a channel model with a rich clustered structure: the COST 2100 channel model. We find that moderately deep CNNs can achieve fractional-wavelength positioning accuracies, provided that an enough representative data set is available for training.
• Given an integer base b>1, a set of integers is represented in base b by a language over 0,1,...,b-1. The set is said to be b-recognisable if its representation is a regular language. It is known that ultimately periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a b-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed in 1986 that this problem is decidable. Leroux used in 2005 the convention to write integers with the least significant digit first (LSDF), and designed a quadratic algorithm to solve a more general problem. We use here LSDF convention as well and give a structural description of the minimal automata that accept periodic sets of integers. We then show that it can be verified in linear time if a given minimal automaton meets this description. This yields a O(bn log(n)) procedure to decide whether a general deterministic automaton accepts an ultimately periodic set of numbers.
• Human action recognition has been one of the most active fields of research in computer vision for last years. Two dimensional action recognition methods are facing serious challenges such as occlusion and missing the third dimension of data. Development of depth sensors has made it feasible to track positions of human body joints over time. This paper proposes a novel method of action recognition which uses temporal 3D skeletal Kinect data. This method introduces the definition of body states and then every action is modeled as a sequence of these states. The learning stage uses Fisher Linear Discriminant Analysis (LDA) to construct discriminant feature space for discriminating the body states. Moreover, this paper suggests the use of the Mahalonobis distance as an appropriate distance metric for the classification of the states of involuntary actions. Hidden Markov Model (HMM) is then used to model the temporal transition between the body states in each action. According to the results, this method significantly outperforms other popular methods, with recognition rate of 88.64% for eight different actions and up to 96.18% for classifying fall actions.
• The 15th International Conference on Automata and Formal Languages (AFL 2017) was held in Debrecen, Hungary, from September 4 to 6, 2017. The conference was organized by the Faculty of Informatics of the University of Debrecen and the Faculty of Informatics of the Eötvös Loránd University of Budapest. Topics of interest covered all aspects of automata and formal languages, including theory and applications.
• Feedforward neural networks have wide applicability in various disciplines of science due to their universal approximation property. Some authors have shown that single hidden layer feedforward neural networks (SLFNs) with fixed weights still possess the universal approximation property provided that approximated functions are univariate. But this phenomenon does not lay any restrictions on the number of neurons in the hidden layer. The more this number, the more the probability of the considered network to give precise results. In this note, we constructively prove that SLFNs with the fixed weight $1$ and two neurons in the hidden layer can approximate any continuous function on a compact subset of the real line. The applicability of this result is demonstrated in various numerical examples. Finally, we show that SLFNs with fixed weights cannot approximate all continuous multivariate functions.
• The goal of an algorithm substitution attack (ASA), also called a subversion attack (SA), is to replace an honest implementation of a cryptographic tool by a subverted one which allows to leak private information while generating output indistinguishable from the honest output. Bellare, Paterson, and Rogaway provided at CRYPTO'14 a formal security model to capture this kind of attacks and constructed practically implementable ASAs against a large class of symmetric encryption schemes. At CCS'15, Ateniese, Magri, and Venturi extended this model to allow the attackers to work in a fully-adaptive and continuous fashion and proposed subversion attacks against digital signature schemes. Both papers also showed the impossibility of ASAs in cases where the cryptographic tools are deterministic. Also at CCS'15, Bellare, Jaeger, and Kane strengthened the original model and proposed a universal ASA against sufficiently random encryption schemes. In this paper we analyze ASAs from the perspective of steganography - the well known concept of hiding the presence of secret messages in legal communications. While a close connection between ASAs and steganography is known, this lacks a rigorous treatment. We consider the common computational model for secret-key steganography and prove that successful ASAs correspond to secure stegosystems on certain channels and vice versa. This formal proof allows us to conclude that ASAs are stegosystems and to "rediscover" several results concerning ASAs known in the steganographic literature.
• Automated and accurate segmentation of cystoid structures in Optical Coherence Tomography (OCT) is of interest in the early detection of retinal diseases. It is, however, a challenging task. We propose a novel method for localizing cysts in 3D OCT volumes. The proposed work is biologically inspired and based on selective enhancement of the cysts, by inducing motion to a given OCT slice. A Convolutional Neural Network (CNN) is designed to learn a mapping function that combines the result of multiple such motions to produce a probability map for cyst locations in a given slice. The final segmentation of cysts is obtained via simple clustering of the detected cyst locations. The proposed method is evaluated on two public datasets and one private dataset. The public datasets include the one released for the OPTIMA Cyst segmentation challenge (OCSC) in MICCAI 2015 and the DME dataset. After training on the OCSC train set, the method achieves a mean Dice Coefficient (DC) of 0.71 on the OCSC test set. The robustness of the algorithm was examined by cross-validation on the DME and AEI (private) datasets and a mean DC values obtained were 0.69 and 0.79, respectively. Overall, the proposed system outperforms all benchmarks. These results underscore the strengths of the proposed method in handling variations in both data acquisition protocols and scanners.
• We prove that every 1-planar graph G has a z-parallel visibility representation, i.e., a 3D visibility representation in which the vertices are isothetic disjoint rectangles parallel to the xy-plane, and the edges are unobstructed z-parallel visibilities between pairs of rectangles. In addition, the constructed representation is such that there is a plane that intersects all the rectangles, and this intersection defines a bar 1-visibility representation of G.
• The paper describes experiments on estimating emotion intensity in tweets using a generalized regressor system. The system combines lexical, syntactic and pre-trained word embedding features, trains them on general regressors and finally combines the best performing models to create an ensemble. The proposed system stood 3rd out of 22 systems in the leaderboard of WASSA-2017 Shared Task on Emotion Intensity.
• We present an algorithm that ensures in finite time the gathering of two robots in the non-rigid ASYNC model. To circumvent established impossibility results, we assume robots are equipped with 2-colors lights and are able to measure distances between one another. Aside from its light, a robot has no memory of its past actions, and its protocol is deterministic. Since, in the same model, gathering is impossible when lights have a single color, our solution is optimal with respect to the number of used colors.
• Aug 22 2017 cs.FL math.GR arXiv:1708.06173v1
We prove that if a group generated by a bireversible Mealy automaton contains an element of infinite order, its growth blows up and is necessarily exponential. As a direct consequence, Z cannot be generated by a bireversible Mealy automaton.
• The memory-type control charts, such as EWMA and CUSUM, are powerful tools for detecting small quality changes in univariate and multivariate processes. Many papers on economic design of these control charts use the formula proposed by Lorenzen and Vance (1986) [Lorenzen, T. J., & Vance, L. C. (1986). The economic design of control charts: A unified approach. Technometrics, 28(1), 3-10, DOI: 10.2307/1269598]. This paper shows that this formula is not correct for memory-type control charts and its values can significantly deviate from the original values even if the ARL values used in this formula are accurately computed. Consequently, the use of this formula can result in charts that are not economically optimal. The formula is corrected for memory-type control charts, but unfortunately the modified formula is not a helpful tool from a computational perspective. We show that simulation-based optimization is a possible alternative method.
• The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a kernel. The kernel can then be solved quickly using exact or heuristic algorithms - or by repeatedly kernelizing recursively in the branch-and-reduce paradigm. It is of critical importance for these algorithms that kernelization is fast and returns a small kernel. Current algorithms are either slow but produce a small kernel, or fast and give a large kernel. We attempt to accomplish both of these goals simultaneously, by giving an efficient parallel kernelization algorithm based on graph partitioning and parallel bipartite maximum matching. We combine our parallelization techniques with two techniques to accelerate kernelization further: dependency checking that prunes reductions that cannot be applied, and reduction tracking that allows us to stop kernelization when reductions become less fruitful. Our algorithm produces kernels that are orders of magnitude smaller than the fastest kernelization methods, while having a similar execution time. Furthermore, our algorithm is able to compute kernels with size comparable to the smallest known kernels, but up to two orders of magnitude faster than previously possible. Finally, we show that our kernelization algorithm can be used to accelerate existing state-of-the-art heuristic algorithms, allowing us to find larger independent sets faster on large real-world networks and synthetic instances.
• Aggregate location data is often used to support smart services and applications, such as generating live traffic maps or predicting visits to businesses. In this paper, we present the first study on the feasibility of membership inference attacks on aggregate location time-series. We introduce a game-based definition of the adversarial task, and cast it as a classification problem where machine learning can be used to distinguish whether or not a target user is part of the aggregates. We empirically evaluate the power of these attacks on both raw and differentially private aggregates using two real-world mobility datasets. We find that membership inference is a serious privacy threat, and show how its effectiveness depends on the adversary's prior knowledge, the characteristics of the underlying location data, as well as the number of users and the timeframe on which aggregation is performed. Although differentially private defenses can indeed reduce the extent of the attacks, they also yield a significant loss in utility. Moreover, a strategic adversary mimicking the behavior of the defense mechanism can greatly limit the protection they provide. Overall, our work presents a novel methodology geared to evaluate membership inference on aggregate location data in real-world settings and can be used by providers to assess the quality of privacy protection before data release or by regulators to detect violations.
• In security-sensitive applications, the success of machine learning depends on a thorough vetting of their resistance to adversarial data. In one pertinent, well-motivated attack scenario, an adversary may attempt to evade a deployed system at test time by carefully manipulating attack samples. In this work, we present a simple but effective gradient-based approach that can be exploited to systematically assess the security of several, widely-used classification algorithms against evasion attacks. Following a recently proposed framework for security evaluation, we simulate attack scenarios that exhibit different risk levels for the classifier by increasing the attacker's knowledge of the system and her ability to manipulate attack samples. This gives the classifier designer a better picture of the classifier performance under evasion attacks, and allows him to perform a more informed model selection (or parameter setting). We evaluate our approach on the relevant security task of malware detection in PDF files, and show that such systems can be easily evaded. We also sketch some countermeasures suggested by our analysis.
• We propose to revisit knowledge transfer for training object detectors on target classes with only weakly supervised training images. We present a unified knowledge transfer framework based on training a single neural network multi-class object detector over all source classes, organized in a semantic hierarchy. This provides proposal scoring functions at multiple levels in the hierarchy, which we use to guide object localization in the target training set. Compared to works using a manually engineered class-generic objectness measure as a vehicle for transfer, our learned top-level scoring function for 'entity' is much stronger. Compared to works that perform class-specific transfer from a few most related source classes to the target class, our framework enables to explore a broad rage of generality of transfer. Experiments on 200 object classes in the ILSVRC 2013 dataset show that our technique (1) leads to much greater performance improvements than manually engineered objectness; (2) outperforms the best reported transfer learning results on this dataset by a wide margin (+40% correct localization on the target training set, and +14% mAP on the target test set).
• Aug 22 2017 cs.DS cs.DC arXiv:1708.06127v1
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art algorithms while our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.
• This paper presents a novel application to detect counterfeit identity documents forged by a scan-printing operation. Texture analysis approaches are proposed to extract validation features from security background that is usually printed in documents as IDs or banknotes. The main contribution of this work is the end-to-end mobile-server architecture, which provides a service for non-expert users and therefore can be used in several scenarios. The system also provides a crowdsourcing mode so labeled images can be gathered, generating databases for incremental training of the algorithms.
• Given a set $U$ of alternatives, a choice (correspondence) on $U$ is a contractive map $c$ defined on a family $\Omega$ of nonempty subsets of $U$. Semantically, a choice $c$ associates to each menu $A \in \Omega$ a nonempty subset $c(A) \subseteq A$ comprising all elements of $A$ that are deemed selectable by an agent. A choice on $U$ is total if its domain is the powerset of $U$ minus the empty set, and partial otherwise. According to the theory of revealed preferences, a choice is rationalizable if it can be retrieved from a binary relation on $U$ by taking all maximal elements of each menu. It is well-known that rationalizable choices are characterized by the satisfaction of suitable axioms of consistency, which codify logical rules of selection within menus. For instance, WARP (Weak Axiom of Revealed Preference) characterizes choices rationalizable by a transitive relation. Here we study the satisfiability problem for unquantified formulae of an elementary fragment of set theory involving a choice function symbol $\mathtt{c}$, the Boolean set operators and the singleton, the equality and inclusion predicates, and the propositional connectives. In particular, we consider the cases in which the interpretation of $\mathtt{c}$ satisfies any combination of two specific axioms of consistency, whose conjunction is equivalent to WARP. In two cases we prove that the related satisfiability problem is NP-complete, whereas in the remaining cases we obtain NP-completeness under the additional assumption that the number of choice terms is constant.
• Aug 22 2017 cs.CV arXiv:1708.06118v1
We present an approach for road segmentation that only requires image-level annotations at training time. We leverage distant supervision, which allows us to train our model using images that are different from the target domain. Using large publicly available image databases as distant supervisors, we develop a simple method to automatically generate weak pixel-wise road masks. These are used to iteratively train a fully convolutional neural network, which produces our final segmentation model. We evaluate our method on the Cityscapes dataset, where we compare it with a fully supervised approach. Further, we discuss the trade-off between annotation cost and performance. Overall, our distantly supervised approach achieves 93.8% of the performance of the fully supervised approach, while using orders of magnitude less annotation work.
• In this paper, we present the block Markov superposition transmission of BCH (BMST-BCH) codes, which can be constructed to obtain a very low error floor. To reduce the implementation complexity, we design a low complexity iterative sliding-window decoding algorithm, in which only binary and/or erasure messages are processed and exchanged between processing units. The error floor can be predicted by a genie-aided lower bound, while the waterfall performance can be analyzed by the density evolution method. To evaluate the error floor of the constructed BMST-BCH codes at a very low bit error rate (BER) region, we propose a fast simulation approach. Numerical results show that, at a target BER of $10^{-15}$, the hard-decision decoding of the BMST-BCH codes with overhead $25\%$ can achieve a net coding gain (NCG) of $10.55$ dB. Furthermore, the soft-decision decoding can yield an NCG of $10.74$ dB. The construction of BMST-BCH codes is flexible to trade off latency against performance at all overheads of interest and may find applications in optical transport networks as an attractive~candidate.
• Statistical inference can be computationally prohibitive in ultrahigh-dimensional linear models. Correlation-based variable screening, in which one leverages marginal correlations for removal of irrelevant variables from the model prior to statistical inference, can be used to overcome this challenge. Prior works on correlation-based variable screening either impose strong statistical priors on the linear model or assume specific post-screening inference methods. This paper first extends the analysis of correlation-based variable screening to arbitrary linear models and post-screening inference techniques. In particular, ($i$) it shows that a condition---termed the screening condition---is sufficient for successful correlation-based screening of linear models, and ($ii$) it provides insights into the dependence of marginal correlation-based screening on different problem parameters. Numerical experiments confirm that these insights are not mere artifacts of analysis; rather, they are reflective of the challenges associated with marginal correlation-based variable screening. Second, the paper explicitly derives the screening condition for two families of linear models, namely, sub-Gaussian linear models and arbitrary (random or deterministic) linear models. In the process, it establishes that---under appropriate conditions---it is possible to reduce the dimension of an ultrahigh-dimensional, arbitrary linear model to almost the sample size even when the number of active variables scales almost linearly with the sample size.
• This paper addresses the problem of extracting keyphrases from scientific articles and categorizing them as corresponding to a task, process, or material. We cast the problem as sequence tagging and introduce semi-supervised methods to a neural tagging model, which builds on recent advances in named entity recognition. Since annotated training data is scarce in this domain, we introduce a graph-based semi-supervised algorithm together with a data selection scheme to leverage unannotated articles. Both inductive and transductive semi-supervised learning strategies outperform state-of-the-art information extraction performance on the 2017 SemEval Task 10 ScienceIE task.
• We describe the 2017 version of Microsoft's conversational speech recognition system, in which we update our 2016 system with recent developments in neural-network-based acoustic and language modeling to further advance the state of the art on the Switchboard speech recognition task. The system adds a CNN-BLSTM acoustic model to the set of model architectures we combined previously, and includes character-based and dialog session aware LSTM language models in rescoring. For system combination we adopt a two-stage approach, whereby subsets of acoustic models are first combined at the senone/frame level, followed by a word-level voting via confusion networks. We also added a confusion network rescoring step after system combination. The resulting system yields a 5.1\% word error rate on the 2000 Switchboard evaluation set.
• A linear or multi-linear valuation on a finite abstract simplicial complex can be expressed as an analytic index dim(ker(D)) -dim(ker(D^*)) of a differential complex D:E -> F. In the discrete, a complex D can be called elliptic if a McKean-Singer spectral symmetry applies as this implies str(exp(-t D^2)) is t-independent. In that case, the analytic index of D is the sum of (-1)^k b_k(D), where b_k(D) is the k'th Betti number, which by Hodge is the nullity of the (k+1)'th block of the Hodge operator L=D^2. It can also be written as a topological index summing K(v) over the set of zero-dimensional simplices in G and where K is an Euler type curvature defined by G and D. This can be interpreted as a Atiyah-Singer type correspondence between analytic and topological index. Examples are the de Rham differential complex for the Euler characteristic X(G) or the connection differential complex for Wu characteristic w_k(G). Given an endomorphism T of an elliptic complex, the Lefschetz number X(T,G,D) is defined as the super trace of T acting on cohomology defined by E. It is equal to the sum i(v) over V which are contained in fixed simplices of T, and i is a Brouwer type index. This Atiyah-Bott result generalizes the Brouwer-Lefschetz fixed point theorem for an endomorphism of the simplicial complex G. In both the static and dynamic setting, the proof is done by heat deforming the Koopman operator U(T) to get the cohomological picture str(exp(-t D^2) U(T)) in the limit t to infinity and then use Hodge, and then by applying a discrete gradient flow to the simplex data defining the valuation to push str(U(T)) to V, getting curvature K(v) or the Brouwer type index i(v).

gae Jul 26 2017 21:19 UTC

For those interested in the literature on teleportation simulation of quantum channels, a detailed and *comprehensive* review is provided in Supplementary Note 8 of https://images.nature.com/original/nature-assets/ncomms/2017/170426/ncomms15043/extref/ncomms15043-s1.pdf
The note describes well the t

...(continued)
SHUAI ZHANG Jul 26 2017 00:20 UTC

I am still working on improving this survey. If you have any suggestions, questions or find any mistakes, please do not hesitate to contact me: shuai.zhang@student.unsw.edu.au.

Eddie Smolansky May 26 2017 05:23 UTC

Updated summary [here](https://github.com/eddiesmo/papers).

# How they made the dataset
- automated filtering with yolo and landmark detection projects
- crowd source final filtering (AMT - give 50 face images to turks and ask which don't belong)
- quality control through s

...(continued)
Stefano Pirandola May 05 2017 05:45 UTC

Today I have seen on the arXiv the version 2 of this paper on quantum reading. I am sorry to say that this revision still misses to acknowledge important contributions from previous works, especially in relation to the methods on channel simulation and teleportation that are crucial for its claims.

...(continued)
Lei Cui May 03 2017 09:00 UTC

what's the value for $n$ of n-grams?

Robin Blume-Kohout Apr 07 2017 20:30 UTC

Zak, David: thanks! So (I think) this is a relation problem, not a decision problem (or even a partial function). Which is fine -- I'm happier with relation problems than with sampling problems, and the quantum part of Shor's algorithm is solving a relation problem, which is a pretty good pedigre

...(continued)
David Gosset Apr 06 2017 20:11 UTC

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak Webb Apr 06 2017 17:15 UTC

You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guaran

...(continued)
Robin Blume-Kohout Apr 06 2017 15:05 UTC

Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allo

...(continued)