OpenRaiser/Intern-Atlas huggingface dataset:
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{Ω(\log \log n)}$. Our results extend the works of Nisan-Wigderson [NW95] (which showed superpolynomial lower bounds for homogeneous depth 3 circuits), Gupta-Kamath-Kayal-Saptharishi and Kayal-Saha-Saptharishi [GKKS13, KSS13] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded bottom fan-in), Kumar-Saraf [KS13a] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded top fan-in) and Raz-Yehudayoff and Fournier-Limaye-Malod-Srinivasan [RY08, FLMS13] (which showed superpolynomial lower bounds for multilinear depth 4 circuits). Several of these results in fact showed exponential lower bounds. The main ingredient in our proof is a new complexity measure of {\it bounded support} shifted partial derivatives. This measure allows us to prove exponential lower bounds for homogeneous depth 4 circuits where all the monomials computed at the bottom layer have {\it bounded support} (but possibly unbounded degree/fan-in), strengthening the results of Gupta et al and Kayal et al [GKKS13, KSS13]. This new lower bound combined with a careful "random restriction" procedure (that transforms general depth 4 homogeneous circuits to depth 4 circuits with bounded support) gives us our final result.
Occupancy Detection in Vehicles Using Fisher Vector Image Representation
Venue: arXiv cs.CV 2013
Year: 2013

Due to the high volume of traffic on modern roadways, transportation agencies have proposed High Occupancy Vehicle (HOV) lanes and High Occupancy Tolling (HOT) lanes to promote car pooling. However, enforcement of the rules of these lanes is currently performed by roadside enforcement officers using visual observation. Manual roadside enforcement is known to be inefficient, costly, potentially dangerous, and ultimately ineffective. Violation rates up to 50%-80% have been reported, while manual enforcement rates of less than 10% are typical. Therefore, there is a need for automated vehicle occupancy detection to support HOV/HOT lane enforcement. A key component of determining vehicle occupancy is to determine whether or not the vehicle's front passenger seat is occupied. In this paper, we examine two methods of determining vehicle front seat occupancy using a near infrared (NIR) camera system pointed at the vehicle's front windshield. The first method examines a state-of-the-art deformable part model (DPM) based face detection system that is robust to facial pose. The second method examines state-of- the-art local aggregation based image classification using bag-of-visual-words (BOW) and Fisher vectors (FV). A dataset of 3000 images was collected on a public roadway and is used to perform the comparison. From these experiments it is clear that the image classification approach is superior for this problem.
Crowdsourced bi-directional disaster reporting and alerting on smartphones in Lao PDR
Venue: arXiv cs.CY 2013
Year: 2013

Natural disasters are a large threat for people especially in developing countries such as Laos. ICT-based disaster management systems aim at supporting disaster warning and response efforts. However, the ability to directly communicate in both directions between local and administrative level is often not supported, and a tight integration into administrative workflows is missing. In this paper, we present the smartphone-based disaster and reporting system Mobile4D. It allows for bi-directional communication while being fully involved in administrative processes. We present the system setup and discuss integration into administrative structures in Lao PDR.
On the Semantics of Gringo
Venue: arXiv cs.AI 2013
Year: 2013

Input languages of answer set solvers are based on the mathematically simple concept of a stable model. But many useful constructs available in these languages, including local variables, conditional literals, and aggregates, cannot be easily explained in terms of stable models in the sense of the original definition of this concept and its straightforward generalizations. Manuals written by designers of answer set solvers usually explain such constructs using examples and informal comments that appeal to the user's intuition, without references to any precise semantics. We propose to approach the problem of defining the semantics of gringo programs by translating them into the language of infinitary propositional formulas. This semantics allows us to study equivalent transformations of gringo programs using natural deduction in infinitary propositional logic.
Abstract Modular Systems and Solvers
Venue: arXiv cs.AI 2013
Year: 2013

Integrating diverse formalisms into modular knowledge representation systems offers increased expressivity, modeling convenience and computational benefits. We introduce concepts of abstract modules and abstract modular systems to study general principles behind the design and analysis of model-finding programs, or solvers, for integrated heterogeneous multi-logic systems. We show how abstract modules and abstract modular systems give rise to transition systems, which are a natural and convenient representation of solvers pioneered by the SAT community. We illustrate our approach by showing how it applies to answer set programming and propositional logic, and to multi-logic systems based on these two formalisms.
GPU Asynchronous Stochastic Gradient Descent to Speed Up Neural Network Training
Venue: arXiv cs.CV 2013
Year: 2013

The ability to train large-scale neural networks has resulted in state-of-the-art performance in many areas of computer vision. These results have largely come from computational break throughs of two forms: model parallelism, e.g. GPU accelerated training, which has seen quick adoption in computer vision circles, and data parallelism, e.g. A-SGD, whose large scale has been used mostly in industry. We report early experiments with a system that makes use of both model parallelism and data parallelism, we call GPU A-SGD. We show using GPU A-SGD it is possible to speed up training of large convolutional neural networks useful for computer vision. We believe GPU A-SGD will make it possible to train larger networks on larger training sets in a reasonable amount of time.
Coverage Games for Testing Nondeterministic Systems
Venue: arXiv cs.SE 2013
Year: 2013

Modern software systems may exhibit a nondeterministic behavior due to many unpredictable factors. In this work, we propose the node coverage game, a two player turn-based game played on a finite game graph, as a formalization of the problem to test such systems. Each node in the graph represents a {\em functional equivalence class} of the software under test (SUT). One player, the tester, wants to maximize the node coverage, measured by the number of nodes visited when exploring the game graphs, while his opponent, the SUT, wants to minimize it. An optimal test would maximize the cover, and it is an interesting problem to find the maximal number of nodes that the tester can guarantee to visit, irrespective of the responses of the SUT. We show that the decision problem of whether the guarantee is less than a given number is NP-complete. Then we present techniques for testing nondeterministic SUTs with existing test suites for deterministic models. Finally, we report our implementation and experiments.
Exact Algorithms for Maximum Independent Set
Venue: arXiv cs.DS 2013
Year: 2013

We show that the maximum independent set problem (MIS) on an $n$-vertex graph can be solved in $1.1996^nn^{O(1)}$ time and polynomial space, which even is faster than Robson's $1.2109^{n}n^{O(1)}$-time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of $1.1893^nn^{O(1)}$ and $1.1970^nn^{O(1)}$, respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analyses on the structure of bounded-degree graphs.
Parallel architectures for fuzzy triadic similarity learning
Venue: arXiv cs.DC 2013
Year: 2013

In a context of document co-clustering, we define a new similarity measure which iteratively computes similarity while combining fuzzy sets in a three-partite graph. The fuzzy triadic similarity (FT-Sim) model can deal with uncertainty offers by the fuzzy sets. Moreover, with the development of the Web and the high availability of storage spaces, more and more documents become accessible. Documents can be provided from multiple sites and make similarity computation an expensive processing. This problem motivated us to use parallel computing. In this paper, we introduce parallel architectures which are able to treat large and multi-source data sets by a sequential, a merging or a splitting-based process. Then, we proceed to a local and a central (or global) computing using the basic FT-Sim measure. The idea behind these architectures is to reduce both time and space complexities thanks to parallel computation.
Some considerations about Java implementation of two provably secure pseudorandom bit generators
Venue: arXiv cs.CR 2013
Year: 2013

The quest for a cryptographically secure pseudorandom bit generator (PRBG) was initiated long ago, and for a long time the proposed pseudorandom generators were very slow. More recently some "provably secure" PRBG capable to achieve a throughput rate greater than 1Mbit/sec. We noticed, anyway, the absence of Java implementations of such PRBGs, provably due to poor expected values for throughput rate. In the present paper we show that it is quite easy to write down Java implementations for them, achieving a throughput rae into range $0,5÷7$ Mbit/sec on very common mobile low-end devices.
Coalgebraic Logic Programming: from Semantics to Implementation
Venue: arXiv cs.PL 2013
Year: 2013

Coinductive definitions, such as that of an infinite stream, may often be described by elegant logic programs, but ones for which SLD-refutation is of no value as SLD-derivations fall into infinite loops. Such definitions give rise to questions of lazy corecursive derivations and parallelism, as execution of such logic programs can have both recursive and corecursive features at once. Observational and coalgebraic semantics have been used to study them abstractly. The programming developments have often occurred separately and have usually been implementation-led. Here, we give a coherent semantics-led account of the issues, starting with abstract category theoretic semantics, developing coalgebra to characterise naturally arising trees, and proceeding towards implementation of a new dialect, CoALP, of logic programming, characterised by guarded lazy corecursion and parallelism.
Rounding Sum-of-Squares Relaxations
Venue: arXiv cs.DS 2013
Year: 2013

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector $v$ in the subspace satisfying $|v|_4^4 > c(k/d^{1/3}) |v|_2^2$, where $|v|_p = (E_i v_i^p)^{1/p}$. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted $μ$-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever $μ< O(\min(1,n/d^2))$, improving for $d < n^{2/3}$ prior methods which intrinsically required $μ< O(1/\sqrt(d))$.
Undecidability in binary tag systems and the Post correspondence problem for four pairs of words
Venue: arXiv cs.FL 2013
Year: 2013

Since Cocke and Minsky proved 2-tag systems universal, they have been extensively used to prove the universality of numerous computational models. Unfortunately, all known algorithms give universal 2-tag systems that have a large number of symbols. In this work, tag systems with only 2 symbols (the minimum possible) are proved universal via an intricate construction showing that they simulate cyclic tag systems. Our simulation algorithm has a polynomial time overhead, and thus shows that binary tag systems simulate Turing machines in polynomial time. We immediately find applications of our result. We reduce the halting problem for binary tag systems to the Post correspondence problem for 4 pairs of words. This improves on 7 pairs, the previous bound for undecidability in this problem. Following our result, only the case for 3 pairs of words remains open, as the problem is known to be decidable for 2 pairs. As a further application, we find that the matrix mortality problem is undecidable for sets with five $3\times 3$ matrices and for sets with two $15\times 15$ matrices. The previous bounds for the undecidability in this problem was seven $3\times 3$ matrices and two $ 21\times 21$ matrices.
Iterative Nearest Neighborhood Oversampling in Semisupervised Learning from Imbalanced Data
Venue: arXiv cs.LG 2013
Year: 2013

Transductive graph-based semi-supervised learning methods usually build an undirected graph utilizing both labeled and unlabeled samples as vertices. Those methods propagate label information of labeled samples to neighbors through their edges in order to get the predicted labels of unlabeled samples. Most popular semi-supervised learning approaches are sensitive to initial label distribution happened in imbalanced labeled datasets. The class boundary will be severely skewed by the majority classes in an imbalanced classification. In this paper, we proposed a simple and effective approach to alleviate the unfavorable influence of imbalance problem by iteratively selecting a few unlabeled samples and adding them into the minority classes to form a balanced labeled dataset for the learning methods afterwards. The experiments on UCI datasets and MNIST handwritten digits dataset showed that the proposed approach outperforms other existing state-of-art methods.
Deep learning for class-generic object detection
Venue: arXiv cs.CV 2013
Year: 2013

We investigate the use of deep neural networks for the novel task of class generic object detection. We show that neural networks originally designed for image recognition can be trained to detect objects within images, regardless of their class, including objects for which no bounding box labels have been provided. In addition, we show that bounding box labels yield a 1% performance increase on the ImageNet recognition challenge.
Deriving Latent Social Impulses to Determine Longevous Videos
Venue: arXiv cs.SI 2013
Year: 2013

Online video websites receive huge amount of videos daily from users all around the world. How to provide valuable recommendations to viewers is an important task for both video websites and related third parties, such as search engines. Previous work conducted numerous analysis on the view counts of videos, which measure a video's value in terms of popularity. However, the long-lasting value of an online video, namely longevity, is hidden behind the history that a video accumulates its "popularity" through time. Generally speaking, a longevous video tends to constantly draw society's attention. With focus on one of the leading video websites, Youtube, this paper proposes a scoring mechanism quantifying a video's longevity. Evaluating a video's longevity can not only improve a video recommender system, but also help us to discover videos having greater advertising value, as well as adjust a video website's strategy of storing videos to shorten its responding time. In order to accurately quantify longevity, we introduce the concept of latent social impulses and how to use them measure a video's longevity. In order to derive latent social impulses, we view the video website as a digital signal filter and formulate the task as a convex minimization problem. The proposed longevity computation is based on the derived social impulses. Unfortunately, the required information to derive social impulses are not always public, which makes a third party unable to directly evaluate every video's longevity. To solve this problem, we formulate a semi-supervised learning task by using part of videos having known longevity scores to predict the unknown longevity scores. We propose a Gaussian Random Markov model with Loopy Belief Propagation to solve this problem. The conducted experiments on Youtube demonstrate that the proposed method significantly improves the prediction results comparing to baselines.
The Application of Data Mining to Build Classification Model for Predicting Graduate Employment
Venue: arXiv cs.CY 2013
Year: 2013

Data mining has been applied in various areas because of its ability to rapidly analyze vast amounts of data. This study is to build the Graduates Employment Model using classification task in data mining, and to compare several of data-mining approaches such as Bayesian method and the Tree method. The Bayesian method includes 5 algorithms, including AODE, BayesNet, HNB, NaviveBayes, WAODE. The Tree method includes 5 algorithms, including BFTree, NBTree, REPTree, ID3, C4.5. The experiment uses a classification task in WEKA, and we compare the results of each algorithm, where several classification models were generated. To validate the generated model, the experiments were conducted using real data collected from graduate profile at the Maejo University in Thailand. The model is intended to be used for predicting whether a graduate was employed, unemployed, or in an undetermined situation.
Maximum Coverage and Maximum Connected Covering in Social Networks with Partial Topology Information
Venue: arXiv cs.SI 2013
Year: 2013

Viral marketing campaigns seek to recruit the most influential individuals to cover the largest target audience. This can be modeled as the well-studied maximum coverage problem. There is a related problem when the recruited nodes are connected. It is called the maximum connected cover problem. This problem ensures a strong coordination between the influential nodes which are the backbone of the marketing campaign. In this work, we are interested on both of these problems. Most of the related literature assumes knowledge about the topology of the network. Even in that case, the problem is known to be NP-hard. In this work, we propose heuristics to the maximum connected cover problem and the maximum coverage problem with different knowledge levels about the topology of the network. We quantify the difference between these heuristics and the local and global greedy algorithms.
Online Steiner Tree with Deletions
Venue: arXiv cs.DS 2013
Year: 2013

In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of $Θ(\log n)$ on the competitiveness is known. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can maintain a constant-competitive tree online. But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman had also considered this model, and it gave a greedy algorithm that maintained a constant-competitive tree online, and made at most $O(n^{3/2})$ edge changes for the first $n$ requests. In this paper give the following two results. Our first result is an online algorithm that maintains a Steiner tree only under deletions: we start off with a set of vertices, and at each time one of the vertices is removed from this set: our Steiner tree no longer has to span this vertex. We give an algorithm that changes only a constant number of edges upon each request, and maintains a constant-competitive tree at all times. Our algorithm uses the primal-dual framework and a global charging argument to carefully make these constant number of changes. We then study the natural greedy algorithm proposed by Imase and Waxman that maintains a constant-competitive Steiner tree in the fully-dynamic model (where each request either adds or deletes a vertex). Our second result shows that this algorithm makes only a constant number of changes per request in an amortized sense.
Simultaneous Perturbation Methods for Adaptive Labor Staffing in Service Systems
Venue: arXiv cs.SY 2013
Year: 2013

Service systems are labor intensive due to the large variation in the tasks required to address service requests from multiple customers. Aligning the staffing levels to the forecasted workloads adaptively in such systems is nontrivial because of a large number of parameters and operational variations leading to a huge search space. A challenging problem here is to optimize the staffing while maintaining the system in steady-state and compliant to aggregate service level agreement (SLA) constraints. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. We formulate this problem as a constrained Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA) based SASOC (Staff Allocation using Stochastic Optimization with Constraints) algorithms for solving the above problem. The algorithms include both first order as well as second order methods and incorporate SPSA based gradient estimates in the primal, with dual ascent for the Lagrange multipliers. Both the algorithms that we propose are online, incremental and easy to implement. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by SASOC algorithms onto the discrete set. We validated our algorithms on five real-life service systems and compared them with a state-of-the-art optimization tool-kit OptQuest. Being 25 times faster than OptQuest, our algorithms are particularly suitable for adaptive labor staffing. Also, we observe that our algorithms guarantee convergence and find better solutions than OptQuest in many cases.