OpenRaiser/Intern-Atlas huggingface dataset:
Reconstructing Generalized Staircase Polygons with Uniform Step Length
Venue: arXiv cs.DS 2017
Year: 2017

Visibility graph reconstruction, which asks us to construct a polygon that has a given visibility graph, is a fundamental problem with unknown complexity (although visibility graph recognition is known to be in PSPACE). We show that two classes of uniform step length polygons can be reconstructed efficiently by finding and removing rectangles formed between consecutive convex boundary vertices called tabs. In particular, we give an $O(n^2m)$-time reconstruction algorithm for orthogonally convex polygons, where $n$ and $m$ are the number of vertices and edges in the visibility graph, respectively. We further show that reconstructing a monotone chain of staircases (a histogram) is fixed-parameter tractable, when parameterized on the number of tabs, and polynomially solvable in time $O(n^2m)$ under reasonable alignment restrictions.
The Painter's Problem: covering a grid with colored connected polygons
Venue: arXiv cs.CG 2017
Year: 2017

Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors $χ$. Each cell $s$ in the grid is assigned a subset of colors $χ_s \subseteq χ$ and should be partitioned such that for each color $c\in χ_s$ at least one piece in the cell is identified with $c$. Cells assigned the empty color set remain white. We focus on the case where $χ= \{\text{red},\text{blue}\}$. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.
Exact Blur Measure Outperforms Conventional Learned Features for Depth Finding
Venue: arXiv cs.CV 2017
Year: 2017

Image analysis methods that are based on exact blur values are faced with the computational complexities due to blur measurement error. This atmosphere encourages scholars to look for handcrafted and learned features for finding depth from a single image. This paper introduces a novel exact realization for blur measures on digital images and implements it on a new measure of defocus Gaussian blur at edge points in Depth From Defocus (DFD) methods with the potential to change this atmosphere. The experiments on real images indicate superiority of the proposed measure in error performance over conventional learned features in the state-of the-art single image based depth estimation methods.
Linguistic Reflexes of Well-Being and Happiness in Echo
Venue: arXiv cs.CL 2017
Year: 2017

Different theories posit different sources for feelings of well-being and happiness. Appraisal theory grounds our emotional responses in our goals and desires and their fulfillment, or lack of fulfillment. Self Determination theory posits that the basis for well-being rests on our assessment of our competence, autonomy, and social connection. And surveys that measure happiness empirically note that people require their basic needs to be met for food and shelter, but beyond that tend to be happiest when socializing, eating or having sex. We analyze a corpus of private microblogs from a well-being application called ECHO, where users label each written post about daily events with a happiness score between 1 and 9. Our goal is to ground the linguistic descriptions of events that users experience in theories of well-being and happiness, and then examine the extent to which different theoretical accounts can explain the variance in the happiness scores. We show that recurrent event types, such as OBLIGATION and INCOMPETENCE, which affect people's feelings of well-being are not captured in current lexical or semantic resources.
Good Usability Practices in Scientific Software Development
Venue: arXiv cs.HC 2017
Year: 2017

Scientific software often presents very particular requirements regarding usability, which is often completely overlooked in this setting. As computational science has emerged as its own discipline, distinct from theoretical and experimental science, it has put new requirements on future scientific software developments. In this paper, we discuss the background of these problems and introduce nine aspects of good usability. We also highlight best practices for each aspect with an emphasis on applications in computational science.
Private Information Retrieval with Side Information
Venue: arXiv cs.IT 2017
Year: 2017

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of $K$ independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of $M$ messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message without revealing its identity while minimizing the amount of data downloaded from the servers. We focus on achieving information-theoretic privacy in two scenarios: (i) the user wants to protect jointly its demand and side information; (ii) the user wants to protect only the information about its demand, but not the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is $K-M$ messages, and in the second scenario it is $\lceil \frac{K}{M+1}\rceil$ messages, which should be compared to $K$ messages, the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.
A Secure Approach for Caching Contents in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2017
Year: 2017

Caching aims to store data locally in some nodes within the network to be able to retrieve the contents in shorter time periods. However, caching in the network did not always consider secure storage (due to the compromise between time performance and security). In this paper, a novel decentralized secure coded caching approach is proposed. In this solution, nodes only transmit coded files to avoid eavesdropper wiretapping and protect the user contents. In this technique random vectors are used to combine the contents using XOR operation. We modeled the proposed coded caching scheme by a Shannon cipher system to show that coded caching achieves asymptotic perfect secrecy. The proposed coded caching scheme significantly simplifies the routing protocol in cached networks while it reduces over-caching and achieves a higher throughput capacity compared to uncoded caching in reactive routing. It is shown that with the proposed coded caching scheme any content can be retrieved by selecting a random path while achieving asymptotic optimum solution. We have also studied the cache hit probability and shown that the coded cache hit probability is significantly higher than uncoded caching. A secure caching update algorithm is also presented.
Weighted Low-rank Tensor Recovery for Hyperspectral Image Restoration
Venue: arXiv cs.CV 2017
Year: 2017

Hyperspectral imaging, providing abundant spatial and spectral information simultaneously, has attracted a lot of interest in recent years. Unfortunately, due to the hardware limitations, the hyperspectral image (HSI) is vulnerable to various degradations, such noises (random noise, HSI denoising), blurs (Gaussian and uniform blur, HSI deblurring), and down-sampled (both spectral and spatial downsample, HSI super-resolution). Previous HSI restoration methods are designed for one specific task only. Besides, most of them start from the 1-D vector or 2-D matrix models and cannot fully exploit the structurally spectral-spatial correlation in 3-D HSI. To overcome these limitations, in this work, we propose a unified low-rank tensor recovery model for comprehensive HSI restoration tasks, in which non-local similarity between spectral-spatial cubic and spectral correlation are simultaneously captured by 3-order tensors. Further, to improve the capability and flexibility, we formulate it as a weighted low-rank tensor recovery (WLRTR) model by treating the singular values differently, and study its analytical solution. We also consider the exclusive stripe noise in HSI as the gross error by extending WLRTR to robust principal component analysis (WLRTR-RPCA). Extensive experiments demonstrate the proposed WLRTR models consistently outperform state-of-the-arts in typical low level vision HSI tasks, including denoising, destriping, deblurring and super-resolution.
Optimal epidemic dissemination
Venue: arXiv cs.DC 2017
Year: 2017

We consider the problem of reliable epidemic dissemination of a rumor in a fully connected network of~$n$ processes using push and pull operations. We revisit the random phone call model and show that it is possible to disseminate a rumor to all processes with high probability using $Θ(\ln n)$ rounds of communication and only $n+o(n)$ messages of size $b$, all of which are asymptotically optimal and achievable with pull and push-then-pull algorithms. This contradicts two highly-cited lower bounds of Karp et al. stating that any algorithm in the random phone call model running in $\mathcal{O}(\ln n)$ rounds with communication peers chosen uniformly at random requires at least $ω(n)$ messages to disseminate a rumor with high probability, and that any address-oblivious algorithm needs $Ω(n \ln \ln n)$ messages regardless of the number of communication rounds. The reason for this contradiction is that in the original work, processes do not have to share the rumor once the communication is established. However, it is implicitly assumed that they always do so in the proofs of their lower bounds, which, it turns out, is not optimal. Our algorithms are strikingly simple, address-oblivious, and robust against $εn$ adversarial failures and stochastic failures occurring with probability $δ$ for any $0 \leq \{ε,δ\} < 1$. Furthermore, they can handle multiple rumors of size $b \in ω(\ln n \ln \ln n)$ with $nb + o(nb)$ bits of communication per rumor.
DeepUNet: A Deep Fully Convolutional Network for Pixel-level Sea-Land Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Semantic segmentation is a fundamental research in remote sensing image processing. Because of the complex maritime environment, the sea-land segmentation is a challenging task. Although the neural network has achieved excellent performance in semantic segmentation in the last years, there are a few of works using CNN for sea-land segmentation and the results could be further improved. This paper proposes a novel deep convolution neural network named DeepUNet. Like the U-Net, its structure has a contracting path and an expansive path to get high resolution output. But differently, the DeepUNet uses DownBlocks instead of convolution layers in the contracting path and uses UpBlock in the expansive path. The two novel blocks bring two new connections that are U-connection and Plus connection. They are promoted to get more precise segmentation results. To verify our network architecture, we made a new challenging sea-land dataset and compare the DeepUNet on it with the SegNet and the U-Net. Experimental results show that DeepUNet achieved good performance compared with other architectures, especially in high-resolution remote sensing imagery.
Convergence, Continuity and Recurrence in Dynamic Epistemic Logic
Venue: arXiv cs.LO 2017
Year: 2017

The paper analyzes dynamic epistemic logic from a topological perspective. The main contribution consists of a framework in which dynamic epistemic logic satisfies the requirements for being a topological dynamical system thus interfacing discrete dynamic logics with continuous mappings of dynamical systems. The setting is based on a notion of logical convergence, demonstratively equivalent with convergence in Stone topology. Presented is a flexible, parametrized family of metrics inducing the latter, used as an analytical aid. We show maps induced by action model transformations continuous with respect to the Stone topology and present results on the recurrent behavior of said maps.
Autonomous Waypoint Generation with Safety Guarantees: On-Line Motion Planning in Unknown Environments
Venue: arXiv cs.RO 2017
Year: 2017

On-line motion planning in unknown environments is a challenging problem as it requires (i) ensuring collision avoidance and (ii) minimizing the motion time, while continuously predicting where to go next. Previous approaches to on-line motion planning assume that a rough map of the environment is available, thereby simplifying the problem. This paper presents a reactive on-line motion planner, Robust Autonomous Waypoint generation (RAW), for mobile robots navigating in unknown and unstructured environments. RAW generates a locally maximal ellipsoid around the robot, using semi-definite programming, such that the surrounding obstacles lie outside the ellipsoid. A reinforcement learning agent then generates a local waypoint in the robot's field of view, inside the ellipsoid. The robot navigates to the waypoint and the process iterates until it reaches the goal. By following the waypoints the robot navigates through a sequence of overlapping ellipsoids, and avoids collision. Robot's safety is guaranteed theoretically and the claims are validated through rigorous numerical experiments in four different experimental setups. Near-optimality is shown empirically by comparing RAW trajectories with the global optimal trajectories.
Compressed Sensing in Multi-Hop Large-Scale Wireless Sensor Networks Based on Routing Topology Tomography
Venue: arXiv cs.NI 2017
Year: 2017

Data acquisition from a multi-hop large-scale outdoor wireless sensor network (WSN) deployment for environmental monitoring is full of challenges. This is because the severe resource constraints on small battery-operated motes (e.g., bandwidth, memory, power, and computing capacity), the big data acquisition volume from the large-scale WSN,and the highly dynamic wireless link conditions in an outdoor communication environment. We present a novel compressed sensing approach which can recover the sensing data at the sink with high fidelity when very few data packets are collected, leading to a significant reduction of the net-work transmissions and thus an extension of the WSN lifetime. Interplaying with the dynamic WSN routing topology, the proposed approach is efficient and simple to implement on the resource-constrained motes without a mote's storing of any part of the random projection matrix, as opposed to other existing compressed sensing based schemes. We propose a systematic method via machine learning to find a suitable representation basis, for any given WSN deployment and data field, which is both sparse and incoherent with the random projection matrix in the compressed sensing for data acquisition. We validate our approach and evaluate its performance using a real-world multi-hop WSN testbed deployment in situ. The results demonstrate that our approach significantly outperforms existing compressed sensing approaches by reducing data recovery errors by an order of magnitude for the entire WSN observation field, while drastically reducing wireless communication costs at the same time.
From Query-By-Keyword to Query-By-Example: LinkedIn Talent Search Approach
Venue: arXiv cs.IR 2017
Year: 2017

One key challenge in talent search is to translate complex criteria of a hiring position into a search query, while it is relatively easy for a searcher to list examples of suitable candidates for a given position. To improve search efficiency, we propose the next generation of talent search at LinkedIn, also referred to as Search By Ideal Candidates. In this system, a searcher provides one or several ideal candidates as the input to hire for a given position. The system then generates a query based on the ideal candidates and uses it to retrieve and rank results. Shifting from the traditional Query-By-Keyword to this new Query-By-Example system poses a number of challenges: How to generate a query that best describes the candidates? When moving to a completely different paradigm, how does one leverage previous product logs to learn ranking models and/or evaluate the new system with no existing usage logs? Finally, given the different nature between the two search paradigms, the ranking features typically used for Query-By-Keyword systems might not be optimal for Query-By-Example. This paper describes our approach to solving these challenges. We present experimental results confirming the effectiveness of the proposed solution, particularly on query building and search ranking tasks. As of writing this paper, the new system has been available to all LinkedIn members.
Enhancing TCP End-to-End Performance in Millimeter-Wave Communications
Venue: arXiv cs.NI 2017
Year: 2017

Recently, millimeter-wave (mmWave) communications have received great attention due to the availability of large spectrum resources. Nevertheless, their impact on TCP performance has been overlooked, which is observed that the said TCP performance collapse occurs owing to the significant difference in signal quality between LOS and NLOS links. We propose a novel TCP design for mmWave communications, a mmWave performance enhancing proxy (mmPEP), enabling not only to overcome TCP performance collapse but also exploit the properties of mmWave channels. The base station installs the TCP proxy to operate the two functionalities called Ack management and batch retransmission. Specifically, the proxy sends the said early-Ack to the server not to decrease its sending rate even in the NLOS status. In addition, when a packet-loss is detected, the proxy retransmits not only lost packets but also the certain number of the following packets expected to be lost too. It is verified by ns-3 simulation that compared with benchmark, mmPEP enhances the end-to-end rate and packet delivery ratio by maintaining high sending rate with decreasing the loss recovery time.
Human Detection and Tracking for Video Surveillance A Cognitive Science Approach
Venue: arXiv cs.CV 2017
Year: 2017

With crimes on the rise all around the world, video surveillance is becoming more important day by day. Due to the lack of human resources to monitor this increasing number of cameras manually new computer vision algorithms to perform lower and higher level tasks are being developed. We have developed a new method incorporating the most acclaimed Histograms of Oriented Gradients the theory of Visual Saliency and the saliency prediction model Deep Multi Level Network to detect human beings in video sequences. Furthermore we implemented the k Means algorithm to cluster the HOG feature vectors of the positively detected windows and determined the path followed by a person in the video. We achieved a detection precision of 83.11% and a recall of 41.27%. We obtained these results 76.866 times faster than classification on normal images.
Deep rank-based transposition-invariant distances on musical sequences
Venue: arXiv cs.IR 2017
Year: 2017

Distances on symbolic musical sequences are needed for a variety of applications, from music retrieval to automatic music generation. These musical sequences belong to a given corpus (or style) and it is obvious that a good distance on musical sequences should take this information into account; being able to define a distance ex nihilo which could be applicable to all music styles seems implausible. A distance could also be invariant under some transformations, such as transpositions, so that it can be used as a distance between musical motives rather than musical sequences. However, to our knowledge, none of the approaches to devise musical distances seem to address these issues. This paper introduces a method to build transposition-invariant distances on symbolic musical sequences which are learned from data. It is a hybrid distance which combines learned feature representations of musical sequences with a handcrafted rank distance. This distance depends less on the musical encoding of the data than previous methods and gives perceptually good results. We demonstrate its efficiency on the dataset of chorale melodies by J.S. Bach.
Analysing Mutual Exclusion using Process Algebra with Signals
Venue: arXiv cs.LO 2017
Year: 2017

In contrast to common belief, the Calculus of Communicating Systems (CCS) and similar process algebras lack the expressive power to accurately capture mutual exclusion protocols without enriching the language with fairness assumptions. Adding a fairness assumption to implement a mutual exclusion protocol seems counter-intuitive. We employ a signalling operator, which can be combined with CCS, or other process calculi, and show that this minimal extension is expressive enough to model mutual exclusion: we confirm the correctness of Peterson's mutual exclusion algorithm for two processes, as well as Lamport's bakery algorithm, under reasonable assumptions on the underlying memory model. The correctness of Peterson's algorithm for more than two processes requires stronger, less realistic assumptions on the underlying memory model.
Using Session Types for Reasoning About Boundedness in the Pi-Calculus
Venue: arXiv cs.LO 2017
Year: 2017

The classes of depth-bounded and name-bounded processes are fragments of the pi-calculus for which some of the decision problems that are undecidable for the full calculus become decidable. P is depth-bounded at level k if every reduction sequence for P contains successor processes with at most k active nested restrictions. P is name-bounded at level k if every reduction sequence for P contains successor processes with at most k active bound names. Membership of these classes of processes is undecidable. In this paper we use binary session types to decise two type systems that give a sound characterization of the properties: If a process is well-typed in our first system, it is depth-bounded. If a process is well-typed in our second, more restrictive type system, it will also be name-bounded.
Distributive Laws for Monotone Specifications
Venue: arXiv cs.LO 2017
Year: 2017

Turi and Plotkin introduced an elegant approach to structural operational semantics based on universal coalgebra, parametric in the type of syntax and the type of behaviour. Their framework includes abstract GSOS, a categorical generalisation of the classical GSOS rule format, as well as its categorical dual, coGSOS. Both formats are well behaved, in the sense that each specification has a unique model on which behavioural equivalence is a congruence. Unfortunately, the combination of the two formats does not feature these desirable properties. We show that monotone specifications - that disallow negative premises - do induce a canonical distributive law of a monad over a comonad, and therefore a unique, compositional interpretation.