OpenRaiser/Intern-Atlas huggingface dataset:
From Weak to Strong LP Gaps for all CSPs
Venue: arXiv cs.CC 2016
Year: 2016

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $Ω\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances of size $n$. It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.. Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than the basic LP. Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which $Ω(\log \log n)$ levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to $Ω\left(\frac{\log n}{\log \log n}\right)$ levels.
Learning Transferable Policies for Monocular Reactive MAV Control
Venue: arXiv cs.RO 2016
Year: 2016

The ability to transfer knowledge gained in previous tasks into new contexts is one of the most important mechanisms of human learning. Despite this, adapting autonomous behavior to be reused in partially similar settings is still an open problem in current robotics research. In this paper, we take a small step in this direction and propose a generic framework for learning transferable motion policies. Our goal is to solve a learning problem in a target domain by utilizing the training data in a different but related source domain. We present this in the context of an autonomous MAV flight using monocular reactive control, and demonstrate the efficacy of our proposed approach through extensive real-world flight experiments in outdoor cluttered environments.
Mining and modeling character networks
Venue: arXiv cs.SI 2016
Year: 2016

We investigate social networks of characters found in cultural works such as novels and films. These character networks exhibit many of the properties of complex networks such as skewed degree distribution and community structure, but may be of relatively small order with a high multiplicity of edges. Building on recent work of beveridge, we consider graph extraction, visualization, and network statistics for three novels: Twilight by Stephanie Meyer, Steven King's The Stand, and J.K. Rowling's Harry Potter and the Goblet of Fire. Coupling with 800 character networks from films found in the http://moviegalaxies.com/ database, we compare the data sets to simulations from various stochastic complex networks models including random graphs with given expected degrees (also known as the Chung-Lu model), the configuration model, and the preferential attachment model. Using machine learning techniques based on motif (or small subgraph) counts, we determine that the Chung-Lu model best fits character networks and we conjecture why this may be the case.
Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures
Venue: arXiv cs.LO 2016
Year: 2016

This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length of relevant sequences, thereby establishing the computability of the distance.
Improving Zero-Day Malware Testing Methodology Using Statistically Significant Time-Lagged Test Samples
Venue: arXiv cs.CR 2016
Year: 2016

Enterprise networks are in constant danger of being breached by cyber-attackers, but making the decision about what security tools to deploy to mitigate this risk requires carefully designed evaluation of security products. One of the most important metrics for a protection product is how well it is able to stop malware, specifically on "zero"-day malware that has not been seen by the security community before. However, evaluating zero-day performance is difficult, because of larger number of previously unseen samples that are needed to properly measure the true and false positive rate, and the challenges involved in accurately labeling these samples. This paper addresses these issues from a statistical and practical perspective. Our contributions include first showing that the number of benign files needed for proper evaluation is on the order of a millions, and the number of malware samples needed is on the order of tens of thousands. We then propose and justify a time-delay method for easily collecting large number of previously unseen, but labeled, samples. This enables cheap and accurate evaluation of zero-day true and false positive rates. Finally, we propose a more fine-grain labeling of the malware/benignware in order to better model the heterogeneous distribution of files on various networks.
Size-Consistent Statistics for Anomaly Detection in Dynamic Networks
Venue: arXiv cs.LG 2016
Year: 2016

An important task in network analysis is the detection of anomalous events in a network time series. These events could merely be times of interest in the network timeline or they could be examples of malicious activity or network malfunction. Hypothesis testing using network statistics to summarize the behavior of the network provides a robust framework for the anomaly detection decision process. Unfortunately, choosing network statistics that are dependent on confounding factors like the total number of nodes or edges can lead to incorrect conclusions (e.g., false positives and false negatives). In this dissertation we describe the challenges that face anomaly detection in dynamic network streams regarding confounding factors. We also provide two solutions to avoiding error due to confounding factors: the first is a randomization testing method that controls for confounding factors, and the second is a set of size-consistent network statistics which avoid confounding due to the most common factors, edge count and node count.
Combining Answer Set Programming and Domain Heuristics for Solving Hard Industrial Problems (Application Paper)
Venue: arXiv cs.AI 2016
Year: 2016

Answer Set Programming (ASP) is a popular logic programming paradigm that has been applied for solving a variety of complex problems. Among the most challenging real-world applications of ASP are two industrial problems defined by Siemens: the Partner Units Problem (PUP) and the Combined Configuration Problem (CCP). The hardest instances of PUP and CCP are out of reach for state-of-the-art ASP solvers. Experiments show that the performance of ASP solvers could be significantly improved by embedding domain-specific heuristics, but a proper effective integration of such criteria in off-the-shelf ASP implementations is not obvious. In this paper the combination of ASP and domain-specific heuristics is studied with the goal of effectively solving real-world problem instances of PUP and CCP. As a byproduct of this activity, the ASP solver WASP was extended with an interface that eases embedding new external heuristics in the solver. The evaluation shows that our domain-heuristic-driven ASP solver finds solutions for all the real-world instances of PUP and CCP ever provided by Siemens. This paper is under consideration for acceptance in TPLP.
Dense semantic labeling of sub-decimeter resolution images with convolutional neural networks
Venue: arXiv cs.CV 2016
Year: 2016

Semantic labeling (or pixel-level land-cover classification) in ultra-high resolution imagery (< 10cm) requires statistical models able to learn high level concepts from spatial data, with large appearance variations. Convolutional Neural Networks (CNNs) achieve this goal by learning discriminatively a hierarchy of representations of increasing abstraction. In this paper we present a CNN-based system relying on an downsample-then-upsample architecture. Specifically, it first learns a rough spatial map of high-level representations by means of convolutions and then learns to upsample them back to the original resolution by deconvolutions. By doing so, the CNN learns to densely label every pixel at the original resolution of the image. This results in many advantages, including i) state-of-the-art numerical accuracy, ii) improved geometric accuracy of predictions and iii) high efficiency at inference time. We test the proposed system on the Vaihingen and Potsdam sub-decimeter resolution datasets, involving semantic labeling of aerial images of 9cm and 5cm resolution, respectively. These datasets are composed by many large and fully annotated tiles allowing an unbiased evaluation of models making use of spatial information. We do so by comparing two standard CNN architectures to the proposed one: standard patch classification, prediction of local label patches by employing only convolutions and full patch labeling by employing deconvolutions. All the systems compare favorably or outperform a state-of-the-art baseline relying on superpixels and powerful appearance descriptors. The proposed full patch labeling CNN outperforms these models by a large margin, also showing a very appealing inference time.
Tracking the Digital Footprints to Scholarly Articles from Social Media
Venue: arXiv cs.DL 2016
Year: 2016

Scholarly articles are discussed and shared on social media, which generates altmetrics. On the opposite side, what is the impact of social media on the dissemination of scholarly articles and how to measure it? What are the visiting patterns? Investigating these issues, the purpose of this study is to seek a solution to fill the research gap, specifically, to explore the dynamic visiting patterns directed by social media, and examine the effects of social buzz on the article visits. Using the unique real referral data of 110 scholarly articles, which are daily updated in a 90-day period, this paper proposes a novel method to make analysis. We find that visits from social media are fast to accumulate but decay rapidly. Twitter and Facebook are the two most important social referrals that directing people to scholarly articles, the two are about the same and account for over 95% of the total social referral directed visits. There is synchronism between tweets and tweets resulted visits. Social media and open access are playing important roles in disseminating scholarly articles and promoting public understanding science, which are confirmed quantitatively for the first time with real data in this study.
Directed expected utility networks
Venue: arXiv cs.AI 2016
Year: 2016

A variety of statistical graphical models have been defined to represent the conditional independences underlying a random vector of interest. Similarly, many different graphs embedding various types of preferential independences, as for example conditional utility independence and generalized additive independence, have more recently started to appear. In this paper we define a new graphical model, called a directed expected utility network, whose edges depict both probabilistic and utility conditional independences. These embed a very flexible class of utility models, much larger than those usually conceived in standard influence diagrams. Our graphical representation, and various transformations of the original graph into a tree structure, are then used to guide fast routines for the computation of a decision problem's expected utilities. We show that our routines generalize those usually utilized in standard influence diagrams' evaluations under much more restrictive conditions. We then proceed with the construction of a directed expected utility network to support decision makers in the domain of household food security.
On constacyclic codes over $\mathbb{Z}_4[u]/\langle u^2-1\rangle$ and their Gray images
Venue: arXiv cs.IT 2016
Year: 2016

We first define a new Gray map from $R=\mathbb{Z}_4+u\mathbb{Z}_4$ to $\mathbb{Z}^{2}_{4}$, where $u^2=1$ and study $(1+2u)$-constacyclic codes over $R$. Also of interest are some properties of $(1+2u)$-constacyclic codes over $R$. Considering their $\mathbb{Z}_4$ images, we prove that the Gray images of $(1+2u)$-constacyclic codes of length $n$ over $R$ are cyclic codes of length $2n$ over $\mathbb{Z}_4$. In many cases the latter codes have better parameters than those in the online database of Aydin and Asamov. We also give a corrected version of a table of new cyclic $R$-codes published by Özen et al. in Finite Fields and Their Applications, {\bf 38}, (2016) 27-39.
Mitochondria-based Renal Cell Carcinoma Subtyping: Learning from Deep vs. Flat Feature Representations
Venue: arXiv cs.LG 2016
Year: 2016

Accurate subtyping of renal cell carcinoma (RCC) is of crucial importance for understanding disease progression and for making informed treatment decisions. New discoveries of significant alterations to mitochondria between subtypes make immunohistochemical (IHC) staining based image classification an imperative. Until now, accurate quantification and subtyping was made impossible by huge IHC variations, the absence of cell membrane staining for cytoplasm segmentation as well as the complete lack of systems for robust and reproducible image based classification. In this paper we present a comprehensive classification framework to overcome these challenges for tissue microarrays (TMA) of RCCs. We compare and evaluate models based on domain specific hand-crafted "flat"-features versus "deep" feature representations from various layers of a pre-trained convolutional neural network (CNN). The best model reaches a cross-validation accuracy of 89%, which demonstrates for the first time, that robust mitochondria-based subtyping of renal cancer is feasible
Distributed, End-to-end Verifiable, and Privacy-Preserving Internet Voting Systems
Venue: arXiv cs.CR 2016
Year: 2016

E-voting systems are a powerful technology for improving democracy. Unfortunately, prior voting systems have single points-of-failure, which may compromise availability, privacy, or integrity of the election results. We present the design, implementation, security analysis, and evaluation of the D-DEMOS suite of distributed, privacy-preserving, and end-to-end verifiable e-voting systems. We present two systems: one asynchronous and one with minimal timing assumptions but better performance. Our systems include a distributed vote collection subsystem that does not require cryptographic operations on behalf of the voter. We also include a distributed, replicated and fault-tolerant Bulletin Board component, that stores all necessary election-related information, and allows any party to read and verify the complete election process. Finally, we incorporate trustees, who control result production while guaranteeing privacy and end-to-end-verifiability as long as their strong majority is honest. Our suite of e-voting systems are the first whose voting operation is human verifiable, i.e., a voter can vote over the web, even when her web client stack is potentially unsafe, without sacrificing her privacy, and still be assured her vote was recorded as cast. Additionally, a voter can outsource election auditing to third parties, still without sacrificing privacy. We provide a model and security analysis of the systems, implement complete prototypes, measure their performance experimentally, and demonstrate their ability to handle large-scale elections. Finally, we demonstrate the performance trade-offs between the two versions of the system. A preliminary version of our system was used to conduct exit-polls at three voting sites for two national-level elections and is being adopted for use by the largest civil union of workers in Greece, consisting of over a half million members.
Registration of Volumetric Prostate Scans using Curvature Flow
Venue: arXiv cs.GR 2016
Year: 2016

Radiological imaging of the prostate is becoming more popular among researchers and clinicians in searching for diseases, primarily cancer. Scans might be acquired with different equipment or at different times for prognosis monitoring, with patient movement between scans, resulting in multiple datasets that need to be registered. For these cases, we introduce a method for volumetric registration using curvature flow. Multiple prostate datasets are mapped to canonical solid spheres, which are in turn aligned and registered through the use of identified landmarks on or within the gland. Theoretical proof and experimental results show that our method produces homeomorphisms with feature constraints. We provide thorough validation of our method by registering prostate scans of the same patient in different orientations, from different days and using different modes of MRI. Our method also provides the foundation for a general group-wise registration using a standard reference, defined on the complex plane, for any input. In the present context, this can be used for registering as many scans as needed for a single patient or different patients on the basis of age, weight or even malignant and non-malignant attributes to study the differences in general population. Though we present this technique with a specific application to the prostate, it is generally applicable for volumetric registration problems.
Multimodal Brain Visualization
Venue: arXiv cs.GR 2016
Year: 2016

Current connectivity diagrams of human brain image data are either overly complex or overly simplistic. In this work we introduce simple yet accurate interactive visual representations of multiple brain image structures and the connectivity among them. We map cortical surfaces extracted from human brain magnetic resonance imaging (MRI) data onto 2D surfaces that preserve shape (angle), extent (area), and spatial (neighborhood) information for 2D (circular disk) and 3D (spherical) mapping, split these surfaces into separate patches, and cluster functional and diffusion tractography MRI connections between pairs of these patches. The resulting visualizations are easier to compute on and more visually intuitive to interact with than the original data, and facilitate simultaneous exploration of multiple data sets, modalities, and statistical maps.
Distributed or Monolithic? A Computational Architecture Decision Framework
Venue: arXiv cs.DC 2016
Year: 2016

Distributed architectures have become ubiquitous in many complex technical and socio-technical systems because of their role in improving uncertainty management, accommodating multiple stakeholders, and increasing scalability and evolvability. This departure from monolithic architectures provides a system with more flexibility and robustness in response to uncertainties that it may confront during its lifetime. Distributed architecture does not provide benefits only, as it can increase cost and complexity of the system and result in potential instabilities. The mechanisms behind this trade-off, however, are analogous to those of the widely-studied transition from integrated to modular architectures. In this paper, we use a conceptual decision framework that unifies modularity and distributed architecture on a five-stage systems architecture spectrum. We add an extensive computational layer to the framework and explain how this can enhance decision making about the level of modularity of the architecture. We then apply it to a simplified demonstration of the Defense Advanced Research Projects Agency (DARPA) fractionated satellite program. Through simulation, we calculate the net value that is gained (or lost) by migrating from a monolithic architecture to a distributed architecture and show how this value changes as a function of uncertainties in the environment and various system parameters. Additionally, we use Value at Risk as a measure for the risk of losing the value of distributed architecture, given its inherent uncertainty.
Analysis of M2/M2/1/R,N Queuing Model for Multimedia over 3.5G Wireless Network Downlink
Venue: arXiv cs.NI 2016
Year: 2016

Analysis of an M2/M2/1/R, N queuing model for the multimedia transmission over HSDPA/3.5G downlink is presented. The queue models the downlink buffer with source multimedia traffic streams comprising two classes of flows: realtime and non real-time. Time priority is accorded to the real-time flows while the non real-time flows are given buffer space priority. An analytic evaluation of the impact of varying the buffer partition threshold on the QoS performance of both classes of customers is undertaken. The results are validated with a discrete event simulation model developed in C language. Finally, a cost function for the joint optimization of the traffic QoS parameters is derived.
FPGA system for real-time computational extended depth of field imaging using phase aperture coding
Venue: arXiv cs.CV 2016
Year: 2016

We present a proof-of-concept end-to-end system for computational extended depth of field (EDOF) imaging. The acquisition is performed through a phase-coded aperture implemented by placing a thin wavelength-dependent optical mask inside the pupil of a conventional camera lens, as a result of which, each color channel is focused at a different depth. The reconstruction process receives the raw Bayer image as the input, and performs blind estimation of the output color image in focus at an extended range of depths using a patch-wise sparse prior. We present a fast non-iterative reconstruction algorithm operating with constant latency in fixed-point arithmetics and achieving real-time performance in a prototype FPGA implementation. The output of the system, on simulated and real-life scenes, is qualitatively and quantitatively better than the result of clear-aperture imaging followed by state-of-the-art blind deblurring.
System level analysis of heterogeneous networks under imperfect traffic hotspot localization
Venue: arXiv cs.NI 2016
Year: 2016

We study, in this paper, the impact of imperfect small cell positioning with respect to traffic hotspots in cellular networks. In order to derive the throughput distribution in macro and small cells, we firstly perform static level analysis of the system considering a non-uniform distribution of user locations. We secondly introduce the dynamics of the system, characterized by random arrivals and departures of users after a finite service duration, with the service rates and distribution of radio conditions outfitted from the first part of the work. When dealing with the dynamics of the system, macro and small cells are modeled by multi-class processor sharing queues. Macro and small cells are assumed to be operating in the same bandwidth. Consequently, they are coupled due to the mutual interferences generated by each cell to the other. We derive several performance metrics such as the mean flow throughput and the gain, if any, generated from deploying small cells to manage traffic hotspots. Our results show that in case the hotspot is near the macro BS (Base Station), even a perfect positioning of the small cell will not yield improved performance due to the high interference experienced at macro and small cell users. However, in case the hotspot is located far enough from the macro BS, performing errors in small cell positioning is tolerated (since related results show positive gains) and it is still beneficial in offloading traffic from the congested macrocell. The best performance metrics depend also on several other important factors such as the users' arrival intensity, the capacity of the cell and the size of the traffic hotspot.