OpenRaiser/Intern-Atlas huggingface dataset:
Tight Bounds for Online Vector Scheduling
Venue: arXiv cs.DS 2015
Year: 2015

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and $L_r$ norms of loads are among the most popular objectives considered. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations. Our main results are: -For identical machines, we show that the optimal competitive ratio is $Θ(\log d / \log \log d)$ by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. -For unrelated machines, we show that the optimal competitive ratio is $Θ(\log m + \log d)$ by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general $L_r$ norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual $L_r$ objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.
Approaches for Synthesis Conjectures in an SMT Solver
Venue: arXiv cs.LO 2015
Year: 2015

This report describes several approaches for handling synthesis conjectures within an Satisfiability Modulo Theories (SMT) solver. We describe approaches that primarily focus on determining the unsatisfiability of the negated form of synthesis conjectures using new techniques for quantifier instantiation.
Numeric Invariants from Multidimensional Persistence
Venue: arXiv cs.CG 2015
Year: 2015

We extend the results of Adcock, Carlsson, and Carlsson by constructing numeric invariants from the computation of a multidimensional persistence module as given by Carlsson, Singh, and Zomorodian.
Sparse And Low Rank Decomposition Based Batch Image Alignment for Speckle Reduction of retinal OCT Images
Venue: arXiv cs.CV 2015
Year: 2015

Optical Coherence Tomography (OCT) is an emerging technique in the field of biomedical imaging, with applications in ophthalmology, dermatology, coronary imaging etc. Due to the underlying physics, OCT images usually suffer from a granular pattern, called speckle noise, which restricts the process of interpretation. Here, a sparse and low rank decomposition based method is used for speckle reduction in retinal OCT images. This technique works on input data that consists of several B-scans of the same location. The next step is the batch alignment of the images using a sparse and low-rank decomposition based technique. Finally the denoised image is created by median filtering of the low-rank component of the processed data. Simultaneous decomposition and alignment of the images result in better performance in comparison to simple registration-based methods that are used in the literature for noise reduction of OCT images.
AGREE -- Algebraic Graph Rewriting with Controlled Embedding (Long Version)
Venue: arXiv cs.LO 2015
Year: 2015

The several algebraic approaches to graph transformation proposed in the literature all ensure that if an item is preserved by a rule, so are its connections with the context graph where it is embedded. But there are applications in which it is desirable, for example when cloning an item, to specify different embeddings for the original and for the copy. Therefore we propose a conservative extension of these approaches where a rule can specify how the embedding of a preserved item should be changed, typically by removing certain connections.
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Venue: arXiv cs.DS 2015
Year: 2015

We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is $\text{polyloglog}(n)$. In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of $\text{polyloglog}(n)$, where $\text{polyloglog}(n)$ is a bounded degree polynomial of $\log\log(n)$. We prove this by showing that any $k$-edge-connected unweighted graph has a $\text{polyloglog}(n)/k$-thin spanning tree. Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a $k$-edge-connected graph $G=(V,E)$ where $k\geq 7\log(n)$, we show that there is a matrix $D$ that "preserves" the structure of all cuts of $G$ such that for a set $F\subseteq E$ that induces an $Ω(k)$-edge-connected graph, the effective resistance of every edge in $F$ w.r.t. $D$ is at most $\text{polylog}(k)/k$. Then, we use a recent extension of the seminal work of Marcus, Spielman, and Srivastava [MSS13] by the authors [AO14] to prove the existence of a $\text{polylog}(k)/k$-spectrally thin tree with respect to $D$. Such a tree is $\text{polylog}(k)/k$-combinatorially thin with respect to $G$ as $D$ preserves the structure of cuts of $G$.
Sample(x)=(a*x<=t) is a distinguisher with probability 1/8
Venue: arXiv cs.DS 2015
Year: 2015

A random sampling function Sample:U->{0,1} for a key universe U is a distinguisher with probability p if for any given assignment of values v(x) to the keys x in U, including at least one non-zero v(x)!=0, the sampled sum sum{ v(x) | x in U and Sample(x) } is non-zero with probability at least p. Here the key values may come from any commutative monoid (addition is commutative and associative and zero is neutral). Such distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor and Naor used them for their small bias probability spaces [STOC'90]. Constant probability distinguishers are used for testing in contexts where the key values are not computed directly, yet where the sum is easily computed. A simple example is when we get a stream of key value pairs (x_1,v_1),(x_2,v_2),...,(x_n,v_n) where the same key may appear many times. The accumulated value of key x is v(x)=sum{v_i | x_i=x}. For space reasons, we may not be able to maintain v(x) for every key x, but the sampled sum is easily maintained as the single value sum{v_i | Sample(x_i)}. Here we show that when dealing with w-bit integers, if a is a uniform odd w-bit integer and t is a uniform w-bit integer, then Sample(x)=[ax mod 2^w <= t] is a distinguisher with probability 1/8. Working with standard units, that is, w=8, 16, 32, 64, we exploit that w-bit multiplication works modulo 2^w, discarding overflow automatically, and then the sampling decision is implemented by the C-code a*x<=t. Previous such samplers were much less computer friendly, e.g., the distinguisher of Naor and Naor [STOC'90] was more complicated and involved a 7-independent hash function.
On the Capacity of the Two-Hop Half-Duplex Relay Channel
Venue: arXiv cs.IT 2015
Year: 2015

Although extensively investigated, the capacity of the two-hop half-duplex (HD) relay channel is not fully understood. In particular, a capacity expression which can be easily evaluated is not available and an explicit coding scheme which achieves the capacity is not known either. In this paper, we derive a new expression for the capacity of the two-hop HD relay channel by simplifying previously derived converse expressions. Compared to previous results, the new capacity expression can be easily evaluated. Moreover, we propose an explicit coding scheme which achieves the capacity. To achieve the capacity, the relay does not only send information to the destination by transmitting information-carrying symbols but also with the zero symbols resulting from the relay's silence during reception. As examples, we compute the capacities of the two-hop HD relay channel for the cases when the source-relay and relay-destination links are both binary-symmetric channels (BSCs) and additive white Gaussian noise (AWGN) channels, respectively, and numerically compare the capacities with the rates achieved by conventional relaying where the relay receives and transmits in a codeword-by-codeword fashion and switches between reception and transmission in a strictly alternating manner. Our numerical results show that the capacities of the two-hop HD relay channel for BSC and AWGN links are significantly larger than the rates achieved with conventional relaying.
Viewpoints and Keypoints
Venue: arXiv cs.CV 2015
Year: 2015

We characterize the problem of pose estimation for rigid objects in terms of determining viewpoint to explain coarse pose and keypoint prediction to capture the finer details. We address both these tasks in two different settings - the constrained setting with known bounding boxes and the more challenging detection setting where the aim is to simultaneously detect and correctly estimate pose of objects. We present Convolutional Neural Network based architectures for these and demonstrate that leveraging viewpoint estimates can substantially improve local appearance based keypoint predictions. In addition to achieving significant improvements over state-of-the-art in the above tasks, we analyze the error modes and effect of object characteristics on performance to guide future efforts towards this goal.
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
Venue: arXiv cs.DS 2015
Year: 2015

In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation" variable, where the original problem corresponds to setting this variable to a constant value. For instance, the problem of packing sets of size at most $p$ into a given universe generalizes the Maximum Matching problem, which is recovered by taking $p=2$. Most often, the complexity of the problem increases with the relaxation variable, but very recently Abasi et al. have given a surprising example of a problem --- $r$-Simple $k$-Path --- that can be solved by a randomized algorithm with running time $O^*(2^{O(k \frac{\log r}{r})})$. That is, the complexity of the problem decreases with $r$. In this paper we pursue further the direction sketched by Abasi et al. Our main contribution is a derandomization tool that provides a deterministic counterpart of the main technical result of Abasi et al.: the $O^*(2^{O(k \frac{\log r}{r})})$ algorithm for $(r,k)$-Monomial Detection, which is the problem of finding a monomial of total degree $k$ and individual degrees at most $r$ in a polynomial given as an arithmetic circuit. Our technique works for a large class of circuits, and in particular it can be used to derandomize the result of Abasi et al. for $r$-Simple $k$-Path. On our way to this result we introduce the notion of representative sets for multisets, which may be of independent interest. Finally, we give two more examples of problems that were already studied in the literature, where the same relaxation phenomenon happens. The first one is a natural relaxation of the Set Packing problem, where we allow the packed sets to overlap at each element at most $r$ times. The second one is Degree Bounded Spanning Tree, where we seek for a spanning tree of the graph with a small maximum degree.
Behaviour Trees for Evolutionary Robotics
Venue: arXiv cs.RO 2015
Year: 2015

Evolutionary Robotics allows robots with limited sensors and processing to tackle complex tasks by means of sensory-motor coordination. In this paper we show the first application of the Behaviour Tree framework to a real robotic platform using the Evolutionary Robotics methodology. This framework is used to improve the intelligibility of the emergent robotic behaviour as compared to the traditional Neural Network formulation. As a result, the behaviour is easier to comprehend and manually adapt when crossing the reality gap from simulation to reality. This functionality is shown by performing real-world flight tests with the 20-gram DelFly Explorer flapping wing Micro Air Vehicle equipped with a 4-gram onboard stereo vision system. The experiments show that the DelFly can fully autonomously search for and fly through a window with only its onboard sensors and processing. The success rate of the optimised behaviour in simulation is 88% and the corresponding real-world performance is 54% after user adaptation. Although this leaves room for improvement, it is higher than the 46% success rate from a tuned user-defined controller.
Impact of redundant checks on the LP decoding thresholds of LDPC codes
Venue: arXiv cs.IT 2015
Year: 2015

Feldman et al.(2005) asked whether the performance of the LP decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove that for LDPC codes, even if we include all redundant checks, asymptotically there is no gain in the LP decoder threshold on the BSC under certain conditions on the base Tanner graph. First, we show that if the graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant checks in the LP does not significantly improve the threshold in the following sense: for each constant delta>0, there is a constant k>0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most delta upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies a rigidity condition, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the LLRs of the correct variables are arbitrarily small. By building on the work of Feldman et al.(2007) and Viderman(2013), we show that asymptotic strength follows from sufficiently large expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular graphs.
Reliable Diversity-Based Spatial Crowdsourcing by Moving Workers
Venue: arXiv cs.DB 2015
Year: 2015

With the rapid development of mobile devices and the crowdsourcig platforms, the spatial crowdsourcing has attracted much attention from the database community, specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions. In this paper, we consider an important spatial crowdsourcing problem, namely reliable diversity-based spatial crowdsourcing (RDB-SC), in which spatial tasks (such as taking videos/photos of a landmark or firework shows, and checking whether or not parking spaces are available) are time-constrained, and workers are moving towards some directions. Our RDB-SC problem is to assign workers to spatial tasks such that the completion reliability and the spatial/temporal diversities of spatial tasks are maximized. We prove that the RDB-SC problem is NP-hard and intractable. Thus, we propose three effective approximation approaches, including greedy, sampling, and divide-and-conquer algorithms. In order to improve the efficiency, we also design an effective cost-model-based index, which can dynamically maintain moving workers and spatial tasks with low cost, and efficiently facilitate the retrieval of RDB-SC answers. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic data sets.
A High Efficiency MAC Protocol for WLANs: Providing Fairness in Dense Scenarios
Venue: arXiv cs.NI 2015
Year: 2015

Collisions are a main cause of throughput degradation in WLANs. The current contention mechanism used in IEEE 802.11 networks is called Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). It uses a Binary Exponential Backoff (BEB) technique to randomise each contender attempt of transmitting, effectively reducing the collision probability. Nevertheless, CSMA/CA relies on a random backoff that while effective and fully decentralised, in principle is unable to completely eliminate collisions, therefore degrading the network throughput as more contenders attempt to share the channel. To overcome these situations, Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA) is able to create a collision-free schedule in a fully decentralised manner using a deterministic backoff after successful transmissions. Hysteresis and Fair Share are two extensions of CSMA/ECA to support a large number of contenders in a collision-free schedule. CSMA/ECA offers better throughput than CSMA/CA and short-term throughput fairness. This work describes CSMA/ECA and its extensions. Additionally, it provides the first evaluation results of CSMA/ECA with non-saturated traffic, channel errors, and its performance when coexisting with CSMA/CA nodes. Furthermore, it describes the effects of imperfect clocks over CSMA/ECA and present a mechanism to leverage the impact of channel errors and the addition/withdrawal of nodes over collision-free schedules. Finally, experimental results on throughput and lost frames from a CSMA/ECA implementation using commercial hardware and open-source firmware are presented.
High-Level Why-Not Explanations using Ontologies
Venue: arXiv cs.DB 2015
Year: 2015

We propose a novel foundational framework for why-not explanations, that is, explanations for why a tuple is missing from a query result. Our why-not explanations leverage concepts from an ontology to provide high-level and meaningful reasons for why a tuple is missing from the result of a query. A key algorithmic problem in our framework is that of computing a most-general explanation for a why-not question, relative to an ontology, which can either be provided by the user, or it may be automatically derived from the data and/or schema. We study the complexity of this problem and associated problems, and present concrete algorithms for computing why-not explanations. In the case where an external ontology is provided, we first show that the problem of deciding the existence of an explanation to a why-not question is NP-complete in general. However, the problem is solvable in polynomial time for queries of bounded arity, provided that the ontology is specified in a suitable language, such as a member of the DL-Lite family of description logics, which allows for efficient concept subsumption checking. Furthermore, we show that a most-general explanation can be computed in polynomial time in this case. In addition, we propose a method for deriving a suitable (virtual) ontology from a database and/or a data workspace schema, and we present an algorithm for computing a most-general explanation to a why-not question, relative to such ontologies. This algorithm runs in polynomial-time in the case when concepts are defined in a selection-free language, or if the underlying schema is fixed. Finally, we also study the problem of computing short most-general explanations, and we briefly discuss alternative definitions of what it means to be an explanation, and to be most general.
Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Venue: arXiv cs.DS 2015
Year: 2015

We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous bounds. The analysis is based on properties of random polynomials, namely the spacings of an ensemble of polynomials. Our technique also applies to other applications of tensor decompositions, including spherical Gaussian mixture models.
Loop-Back Interference Suppression for OFDM Signals via Sampled-Data Control
Venue: arXiv cs.SY 2015
Year: 2015

In this article, we consider the problem of loop-back interference suppression for orthogonal frequency division multiplexing (OFDM) signals in amplify-and-forward single-frequency full-duplex relay stations. The loop-back interference makes the system a closed-loop system, and hence it is important not only to suppress the interference but also to stabilize the system. For this purpose, we propose sampled-data $H^{\infty}$ design of digital filters that ensure the stability of the system and suppress the continuous-time effect of interference at the same time. Simulation results are shown to illustrate the effectiveness of the proposed method.
Asymptotic Parameter Tracking Performance with Measurement Data of 1-bit Resolution
Venue: arXiv cs.IT 2015
Year: 2015

The problem of signal parameter estimation and tracking with measurement data of low resolution is considered. In comparison to an ideal receiver with infinite receive resolution, the performance loss of a simplistic receiver with 1-bit resolution is investigated. For the case where the measurement data is preprocessed by a symmetric hard-limiting device with 1-bit output, it is well-understood that the performance for low SNR channel parameter estimation degrades moderately by 2/pi (-1.96 dB). Here we show that the 1-bit quantization loss can be significantly smaller if information about the temporal evolution of the channel parameters is taken into account in the form of a state-space model. By the analysis of a Bayesian bound for the achievable tracking performance, we attain the result that the quantization loss in dB is in general smaller by a factor of two if the channel evolution is slow. For the low SNR regime, this is equivalent to a reduced loss of sqrt(2/pi) (-0.98 dB). By simulating non-linear filtering algorithms for a satellite-based ranging application (GPS) and a UWB channel estimation problem, both with low-complexity 1-bit analog-to-digital converter (ADC) at the receiver, we verify that the analytical characterization of the tracking error is accurate. This shows that the performance loss due to observations with low amplitude resolution can, in practice, be much less pronounced than indicated by classical results. Finally, we discuss the implication of the result for medium SNR applications like channel estimation in the context of mobile wireless communications.
Running Probabilistic Programs Backwards
Venue: arXiv cs.PL 2015
Year: 2015

Many probabilistic programming languages allow programs to be run under constraints in order to carry out Bayesian inference. Running programs under constraints could enable other uses such as rare event simulation and probabilistic verification---except that all such probabilistic languages are necessarily limited because they are defined or implemented in terms of an impoverished theory of probability. Measure-theoretic probability provides a more general foundation, but its generality makes finding computational content difficult. We develop a measure-theoretic semantics for a first-order probabilistic language with recursion, which interprets programs as functions that compute preimages. Preimage functions are generally uncomputable, so we derive an abstract semantics. We implement the abstract semantics and use the implementation to carry out Bayesian inference, stochastic ray tracing (a rare event simulation), and probabilistic verification of floating-point error bounds.