OpenRaiser/Intern-Atlas huggingface dataset:
Rapidly computable viscous friction and no-slip rigid contact models
Venue: arXiv cs.RO 2015
Year: 2015

This article presents computationally efficient algorithms for modeling two special cases of rigid contact---contact with only viscous friction and contact without slip---that have particularly useful applications in robotic locomotion and grasping. Modeling rigid contact with Coulomb friction generally exhibits $O(n^3)$ expected time complexity in the number of contact points and $2^{O(n)}$ worst-case complexity. The special cases we consider exhibit $O(m^3 + m^2n)$ time complexity ($m$ is the number of independent coordinates in the multi rigid body system) in the expected case and polynomial complexity in the worst case; thus, asymptotic complexity is no longer driven by number of contact points (which is conceivably limitless) but instead is more dependent on the number of bodies in the system (which is often fixed). These special cases also require considerably fewer constrained nonlinear optimization variables thus yielding substantial improvements in running time. Finally, these special cases also afford one other advantage: the nonlinear optimization problems are numerically easier to solve.
How to solve the cake-cutting problem in sublinear time
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we show algorithms for solving the cake-cutting problem in sublinear-time. More specifically, we preassign (simple) fair portions to o(n) players in o(n)-time, and minimize the damage to the rest of the players. All currently known algorithms require Omega(n)-time, even when assigning a portion to just one player, and it is nontrivial to revise these algorithms to run in $o(n)$-time since many of the remaining players, who have not been asked any queries, may not be satisfied with the remaining cake. To challenge this problem, we begin by providing a framework for solving the cake-cutting problem in sublinear-time. Generally speaking, solving a problem in sublinear-time requires the use of approximations. However, in our framework, we introduce the concept of "eps n-victims," which means that eps n players (victims) may not get fair portions, where 0< eps =< 1 is an arbitrary constant. In our framework, an algorithm consists of the following two parts: In the first (Preassigning) part, it distributes fair portions to r < n players in o(n)-time. In the second (Completion) part, it distributes fair portions to the remaining n-r players except for the eps n victims in poly}(n)-time. There are two variations on the r players in the first part. Specifically, whether they can or cannot be designated. We will then present algorithms in this framework. In particular, an O(r/eps)-time algorithm for r =< eps n/127 undesignated players with eps n-victims, and an O~(r^2/eps)-time algorithm for r =< eps e^{sqrt{ln{n}}/{7}} designated players and eps =< 1/e with eps n-victims are presented.
The complexity of computation in bit streams
Venue: arXiv cs.CC 2015
Year: 2015

We revisit the complexity of online computation in the cell probe model. We consider a class of problems where we are first given a fixed pattern or vector $F$ of $n$ symbols and then one symbol arrives at a time in a stream. After each symbol has arrived we must output some function of $F$ and the $n$-length suffix of the arriving stream. Cell probe bounds of $Ω(δ\lg{n}/w)$ have previously been shown for both convolution and Hamming distance in this setting, where $δ$ is the size of a symbol in bits and $w\inΩ(\lg{n})$ is the cell size in bits. However, when $δ$ is a constant, as it is in many natural situations, these previous results no longer give us non-trivial bounds. We introduce a new lop-sided information transfer proof technique which enables us to prove meaningful lower bounds even for constant size input alphabets. We use our new framework to prove an amortised cell probe lower bound of $Ω(\lg^2 n/(w\cdot \lg \lg n))$ time per arriving bit for an online version of a well studied problem known as pattern matching with address errors. This is the first non-trivial cell probe lower bound for any online problem on bit streams that still holds when the cell sizes are large. We also show the same bound for online convolution conditioned on a new combinatorial conjecture related to Toeplitz matrices.
The Shannon's mutual information of a multiple antenna time and frequency dependent channel: an ergodic operator approach
Venue: arXiv cs.IT 2015
Year: 2015

Consider a random non-centered multiple antenna radio transmission channel. Assume that the deterministic part of the channel is itself frequency selective, and that the random multipath part is represented by an ergodic stationary vector process. In the Hilbert space $l^2({\mathbb Z})$, one can associate to this channel a random ergodic self-adjoint operator having a so-called Integrated Density of States (IDS). Shannon's mutual information per receive antenna of this channel coincides then with the integral of a $\log$ function with respect to the IDS. In this paper, it is shown that when the numbers of antennas at the transmitter and at the receiver tend to infinity at the same rate, the mutual information per receive antenna tends to a quantity that can be identified and, in fact, is closely related to that obtained within the random matrix approach. This result can be obtained by analyzing the behavior of the Stieltjes transform of the IDS in the regime of the large numbers of antennas.
Convex Denoising using Non-Convex Tight Frame Regularization
Venue: arXiv cs.CV 2015
Year: 2015

This paper considers the problem of signal denoising using a sparse tight-frame analysis prior. The L1 norm has been extensively used as a regularizer to promote sparsity; however, it tends to under-estimate non-zero values of the underlying signal. To more accurately estimate non-zero values, we propose the use of a non-convex regularizer, chosen so as to ensure convexity of the objective function. The convexity of the objective function is ensured by constraining the parameter of the non-convex penalty. We use ADMM to obtain a solution and show how to guarantee that ADMM converges to the global optimum of the objective function. We illustrate the proposed method for 1D and 2D signal denoising.
Managing Multi-Granular Linguistic Distribution Assessments in Large-Scale Multi-Attribute Group Decision Making
Venue: arXiv cs.AI 2015
Year: 2015

Linguistic large-scale group decision making (LGDM) problems are more and more common nowadays. In such problems a large group of decision makers are involved in the decision process and elicit linguistic information that are usually assessed in different linguistic scales with diverse granularity because of decision makers' distinct knowledge and background. To keep maximum information in initial stages of the linguistic LGDM problems, the use of multi-granular linguistic distribution assessments seems a suitable choice, however to manage such multigranular linguistic distribution assessments, it is necessary the development of a new linguistic computational approach. In this paper it is proposed a novel computational model based on the use of extended linguistic hierarchies, which not only can be used to operate with multi-granular linguistic distribution assessments, but also can provide interpretable linguistic results to decision makers. Based on this new linguistic computational model, an approach to linguistic large-scale multi-attribute group decision making is proposed and applied to a talent selection process in universities.
On the Total-Power Capacity of Regular-LDPC Codes with Iterative Message-Passing Decoders
Venue: arXiv cs.IT 2015
Year: 2015

Motivated by recently derived fundamental limits on total (transmit + decoding) power for coded communication with VLSI decoders, this paper investigates the scaling behavior of the minimum total power needed to communicate over AWGN channels as the target bit-error-probability tends to zero. We focus on regular-LDPC codes and iterative message-passing decoders. We analyze scaling behavior under two VLSI complexity models of decoding. One model abstracts power consumed in processing elements ("node model"), and another abstracts power consumed in wires which connect the processing elements ("wire model"). We prove that a coding strategy using regular-LDPC codes with Gallager-B decoding achieves order-optimal scaling of total power under the node model. However, we also prove that regular-LDPC codes and iterative message-passing decoders cannot meet existing fundamental limits on total power under the wire model. Further, if the transmit energy-per-bit is bounded, total power grows at a rate that is worse than uncoded transmission. Complementing our theoretical results, we develop detailed physical models of decoding implementations using post-layout circuit simulations. Our theoretical and numerical results show that approaching fundamental limits on total power requires increasing the complexity of both the code design and the corresponding decoding algorithm as communication distance is increased or error-probability is lowered.
Preprint A Game Based Assistive Tool for Rehabilitation of Dysphonic Patients
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on 3rd International Workshop on Virtual and Augmented Assistive Technology (VAAT) at IEEE Virtual Reality 2015 (VR2015). An assistive training tool for rehabilitation of dysphonic patients is designed and developed according to the practical clinical needs. The assistive tool employs a space flight game as the attractive logic part, and microphone arrays as input device, which is getting rid of ambient noise by setting a specific orientation. The therapist can guide the patient to play the game as well as the voice training simultaneously side by side, while not interfere the patient voice. The voice information can be recorded and extracted for evaluating the long-time rehabilitation progress. This paper outlines a design science approach for the development of an initial useful software prototype of such a tool, considering 'Intuitive', 'Entertainment', 'Incentive' as main design factors.
3D visual analysis of seabed on smartphone
Venue: arXiv cs.HC 2015
Year: 2015

We create a 'virtual-seabed' platform to realize the 3D visual analysis of seabed on smartphone. The 3D seabed platform is based on a 'section-drilling' model, implementing visualization and analysis of the integrated data of seabed on the 3D browser on smartphone. Some 3D visual analysis functions are developed. This work presents a thorough and interesting way of presenting seabed data on smartphone, which raises many application possibilities. This platform is another practical proof based on our WebVRGIS platform.
Pricing Online Decisions: Beyond Auctions
Venue: arXiv cs.GT 2015
Year: 2015

We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforceable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the $k$-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially.
CRT and Fixed Patterns in Combinatorial Sequences
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, new context of Chinese Remainder Theorem (CRT) based analysis of combinatorial sequence generators has been presented. CRT is exploited to establish fixed patterns in LFSR sequences and underlying cyclic structures of finite fields. New methodology of direct computations of DFT spectral points in higher finite fields from known DFT spectra points of smaller constituent fields is also introduced. Novel approach of CRT based structural analysis of LFSR based combinatorial sequence is given both in time and frequency domain. The proposed approach is demonstrated on some examples of combiner generators and is scalable to general configuration of combiner generators.
Coloring tournaments with forbidden substructures
Venue: arXiv cs.DM 2015
Year: 2015

Coloring graphs is an important algorithmic problem in combinatorics with many applications in computer science. In this paper we study coloring tournaments. A chromatic number of a random tournament is of order $Ω(\frac{n}{\log(n)})$. The question arises whether the chromatic number can be proven to be smaller for more structured nontrivial classes of tournaments. We analyze the class of tournaments defined by a forbidden subtournament $H$. This paper gives a first quasi-polynomial algorithm running in time $e^{O(\log(n)^{2})}$ that constructs colorings of $H$-free tournaments using only $O(n^{1-ε(H)}\log(n))$ colors, where $ε(H) \geq 2^{-2^{50|H|^{2}+1}}$ for many forbidden tournaments $H$. To the best of our knowledge all previously known related results required at least sub-exponential time and relied on the regularity lemma. Since we do not use the regularity lemma, we obtain the first known lower bounds on $ε(H)$ that can be given by a closed-form expression. As a corollary, we give a constructive proof of the celebrated open Erdős-Hajnal conjecture with explicitly given lower bounds on the EH coefficients for all classes of prime tournaments for which the conjecture is known. Such a constractive proof was not known before. Thus we significantly reduce the gap between best lower and upper bounds on the EH coefficients from the conjecture for all known prime tournaments that satisfy it. We also briefly explain how our methods may be used for coloring $H$-free tournaments under the following conditions: $H$ is any tournament with $\leq 5$ vertices or: $H$ is any but one tournament of six vertices.
Discriminative and Efficient Label Propagation on Complementary Graphs for Multi-Object Tracking
Venue: arXiv cs.CV 2015
Year: 2015

Given a set of detections, detected at each time instant independently, we investigate how to associate them across time. This is done by propagating labels on a set of graphs, each graph capturing how either the spatio-temporal or the appearance cues promote the assignment of identical or distinct labels to a pair of detections. The graph construction is motivated by a locally linear embedding of the detection features. Interestingly, the neighborhood of a node in appearance graph is defined to include all the nodes for which the appearance feature is available (even if they are temporally distant). This gives our framework the uncommon ability to exploit the appearance features that are available only sporadically. Once the graphs have been defined, multi-object tracking is formulated as the problem of finding a label assignment that is consistent with the constraints captured each graph, which results into a difference of convex (DC) program. We propose to decompose the global objective function into node-wise sub-problems. This not only allows a computationally efficient solution, but also supports an incremental and scalable construction of the graph, thereby making the framework applicable to large graphs and practical tracking scenarios. Moreover, it opens the possibility of parallel implementation.
Dual Decomposition from the Perspective of Relax, Compensate and then Recover
Venue: arXiv cs.AI 2015
Year: 2015

Relax, Compensate and then Recover (RCR) is a paradigm for approximate inference in probabilistic graphical models that has previously provided theoretical and practical insights on iterative belief propagation and some of its generalizations. In this paper, we characterize the technique of dual decomposition in the terms of RCR, viewing it as a specific way to compensate for relaxed equivalence constraints. Among other insights gathered from this perspective, we propose novel heuristics for recovering relaxed equivalence constraints with the goal of incrementally tightening dual decomposition approximations, all the way to reaching exact solutions. We also show empirically that recovering equivalence constraints can sometimes tighten the corresponding approximation (and obtaining exact results), without increasing much the complexity of inference.
Reproducibility as a Technical Specification
Venue: arXiv cs.CE 2015
Year: 2015

Reproducibility of computationally-derived scientific discoveries should be a certainty. As the product of several person-years' worth of effort, results -- whether disseminated through academic journals, conferences or exploited through commercial ventures -- should at some level be expected to be repeatable by other researchers. While this stance may appear to be obvious and trivial, a variety of factors often stand in the way of making it commonplace. Whilst there has been detailed cross-disciplinary discussions of the various social, cultural and ideological drivers and (potential) solutions, one factor which has had less focus is the concept of reproducibility as a technical challenge. Specifically, that the definition of an unambiguous and measurable standard of reproducibility would offer a significant benefit to the wider computational science community. In this paper, we propose a high-level technical specification for a service for reproducibility, presenting cyberinfrastructure and associated workflow for a service which would enable such a specification to be verified and validated. In addition to addressing a pressing need for the scientific community, we further speculate on the potential contribution to the wider software development community of services which automate de novo compilation and testing of code from source. We illustrate our proposed specification and workflow by using the BioModelAnalyzer tool as a running example.
Totally Corrective Boosting with Cardinality Penalization
Venue: arXiv cs.LG 2015
Year: 2015

We propose a totally corrective boosting algorithm with explicit cardinality regularization. The resulting combinatorial optimization problems are not known to be efficiently solvable with existing classical methods, but emerging quantum optimization technology gives hope for achieving sparser models in practice. In order to demonstrate the utility of our algorithm, we use a distributed classical heuristic optimizer as a stand-in for quantum hardware. Even though this evaluation methodology incurs large time and resource costs on classical computing machinery, it allows us to gauge the potential gains in generalization performance and sparsity of the resulting boosted ensembles. Our experimental results on public data sets commonly used for benchmarking of boosting algorithms decidedly demonstrate the existence of such advantages. If actual quantum optimization were to be used with this algorithm in the future, we would expect equivalent or superior results at much smaller time and energy costs during training. Moreover, studying cardinality-penalized boosting also sheds light on why unregularized boosting algorithms with early stopping often yield better results than their counterparts with explicit convex regularization: Early stopping performs suboptimal cardinality regularization. The results that we present here indicate it is beneficial to explicitly solve the combinatorial problem still left open at early termination.
A Complete Worst-Case Analysis of Heapsort with Experimental Verification of Its Results, A manuscript (MS)
Venue: arXiv cs.DS 2015
Year: 2015

A rigorous proof is presented that the number of comparisons of keys performed in the worst case by ${\tt Heapsort}$ on any array of size $N \geq 2$ is equal to: $ 2 (N-1)\, ( \, \lg \frac{N-1}{2} +\varepsilon \, ) - 2s_2(N) - e_2(N) + \min (\lfloor \lg (N-1) \rfloor, 2) + 6 + c, $ where $ \varepsilon $, given by: $\varepsilon = 1 + \lceil \lg \, (N-1) \rceil - \lg \, (N-1) - 2^{\lceil \lg \, (N-1) \rceil - \lg \, (N-1)} ,$ is a function of $ N $ with the minimum value 0 and and the supremum value $δ= 1 - \lg e + \lg \lg e \approx 0.0860713320559342$, $s_2(N)$ is the sum of all digits of the binary representation of $N$, $e_2(N)$ is the exponent of $2$ in the prime factorization of $N$, and $ c $ is a binary function on the set of integers defined by: $c = 1$, if $N \leq 2 ^{\lceil \lg N \rceil} - 4$, and $c = 0$, otherwise. An algorithm that generates worst-case input arrays of any size $ N \geq 2 $ for ${\tt Heapsort}$ is offered. The algorithm has been implemented in Java, runs in $O( N \log N )$ time, and allows for precise experimental verification of the above formula.
Security Toolbox for Detecting Novel and Sophisticated Android Malware
Venue: arXiv cs.CR 2015
Year: 2015

This paper presents a demo of our Security Toolbox to detect novel malware in Android apps. This Toolbox is developed through our recent research project funded by the DARPA Automated Program Analysis for Cybersecurity (APAC) project. The adversarial challenge ("Red") teams in the DARPA APAC program are tasked with designing sophisticated malware to test the bounds of malware detection technology being developed by the research and development ("Blue") teams. Our research group, a Blue team in the DARPA APAC program, proposed a "human-in-the-loop program analysis" approach to detect malware given the source or Java bytecode for an Android app. Our malware detection apparatus consists of two components: a general-purpose program analysis platform called Atlas, and a Security Toolbox built on the Atlas platform. This paper describes the major design goals, the Toolbox components to achieve the goals, and the workflow for auditing Android apps. The accompanying video (http://youtu.be/WhcoAX3HiNU) illustrates features of the Toolbox through a live audit.
Tensor machines for learning target-specific polynomial features
Venue: arXiv cs.LG 2015
Year: 2015

Recent years have demonstrated that using random feature maps can significantly decrease the training and testing times of kernel-based algorithms without significantly lowering their accuracy. Regrettably, because random features are target-agnostic, typically thousands of such features are necessary to achieve acceptable accuracies. In this work, we consider the problem of learning a small number of explicit polynomial features. Our approach, named Tensor Machines, finds a parsimonious set of features by optimizing over the hypothesis class introduced by Kar and Karnick for random feature maps in a target-specific manner. Exploiting a natural connection between polynomials and tensors, we provide bounds on the generalization error of Tensor Machines. Empirically, Tensor Machines behave favorably on several real-world datasets compared to other state-of-the-art techniques for learning polynomial features, and deliver significantly more parsimonious models.