OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Broader View of Theory of Computing
Venue: arXiv cs.NA 2014
Year: 2014

Beginning with the projectively invariant method for linear programming, interior point methods have led to powerful algorithms for many difficult computing problems, in combinatorial optimization, logic, number theory and non-convex optimization. Algorithms for convex optimization benefitted from many pre-established ideas from classical mathematics, but non-convex problems require new concepts. Lecture series I am presenting at the conference on Foundations of Computational Mathematics, 2014, outlines some of these concepts{computational models based on the concept of the continuum, algorithms invariant w.r.t. projective, bi-rational, and bi-holomorphic transformations on co-ordinate representation, extended proof systems for more efficient certificates of optimality, extensions of Grassmanns extension theory, efficient evaluation methods for the effect of exponential number of constraints, theory of connected sets based on graded connectivity, theory of curved spaces adapted to the problem data, and concept of relatively algebraic sets in curved space. Since this conference does not have a proceedings, the purpose of this article is to provide the material being presented at the conference in more widely accessible form.
Deep Domain Confusion: Maximizing for Domain Invariance
Venue: arXiv cs.CV 2014
Year: 2014

Recent reports suggest that a generic supervised deep CNN model trained on a large-scale dataset reduces, but does not remove, dataset bias on a standard benchmark. Fine-tuning deep models in a new domain can require a significant amount of data, which for many applications is simply not available. We propose a new CNN architecture which introduces an adaptation layer and an additional domain confusion loss, to learn a representation that is both semantically meaningful and domain invariant. We additionally show that a domain confusion metric can be used for model selection to determine the dimension of an adaptation layer and the best position for the layer in the CNN architecture. Our proposed adaptation method offers empirical performance which exceeds previously published results on a standard benchmark visual domain adaptation task.
Road Detection by One-Class Color Classification: Dataset and Experiments
Venue: arXiv cs.CV 2014
Year: 2014

Detecting traversable road areas ahead a moving vehicle is a key process for modern autonomous driving systems. A common approach to road detection consists of exploiting color features to classify pixels as road or background. These algorithms reduce the effect of lighting variations and weather conditions by exploiting the discriminant/invariant properties of different color representations. Furthermore, the lack of labeled datasets has motivated the development of algorithms performing on single images based on the assumption that the bottom part of the image belongs to the road surface. In this paper, we first introduce a dataset of road images taken at different times and in different scenarios using an onboard camera. Then, we devise a simple online algorithm and conduct an exhaustive evaluation of different classifiers and the effect of using different color representation to characterize pixels.
Online Covering with Convex Objectives and Applications
Venue: arXiv cs.DS 2014
Year: 2014

We give an algorithmic framework for minimizing general convex objectives (that are differentiable and monotone non-decreasing) over a set of covering constraints that arrive online. This substantially extends previous work on online covering for linear objectives (Alon {\em et al.}, STOC 2003) and online covering with offline packing constraints (Azar {\em et al.}, SODA 2013). To the best of our knowledge, this is the first result in online optimization for generic non-linear objectives; special cases of such objectives have previously been considered, particularly for energy minimization. As a specific problem in this genre, we consider the unrelated machine scheduling problem with startup costs and arbitrary $\ell_p$ norms on machine loads (including the surprisingly non-trivial $\ell_1$ norm representing total machine load). This problem was studied earlier for the makespan norm in both the offline (Khuller~{\em et al.}, SODA 2010; Li and Khuller, SODA 2011) and online settings (Azar {\em et al.}, SODA 2013). We adapt the two-phase approach of obtaining a fractional solution and then rounding it online (used successfully to many linear objectives) to the non-linear objective. The fractional algorithm uses ideas from our general framework that we described above (but does not fit the framework exactly because of non-positive entries in the constraint matrix). The rounding algorithm uses ideas from offline rounding of LPs with non-linear objectives (Azar and Epstein, STOC 2005; Kumar {\em et al.}, FOCS 2005). Our competitive ratio is tight up to a logarithmic factor. Finally, for the important special case of total load ($\ell_1$ norm), we give a different rounding algorithm that obtains a better competitive ratio than the generic rounding algorithm for $\ell_p$ norms. We show that this competitive ratio is asymptotically tight.
Towards Logical Architecture and Formal Analysis of Dependencies Between Services
Venue: arXiv cs.SE 2014
Year: 2014

This paper presents a formal approach to modelling and analysis of data and control flow dependencies between services within remotely deployed distributed systems of services. Our work aims at elaborating for a concrete system, which parts of the system (or system model) are necessary to check a given property. The approach allows services decomposition oriented towards efficient checking of system properties as well as analysis of dependencies within a system.
Cost-Effective Frequency Planning for Capacity Enhancement of Femtocellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Femtocellular networks will co-exist with macrocellular networks, mitigation of the interference between these two network types is a key challenge for successful integration of these two technologies. In particular, there are several interference mechanisms between the femtocellular and the macrocellular networks, and the effects of the resulting interference depend on the density of femtocells and the overlaid macrocells in a particular coverage area. While improper interference management can cause a significant reduction in the system capacity and can increase the outage probability, effective and efficient frequency allocation among femtocells and macrocells can result in a successful co-existence of these two technologies. Furthermore, highly dense femtocellular deployments the ultimate goal of the femtocellular technology will require significant degree of self-organization in lieu of manual configuration. In this paper, we present various femtocellular network deployment scenarios, and we propose a number of frequency-allocation schemes to mitigate the interference and to increases the spectral efficiency of the integrated network. These schemes include: shared frequency band, dedicated frequency band, sub-frequency band, static frequency-reuse, and dynamic frequency-reuse.
Negacyclic codes over Z4+uZ4
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study negacyclic codes of odd length and of length $2^k$ over the ring $R=\mathbb{Z}_4+u\mathbb{Z}_4$, $u^2=0$. We give the complete structure of negacyclic codes for both the cases. We have obtained a minimal spanning set for negacyclic codes of odd lengths over $R$. A necessary and sufficient condition for negacyclic codes of odd lengths to be free is presented. We have determined the cardinality of negacyclic codes in each case. We have obtained the structure of the duals of negacyclic codes of length $2^k$ over $R$ and also characterized self-dual negacyclic codes of length $2^k$ over $R$.
Answering Conjunctive Queries with Inequalities
Venue: arXiv cs.DB 2014
Year: 2014

In this paper, we study the complexity of answering conjunctive queries (CQ) with inequalities). In particular, we are interested in comparing the complexity of the query with and without inequalities. The main contribution of our work is a novel combinatorial technique that enables us to use any Select-Project-Join query plan for a given CQ without inequalities in answering the CQ with inequalities, with an additional factor in running time that only depends on the query. The key idea is to define a new projection operator, which keeps a small representation (independent of the size of the database) of the set of input tuples that map to each tuple in the output of the projection; this representation is used to evaluate all the inequalities in the query. Second, we generalize a result by Papadimitriou-Yannakakis [17] and give an alternative algorithm based on the color-coding technique [4] to evaluate a CQ with inequalities by using an algorithm for the CQ without inequalities. Third, we investigate the structure of the query graph, inequality graph, and the augmented query graph with inequalities, and show that even if the query and the inequality graphs have bounded treewidth, the augmented graph not only can have an unbounded treewidth but can also be NP-hard to evaluate. Further, we illustrate classes of queries and inequalities where the augmented graphs have unbounded treewidth, but the CQ with inequalities can be evaluated in poly-time. Finally, we give necessary properties and sufficient properties that allow a class of CQs to have poly-time combined complexity with respect to any inequality pattern. We also illustrate classes of queries where our query-plan-based technique outperforms the alternative approaches discussed in the paper.
Machine Learning for Neuroimaging with Scikit-Learn
Venue: arXiv cs.LG 2014
Year: 2014

Statistical machine learning methods are increasingly used for neuroimaging data analysis. Their main virtue is their ability to model high-dimensional datasets, e.g. multivariate analysis of activation images or resting-state time series. Supervised learning is typically used in decoding or encoding settings to relate brain images to behavioral or clinical observations, while unsupervised learning can uncover hidden structures in sets of images (e.g. resting state functional MRI) or find sub-populations in large cohorts. By considering different functional neuroimaging applications, we illustrate how scikit-learn, a Python machine learning library, can be used to perform some key analysis steps. Scikit-learn contains a very large set of statistical learning algorithms, both supervised and unsupervised, and its application to neuroimaging data provides a versatile tool to study the brain.
Almost Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Galleries
Venue: arXiv cs.CG 2014
Year: 2014

We address recently proposed chromatic versions of the classic Art Gallery Problem. Assume a simple polygon $P$ is guarded by a finite set of point guards and each guard is assigned one of $t$ colors. Such a chromatic guarding is said to be conflict-free if each point $p\in P$ sees at least one guard with a unique color among all guards visible from $p$. The goal is to establish bounds on the function $χ_{cf}(n)$ of the number of colors sufficient to guarantee the existence of a conflict-free chromatic guarding for any $n$-vertex polygon. Bärtschi and Suri showed $χ_{cf}(n)\in O(\log n)$ (Algorithmica, 2014) for simple orthogonal polygons and the same bound applies to general simple polygons (Bärtschi et al., SoCG 2014). In this paper, we assume the r-visibility model instead of standard line visibility. Points $p$ and $q$ in an orthogonal polygon are r-visible to each other if the rectangle spanned by the points is contained in $P$. For this model we show $χ_{cf}(n)\in O(\log\log n)$ and $χ_{cf}(n)\in Ω(\log\log n /\log\log\log n)$. Most interestingly, we can show that the lower bound proof extends to guards with line visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau. This is the first non-trivial lower bound for this problem setting.Furthermore, for the strong chromatic version of the problem, where all guards r-visible from a point must have distinct colors, we prove a $Θ(\log n)$-bound. Our results can be interpreted as coloring results for special geometric hypergraphs.
Efficient edge-skeleton computation for polytopes defined by oracles
Venue: arXiv cs.CG 2014
Year: 2014

In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems (and polytope representations) for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton (including vertex enumeration) of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity's exponential dependence in the dimension.
Energy Consumption of VLSI Decoders
Venue: arXiv cs.IT 2014
Year: 2014

Thompson's model of VLSI computation relates the energy of a computation to the product of the circuit area and the number of clock cycles needed to carry out the computation. It is shown that for any family of circuits implemented according to this model, using any algorithm that performs decoding of a codeword passed through a binary erasure channel, as the block length approaches infinity either (a) the probability of block error is asymptotically lower bounded by 1/2 or (b) the energy of the computation scales at least as Omega(n(log n)^(1/2)), and so the energy of successful decoding, per decoded bit, must scale at least as Omega((log n)^(1/2)). This implies that the average energy per decoded bit must approach infinity for any sequence of codes that approaches capacity. The analysis techniques used are then extended to the case of serial computation, showing that if a circuit is restricted to serial computation, then as block length approaches infinity, either the block error probability is lower bounded by 1/2 or the energy scales at least as fast as Omega(n log(n)). In a very general case that allows for the number of output pins to vary with block length, it is shown that the average energy per decoded bit must scale as Omega(n(log n)^(1/5)). A simple example is provided of a class of circuits performing low-density parity-check decoding whose energy complexity scales as O(n^2 log log n).
Locating Contagion Sources in Networks with Partial Timestamps
Venue: arXiv cs.SI 2014
Year: 2014

This paper studies the problem of identifying the contagion source when partial timestamps of a contagion process are available. We formulate the source localization problem as a ranking problem on graphs, where infected nodes are ranked according to their likelihood of being the source. Two ranking algorithms, cost-based ranking (CR) and tree-based ranking (TR), are proposed in this paper. Experimental evaluations with synthetic and real-world data show that our algorithms significantly improve the ranking accuracy compared with four existing algorithms.
Binary Log-Linear Learning with Stochastic Communication Links
Venue: arXiv cs.MA 2014
Year: 2014

In this paper, we consider distributed decision-making over stochastic communication links in multi-agent systems. We show how to extend the current literature on potential games with binary log-linear learning (which mainly focuses on ideal communication links) to consider the impact of stochastic communication channels. More specifically, we derive conditions on the probability of link connectivity to achieve a target probability for the set of potential maximizers (in the stationary distribution). Furthermore, our toy example demonstrates a transition phenomenon for achieving any target probability for the set of potential maximizers.
What About Feedback?
Venue: arXiv cs.HC 2014
Year: 2014

The role of immediate feedback in-group conversations has received scant attention in the recent literature. While studies from the early 1990's suggested that "added information" in the form of non-verbal cues would allow video conferencing to "augment" the audio-only conference in terms of effectiveness, stunningly little follow-on research has been done reflective of the current state of computer mediated communication, video conferencing, "live walls", etc. This article contrasts three studies of immediate feedback in in-person settings as the basis for suggesting a new research program - research to look at potential effects of augmenting video-conferencing with an immediate feedback channel.
An Evaluation of Support Vector Machines as a Pattern Recognition Tool
Venue: arXiv cs.LG 2014
Year: 2014

The purpose of this report is in examining the generalization performance of Support Vector Machines (SVM) as a tool for pattern recognition and object classification. The work is motivated by the growing popularity of the method that is claimed to guarantee a good generalization performance for the task in hand. The method is implemented in MATLAB. SVMs based on various kernels are tested for classifying data from various domains.
On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint
Venue: arXiv cs.SY 2014
Year: 2014

We take a new look at the relation between the optimal transport problem and the Schrödinger bridge problem from the stochastic control perspective. We show that the connections are richer and deeper than described in existing literature. In particular: a) We give an elementary derivation of the Benamou-Brenier fluid dynamics version of the optimal transport problem; b) We provide a new fluid dynamics version of the Schrödinger bridge problem; c) We observe that the latter provides an important connection with optimal transport without zero noise limits; d) We propose and solve a fluid dynamic version of optimal transport with prior; e) We can then view optimal transport with prior as the zero noise limit of Schrödinger bridges when the prior is any Markovian evolution. In particular, we work out the Gaussian case. A numerical example of the latter convergence involving Brownian particles is also provided.
Highly Efficient Forward and Backward Propagation of Convolutional Neural Networks for Pixelwise Classification
Venue: arXiv cs.CV 2014
Year: 2014

We present highly efficient algorithms for performing forward and backward propagation of Convolutional Neural Network (CNN) for pixelwise classification on images. For pixelwise classification tasks, such as image segmentation and object detection, surrounding image patches are fed into CNN for predicting the classes of centered pixels via forward propagation and for updating CNN parameters via backward propagation. However, forward and backward propagation was originally designed for whole-image classification. Directly applying it to pixelwise classification in a patch-by-patch scanning manner is extremely inefficient, because surrounding patches of pixels have large overlaps, which lead to a lot of redundant computation. The proposed algorithms eliminate all the redundant computation in convolution and pooling on images by introducing novel d-regularly sparse kernels. It generates exactly the same results as those by patch-by-patch scanning. Convolution and pooling operations with such kernels are able to continuously access memory and can run efficiently on GPUs. A fraction of patches of interest can be chosen from each training image for backward propagation by applying a mask to the error map at the last CNN layer. Its computation complexity is constant with respect to the number of patches sampled from the image. Experiments have shown that our proposed algorithms speed up commonly used patch-by-patch scanning over 1500 times in both forward and backward propagation. The speedup increases with the sizes of images and patches.
Adaptive Mechanism for Distributed Opportunistic Scheduling
Venue: arXiv cs.NI 2014
Year: 2014

Distributed Opportunistic Scheduling (DOS) techniques have been recently proposed to improve the throughput performance of wireless networks. With DOS, each station contends for the channel with a certain access probability. If a contention is successful, the station measures the channel conditions and transmits in case the channel quality is above a certain threshold. Otherwise, the station does not use the transmission opportunity, allowing all stations to recontend. A key challenge with DOS is to design a distributed algorithm that optimally adjusts the access probability and the threshold of each station. To address this challenge, in this paper we first compute the configuration of these two parameters that jointly optimizes throughput performance in terms of proportional fairness. Then, we propose an adaptive algorithm based on control theory that converges to the desired point of operation. Finally, we conduct a control theoretic analysis of the algorithm to find a setting for its parameters that provides a good tradeoff between stability and speed of convergence. Simulation results validate the design of the proposed mechanism and confirm its advantages over previous proposals.
Towards Live Programming in ROS with PhaROS and LRP
Venue: arXiv cs.PL 2014
Year: 2014

In traditional robot behavior programming, the edit-compile-simulate-deploy-run cycle creates a large mental disconnect between program creation and eventual robot behavior. This significantly slows down behavior development because there is no immediate mental connection between the program and the resulting behavior. With live programming the development cycle is made extremely tight, realizing such an immediate connection. In our work on programming of ROS robots in a more dynamic fashion through PhaROS, we have experimented with the use of the Live Robot Programming language. This has given rise to a number of requirements for such live programming of robots. In this text we introduce these requirements and illustrate them using an example robot behavior.
Polynomial-Time Approximation Schemes for Circle and Other Packing Problems
Venue: arXiv cs.DS 2014
Year: 2014

We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+γ$, for some arbitrarily small number $γ> 0$. Our algorithm is polynomial on $\log 1/γ$, and thus $γ$ is part of the problem input. For the special case that $γ$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+γ$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the $L_p$-norm.