OpenRaiser/Intern-Atlas huggingface dataset:
$2^{(\log N)^{1/10-o(1)}}$ Hardness for Hypergraph Coloring
Venue: arXiv cs.CC 2015
Year: 2015

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/10-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, Håstad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{2^{Ω(\sqrt{\log\log N})}}$ colors. Their result is obtained by composing standard Label Cover with an inner-verifier based on Low Degree Long Code, using Reed-Muller code testing results by Dinur and Guruswami. Using a different approach, Khot and Saket constructed a new variant of Label Cover, and composed it with Quadratic Code to show quasi-NP-hardness of coloring 2-colorable 12-uniform hypergraphs with $2^{(\log N)^c}$ colors, for some $c$ around 1/20. Their construction of Label Cover is based on a new notion of superposition complexity for CSP instances. The composition with inner-verifier was subsequently improved by Varma, giving the same hardness result for 8-uniform hypergraphs. Our construction uses both Quadratic Code and Low Degree Long Code, and builds upon the work by Khot and Saket. We present a different approach to construct CSP instances with superposition hardness by observing that when the number of assignments is odd, satisfying a constraint in superposition is the same as "odd-covering" the constraint. We employ Low Degree Long Code in order to keep the construction efficient. In the analysis, we also adapt and generalize one of the key theorems by Dinur and Guruswami in the context of analyzing probabilistically checkable proof systems.
Online QoS Modeling in the Cloud: A Hybrid and Adaptive Multi-Learners Approach
Venue: arXiv cs.DC 2015
Year: 2015

Given the on-demand nature of cloud computing, managing cloud-based services requires accurate modeling for the correlation between their Quality of Service (QoS) and cloud configurations/resources. The resulted models need to cope with the dynamic fluctuation of QoS sensitivity and interference. However, existing QoS modeling in the cloud are limited in terms of both accuracy and applicability due to their static and semi- dynamic nature. In this paper, we present a fully dynamic multi- learners approach for automated and online QoS modeling in the cloud. We contribute to a hybrid learners solution, which improves accuracy while keeping model complexity adequate. To determine the inputs of QoS model at runtime, we partition the inputs space into two sub-spaces, each of which applies different symmetric uncertainty based selection techniques, and we then combine the sub-spaces results. The learners are also adaptive; they simultaneously allow several machine learning algorithms to model QoS function and dynamically select the best model for prediction on the fly. We experimentally evaluate our models using RUBiS benchmark and realistic FIFA 98 workload. The results show that our multi-learners approach is more accurate and effective in contrast to the other state-of-the-art approaches.
Deep convolutional networks for pancreas segmentation in CT imaging
Venue: arXiv cs.CV 2015
Year: 2015

Automatic organ segmentation is an important prerequisite for many computer-aided diagnosis systems. The high anatomical variability of organs in the abdomen, such as the pancreas, prevents many segmentation methods from achieving high accuracies when compared to other segmentation of organs like the liver, heart or kidneys. Recently, the availability of large annotated training sets and the accessibility of affordable parallel computing resources via GPUs have made it feasible for "deep learning" methods such as convolutional networks (ConvNets) to succeed in image classification tasks. These methods have the advantage that used classification features are trained directly from the imaging data. We present a fully-automated bottom-up method for pancreas segmentation in computed tomography (CT) images of the abdomen. The method is based on hierarchical coarse-to-fine classification of local image regions (superpixels). Superpixels are extracted from the abdominal region using Simple Linear Iterative Clustering (SLIC). An initial probability response map is generated, using patch-level confidences and a two-level cascade of random forest classifiers, from which superpixel regions with probabilities larger 0.5 are retained. These retained superpixels serve as a highly sensitive initial input of the pancreas and its surroundings to a ConvNet that samples a bounding box around each superpixel at different scales (and random non-rigid deformations at training time) in order to assign a more distinct probability of each superpixel region being pancreas or not. We evaluate our method on CT images of 82 patients (60 for training, 2 for validation, and 20 for testing). Using ConvNets we achieve average Dice scores of 68%+-10% (range, 43-80%) in testing. This shows promise for accurate pancreas segmentation, using a deep learning approach and compares favorably to state-of-the-art methods.
Asymptotic Analysis of Run-Length Encoding
Venue: arXiv cs.IT 2015
Year: 2015

Gallager and Van Voorhis have found optimal prefix-free codes $κ(K)$ for a random variable $K$ that is geometrically distributed: $\Pr[K=k] = p(1-p)^k$ for $k\ge 0$. We determine the asymptotic behavior of the expected length ${\rm Ex}[{\#κ(K)}]$ of these codes as $p\to 0$: $${\rm Ex}[{\#κ(K)}] = \log_2 {1\over p} + \log_2 \log 2 + 2 + f\left(\log_2 {1\over p} + \log_2 \log 2\right) + O(p),$$ where $$f(z) = 4\cdot 2^{-2^{1-\{z\}}} - \{z\} - 1,$$ and $\{z\} = z - \lfloor z\rfloor$ is the fractional part of $z$. The function $f(z)$ is a periodic function (with period $1$) that exhibits small oscillations (with magnitude less than $0.005$) about an even smaller average value (less than $0.0005$).
On the Performance of the Relay-ARQ Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the performance of relay networks in the presence of hybrid automatic repeat request (ARQ) feedback and adaptive power allocation. The throughput and the outage probability of different hybrid ARQ protocols are studied for independent and spatially-correlated fading channels. The results are obtained for the cases where there is a sum power constraint on the source and the relay or when each of the source and the relay are power-limited individually. With adaptive power allocation, the results demonstrate the efficiency of relay-ARQ techniques in different conditions.
FO Model Checking on Posets of Bounded Width
Venue: arXiv cs.LO 2015
Year: 2015

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an $n$-element poset $\cal P$ of width $w$ and an FO logic formula $ϕ$, and determines whether $ϕ$ holds on $\cal P$ in time $f(ϕ,w)\cdot n^2$.
Deciding the value 1 problem for probabilistic leaktight automata
Venue: arXiv cs.FL 2015
Year: 2015

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently; to overcome this, several classes of probabilistic automata of different nature were proposed, for which the value 1 problem has been shown decidable. In this paper, we introduce yet another class of probabilistic automata, called leaktight automata, which strictly subsumes all classes of probabilistic automata whose value 1 problem is known to be decidable. We prove that for leaktight automata, the value 1 problem is decidable (in fact, PSPACE-complete) by constructing a saturation algorithm based on the computation of a monoid abstracting the behaviours of the automaton. We rely on algebraic techniques developed by Simon to prove that this abstraction is complete. Furthermore, we adapt this saturation algorithm to decide whether an automaton is leaktight. Finally, we show a reduction allowing to extend our decidability results from finite words to infinite ones, implying that the value 1 problem for probabilistic leaktight parity automata is decidable.
Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff
Venue: arXiv cs.DS 2015
Year: 2015

This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms: (a) {\em backup}, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) {\em reinforcement}, namely, acquiring high-cost but fault-resistant components. To study the trade-off between these two mechanisms in a concrete setting, we address the problem of designing a $(b,r)$ {\em fault-tolerant} BFS (or $(b,r)$ FT-BFS for short) structure, namely, a subgraph $H$ of the network $G$ consisting of two types of edges: a set $E' \subseteq E$ of $r(n)$ fault-resistant {\em reinforcement} edges, which are assumed to never fail, and a (larger) set $E(H) \setminus E'$ of $b(n)$ fault-prone {\em backup} edges, such that subsequent to the failure of a single fault-prone backup edge $e \in E \setminus E'$, the surviving part of $H$ still contains an BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus \{e\}) \leq dist(s,v,G\setminus \{e\})$ for every $v \in V$ and $e \in E \setminus E'$. We establish the following tradeoff between $b(n)$ and $r(n)$: For every real $ε\in (0,1]$, if $r(n) = {\tildeΘ}(n^{1-ε})$, then $b(n) = {\tildeΘ}(n^{1+ε})$ is necessary and sufficient.
Contextualization of topics - browsing through terms, authors, journals and cluster allocations
Venue: arXiv cs.DL 2015
Year: 2015

This paper builds on an innovative Information Retrieval tool, Ariadne. The tool has been developed as an interactive network visualization and browsing tool for large-scale bibliographic databases. It basically allows to gain insights into a topic by contextualizing a search query (Koopman et al., 2015). In this paper, we apply the Ariadne tool to a far smaller dataset of 111,616 documents in astronomy and astrophysics. Labeled as the Berlin dataset, this data have been used by several research teams to apply and later compare different clustering algorithms. The quest for this team effort is how to delineate topics. This paper contributes to this challenge in two different ways. First, we produce one of the different cluster solution and second, we use Ariadne (the method behind it, and the interface - called LittleAriadne) to display cluster solutions of the different group members. By providing a tool that allows the visual inspection of the similarity of article clusters produced by different algorithms, we present a complementary approach to other possible means of comparison. More particular, we discuss how we can - with LittleAriadne - browse through the network of topical terms, authors, journals and cluster solutions in the Berlin dataset and compare cluster solutions as well as see their context.
Secrecy Communication with Security Rate Measure
Venue: arXiv cs.IT 2015
Year: 2015

We introduce a new measure on secrecy, which is established based on rate-distortion theory. It is named \emph{security rate}, which is the minimum (infimum) of the additional rate needed to reconstruct the source within target distortion level with any positive probability for wiretapper. It denotes the minimum distance in information metric (bits) from what wiretapper has received to any decrypted reconstruction (where decryption is defined as reconstruction within target distortion level with some positive possibility). By source coding theorem, it is equivalent to a distortion-based equivocation $\mathop{\min}\limits _{p\left(v^{n}|s^{n},m\right):Ed\left(S^{n},V^{n}\right)\le D_{E}}\frac{1}{n}I\left(S^{n};V^{n}|M\right)$ which can be seen as a direct extension of equivocation $\frac{1}{n}H\left(S^{n}|M\right)$ to lossy decryption case, given distortion level $D_{E}$ and the received (encrypted) message $M$ of wiretapper. In this paper, we study it in Shannon cipher system with lossless communication, where a source is transmitted from sender to legitimate receiver secretly and losslessly, and also eavesdropped by a wiretapper. We characterize the admissible region of secret key rate, coding rate of the source, wiretapper distortion, and security rate (distortion-based equivocation). Since the security rate equals the distortion-based equivocation, and the equivocation is a special case of the distortion-based equivocation (with Hamming distortion measure and $D_{E}=0$), this gives an answer for the meaning of the maximum equivocation.
Preprint Clinical Feedback and Technology Selection of Game Based Dysphonic Rehabilitation Tool
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on 2015 9th International Conference on Pervasive Computing Technologies for Healthcare (PervasiveHealth2015). An assistive training tool software for rehabilitation of dysphonic patients is evaluated according to the practical clinical feedback from the treatments. One stroke sufferer and one parkinson sufferer have provided earnest suggestions for the improvement of our tool software. The assistive tool employs a serious game as the attractive logic part, and running on the tablet with normal microphone as input device. Seven pitch estimation algorithms have been evaluated and compared with selected patients voice database. A series of benchmarks have been generated during the evaluation process for technology selection.
To Make a Robot Secure: An Experimental Analysis of Cyber Security Threats Against Teleoperated Surgical Robots
Venue: arXiv cs.RO 2015
Year: 2015

Teleoperated robots are playing an increasingly important role in military actions and medical services. In the future, remotely operated surgical robots will likely be used in more scenarios such as battlefields and emergency response. But rapidly growing applications of teleoperated surgery raise the question; what if the computer systems for these robots are attacked, taken over and even turned into weapons? Our work seeks to answer this question by systematically analyzing possible cyber security attacks against Raven II, an advanced teleoperated robotic surgery system. We identify a slew of possible cyber security threats, and experimentally evaluate their scopes and impacts. We demonstrate the ability to maliciously control a wide range of robots functions, and even to completely ignore or override command inputs from the surgeon. We further find that it is possible to abuse the robot's existing emergency stop (E-stop) mechanism to execute efficient (single packet) attacks. We then consider steps to mitigate these identified attacks, and experimentally evaluate the feasibility of applying the existing security solutions against these threats. The broader goal of our paper, however, is to raise awareness and increase understanding of these emerging threats. We anticipate that the majority of attacks against telerobotic surgery will also be relevant to other teleoperated robotic and co-robotic systems.
Constraints to Validate RDF Data Quality on Common Vocabularies in the Social, Behavioral, and Economic Sciences
Venue: arXiv cs.DL 2015
Year: 2015

To ensure high quality of and trust in both metadata and data, their representation in RDF must satisfy certain criteria - specified in terms of RDF constraints. From 2012 to 2015 together with other Linked Data community members and experts from the social, behavioral, and economic sciences (SBE), we developed diverse vocabularies to represent SBE metadata and rectangular data in RDF. The DDI-RDF Discovery Vocabulary (DDI-RDF) is designed to support the dissemination, management, and reuse of unit-record data, i.e., data about individuals, households, and businesses, collected in form of responses to studies and archived for research purposes. The RDF Data Cube Vocabulary (QB) is a W3C recommendation for expressing data cubes, i.e. multi-dimensional aggregate data and its metadata. Physical Data Description (PHDD) is a vocabulary to model data in rectangular format, i.e., tabular data. The data could either be represented in records with character-separated values (CSV) or fixed length. The Simple Knowledge Organization System (SKOS) is a vocabulary to build knowledge organization systems such as thesauri, classification schemes, and taxonomies. XKOS is a SKOS extension to describe formal statistical classifications. In this paper, we describe RDF constraints to validate metadata on unit-record data (DDI-RDF), aggregated data (QB), thesauri (SKOS), and statistical classifications (XKOS) and to validate tabular data (PHDD) - all of them represented in RDF. We classified these constraints according to the severity of occurring constraint violations. This technical report is updated continuously as modifying, adding, and deleting constraints remains ongoing work.
Perfectly Secure Index Coding
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the index coding problem in the presence of an eavesdropper. Messages are to be sent from one transmitter to a number of legitimate receivers who have side information about the messages, and share a set of secret keys with the transmitter. We assume perfect secrecy, meaning that the eavesdropper should not be able to retrieve any information about the message set. We study the minimum key lengths for zero-error and perfectly secure index coding problem. On one hand, this problem is a generalization of the index coding problem (and thus a difficult one). On the other hand, it is a generalization of the Shannon's cipher system. We show that a generalization of Shannon's one-time pad strategy is optimal up to a multiplicative constant, meaning that it obtains the entire boundary of the cone formed by looking at the secure rate region from the origin. Finally, we consider relaxation of the perfect secrecy and zero-error constraints to weak secrecy and asymptotically vanishing probability of error, and provide a secure version of the result, obtained by Langberg and Effros, on the equivalence of zero-error and $ε$-error regions in the conventional index coding problem.
General Capacity for Deterministic Dissemination in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study capacity scaling laws of the deterministic dissemination (DD) in random wireless networks under the generalized physical model (GphyM). This is truly not a new topic. Our motivation to readdress this issue is two-fold: Firstly, we aim to propose a more general result to unify the network capacity for general homogeneous random models by investigating the impacts of different parameters of the system on the network capacity. Secondly, we target to close the open gaps between the upper and the lower bounds on the network capacity in the literature. The generality of this work lies in three aspects: (1) We study the homogeneous random network of a general node density $λ\in [1,n]$, rather than either random dense network (RDN, $λ=n$) or random extended network (REN, $λ=1$) as in the literature. (2) We address the general deterministic dissemination sessions, \ie, the general multicast sessions, which unify the capacities for unicast and broadcast sessions by setting the number of destinations for each session as a general value $n_d\in[1,n]$. (3) We allow the number of sessions to change in the range $n_s\in(1,n]$, instead of assuming that $n_s=Θ(n)$ as in the literature. We derive the general upper bounds on the capacity for the arbitrary case of $(λ, n_d, n_s)$ by introducing the Poisson Boolean model of continuum percolation, and prove that they are tight according to the existing general lower bounds constructed in the literature.
Color Constancy Using CNNs
Venue: arXiv cs.CV 2015
Year: 2015

In this work we describe a Convolutional Neural Network (CNN) to accurately predict the scene illumination. Taking image patches as input, the CNN works in the spatial domain without using hand-crafted features that are employed by most previous methods. The network consists of one convolutional layer with max pooling, one fully connected layer and three output nodes. Within the network structure, feature learning and regression are integrated into one optimization process, which leads to a more effective model for estimating scene illumination. This approach achieves state-of-the-art performance on a standard dataset of RAW images. Preliminary experiments on images with spatially varying illumination demonstrate the stability of the local illuminant estimation ability of our CNN.
Information without rolling dice
Venue: arXiv cs.IT 2015
Year: 2015

The deterministic notions of capacity and entropy are studied in the context of communication and storage of information using square-integrable, bandlimited signals subject to perturbation. The $(ε,δ)$-capacity, that extends the Kolmogorov $ε$-capacity to packing sets of overlap at most $δ$, is introduced and compared to the Shannon capacity. The functional form of the results indicates that in both Kolmogorov and Shannon's settings, capacity and entropy grow linearly with the number of degrees of freedom, but only logarithmically with the signal to noise ratio. This basic insight transcends the details of the stochastic or deterministic description of the information-theoretic model. For $δ=0$, the analysis leads to new bounds on the Kolmogorov $ε$-capacity, and to a tight asymptotic expression of the Kolmogorov $ε$-entropy of bandlimited signals. A deterministic notion of error exponent is introduced. Applications of the theory are briefly discussed.
Generating upward sweeps in population using the Turchin--Korotayev model
Venue: arXiv cs.SI 2015
Year: 2015

The works of [Cha-DunAlvInoNieCarFieLaw,Cha-Dun] describe upward sweeps in populations of city-states and attempt to characterize such phenomenon. The model proposed in both [TurKor,Tur] describes how the population, state resources and internal conflict influence each other over time. We show that one can obtain an upward sweep in the population by altering particular parameters of the system of differential equations constituting the model given in [TurKor,Tur]. Moreover, we show that such a system has a unstable critical point and propose an approach for determining bifurcation points in the parameter space for the model.