OpenRaiser/Intern-Atlas huggingface dataset:
Discovering Human Interactions in Videos with Limited Data Labeling
Venue: arXiv cs.CV 2015
Year: 2015

We present a novel approach for discovering human interactions in videos. Activity understanding techniques usually require a large number of labeled examples, which are not available in many practical cases. Here, we focus on recovering semantically meaningful clusters of human-human and human-object interaction in an unsupervised fashion. A new iterative solution is introduced based on Maximum Margin Clustering (MMC), which also accepts user feedback to refine clusters. This is achieved by formulating the whole process as a unified constrained latent max-margin clustering problem. Extensive experiments have been carried out over three challenging datasets, Collective Activity, VIRAT, and UT-interaction. Empirical results demonstrate that the proposed algorithm can efficiently discover perfect semantic clusters of human interactions with only a small amount of labeling effort.
Further results on differentially 4-uniform permutations over $\F_{2^{2m}}$
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we present several new constructions of differentially 4-uniform permutations over $\F_{2^{2m}}$ by modifying the values of the inverse function on some subsets of $\F_{2^{2m}}$. The resulted differentially 4-uniform permutations have high nonlinearities and algebraic degrees, which provide more choices for the design of cryptographic substitution boxes.
A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields
Venue: arXiv cs.CC 2015
Year: 2015

In this note we show that unsatisfiable systems of linear equations with a constant number of variables per equation over prime finite fields have polynomial-size constant-degree semi-algebraic proofs of unsatisfiability. These are proofs that manipulate polynomial inequalities over the reals with variables ranging in $\{0,1\}$. This upper bound is to be put in contrast with the known fact that, for certain explicit systems of linear equations over the two-element field, such refutations require linear degree and exponential size if they are restricted to so-called static semi-algebraic proofs, and even tree-like semi-algebraic and sums-of-squares proofs. Our upper bound is a more or less direct translation of an argument due to Grigoriev, Hirsch and Pasechnik (Moscow Mathematical Journal, 2002) who did it for a family of linear systems of interest in propositional proof complexity. We point out that their method is more general and can be thought of as simulating Gaussian elimination.
Stakeholders, Viewpoints and Languages of a Modelling Framework for the Design and Development of Data-Intensive Mobile Apps
Venue: arXiv cs.SE 2015
Year: 2015

Today millions of mobile apps are downloaded and used all over the world. Guidelines and best practices on how to design and develop mobile apps are being periodically released, mainly by mobile platform vendors and researchers. They cover different concerns, and refer to different technical and non-technical stakeholders. Still, mobile applications are developed with ad-hoc development processes, and on-paper best practices. In this paper we discuss a multi-view modelling framework supporting the collaborative design and development of mobile apps. The proposed framework embraces the Model-Driven Engineering methodology. This paper provides an overall view of the modelling framework in terms of its main stakeholders, viewpoints, and modelling languages.
The Meaning of Attack-Resistant Systems
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, we introduce a formal notion of partial compliance, called Attack-resistance, of a computer program running together with a defense mechanism w.r.t a non-exploitability specification. In our setting, a program may contain exploitable vulnerabilities, such as buffer overflows, but appropriate defense mechanisms built into the program or the operating system render such vulnerabilities hard to exploit by certain attackers, usually relying on the strength of the randomness of a probabilistic transformation of the environment or the program and some knowledge on the attacker's goals and attack strategy. We are motivated by the reality that most large-scale programs have vulnerabilities despite our best efforts to get rid of them. Security researchers have responded to this state of affairs by coming up with ingenious defense mechanisms such as address space layout randomization (ASLR) or instruction set randomization (ISR) that provide some protection against exploitation. However, implementations of such mechanism have been often shown to be insecure, even against the attacks they were designed to prevent. By formalizing this notion of attack-resistance we pave the way towards addressing the questions: "How do we formally analyze defense mechanisms? Is there a mathematical way of distinguishing effective defense mechanisms from ineffective ones? Can we quantify and show that these defense mechanisms provide formal security guarantees, albeit partial, even in the presence of exploitable vulnerabilities?". To illustrate our approach we discuss under which circumstances ISR implementations comply with the Attack-resistance definition.
Building Nim
Venue: arXiv cs.DM 2015
Year: 2015

The game of nim, with its simple rules, its elegant solution and its historical importance is the quintessence of a combinatorial game, which is why it led to so many generalizations and modifications. We present a modification with a new spin: building nim. With given finite numbers of tokens and stacks, this two-player game is played in two stages (thus belonging to the same family of games as e.g. nine-men's morris): first building, where players alternate to put one token on one of the, initially empty, stacks until all tokens have been used. Then, the players play nim. Of course, because the solution for the game of nim is known, the goal of the player who starts nim play is a placement of the tokens so that the Nim-sum of the stack heights at the end of building is different from 0. This game is trivial if the total number of tokens is odd as the Nim-sum could never be 0, or if both the number of tokens and the number of stacks are even, since a simple mimicking strategy results in a Nim-sum of 0 after each of the second player's moves. We present the solution for this game for some non-trivial cases and state a general conjecture.
Evaluating Open Access Paper Repository In Higher Education For Asean Region
Venue: arXiv cs.DL 2015
Year: 2015

Paper repository at higher education is a collection of scientific articles created by the academic society. This study took as many as 80 universities in the Webometrics ranking of repositories in the Southeast Asia region. The tools used in this research is Google for number of web page and Google Scholar for number of document paper repository and Ahrefs for referring page, backlink and reffering domain. The result of this study, Eprints is the most widely used tools in higher education, as many as 37 higher educations (46,25%). Institut Teknologi Sepuluh November got the highest score in number of web page in Google (2.010.000), Bogor Agricultural University Scientific Repository got the highest score for number of document paper (44.300). University of Sumatera Utara Repository got the highest score for reffering page (82588) and backlink (86421). Universiti Teknologi Malaysia Institutional Repository got the highest score for reffering domain (532).
Structured Descriptions of Roles, Activities,and Procedures in the Roman Constitution
Venue: arXiv cs.DL 2015
Year: 2015

A highly structured description of entities and events in histories can support flexible exploration of those histories by users and, ultimately, support richly-linked full-text digital libraries. Here, we apply the Basic Formal Ontology (BFO) to structure a passage about the Roman Constitution from Gibbon's Decline and Fall of the Roman Empire. Specifically, we consider the specification of Roles such as Consuls, Activities associated with those Roles, and Procedures for accomplishing those Activities.
Non-Adaptive Learning a Hidden Hipergraph
Venue: arXiv cs.LG 2015
Year: 2015

We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraph that asks almost optimal number of queries.
Joint Optimization of Masks and Deep Recurrent Neural Networks for Monaural Source Separation
Venue: arXiv cs.SD 2015
Year: 2015

Monaural source separation is important for many real world applications. It is challenging because, with only a single channel of information available, without any constraints, an infinite number of solutions are possible. In this paper, we explore joint optimization of masking functions and deep recurrent neural networks for monaural source separation tasks, including monaural speech separation, monaural singing voice separation, and speech denoising. The joint optimization of the deep recurrent neural networks with an extra masking layer enforces a reconstruction constraint. Moreover, we explore a discriminative criterion for training neural networks to further enhance the separation performance. We evaluate the proposed system on the TSP, MIR-1K, and TIMIT datasets for speech separation, singing voice separation, and speech denoising tasks, respectively. Our approaches achieve 2.30--4.98 dB SDR gain compared to NMF models in the speech separation task, 2.30--2.48 dB GNSDR gain and 4.32--5.42 dB GSIR gain compared to existing models in the singing voice separation task, and outperform NMF and DNN baselines in the speech denoising task.
Width Hierarchy for k-OBDD of Small Width
Venue: arXiv cs.CC 2015
Year: 2015

In this paper was explored well known model k-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by k-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as k-OBDD and complexity properties of Boolean function SAF. This function is modification of known Pointer Jumping (PJ) and Indirect Storage Access (ISA) functions.
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
Venue: arXiv cs.DM 2015
Year: 2015

In the paper we consider the problem of scheduling $n$ identical jobs on 3 uniform machines with speeds $s_1, s_2,$ and $s_3$ to minimize the schedule length. We assume that jobs are subjected to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We show that if the graph is 2-chromatic then the problem can be solved in $O(n^2)$ time. If the graph is 3-chromatic, the problem becomes NP-hard even if $s_1>s_2=s_3$. However, in this case there exists a $4/3$-approximation algorithm running in $O(n^3)$ time. Moreover, this algorithm solves the problem almost surely to optimality if $3s_1/4 \leq s_2 = s_3$.
Supporting Instructors in Collaborating with Researchers using MOOClets
Venue: arXiv cs.CY 2015
Year: 2015

Most education and workplace learning takes place in classroom contexts far removed from laboratories or field sites with special arrangements for scientific research. But digital online resources provide a novel opportunity for large scale efforts to bridge the real world and laboratory settings which support data collection and randomized A/B experiments comparing different versions of content or interactions [2]. However, there are substantial technological and practical barriers in aligning instructors and researchers to use learning technologies like blended lessons/exercises & MOOCs as both a service for students and a realistic context to conduct research. This paper explains how the concept of a MOOClet can facilitate research-practitioner collaborations. MOOClets [3] are defined as modular components of a digital resource that can be implemented in technology to: (1) allow modification to create multiple versions, (2) allow experimental comparison and personalization of different versions, (3) reliably specify what data are collected. We suggest a framework in which instructors specify what kinds of changes to lessons, exercises, and emails they would be willing to adopt, and what data they will collect and make available. Researchers can then: (1) specify or design experiments that compare the effects of different versions on quantifiable outcomes. (2) Explore algorithms for maximizing particular outcomes by choosing alternative versions of a MOOClet based on the input variables available. We present a prototype survey tool for instructors intended to facilitate practitioner researcher matches and successful collaborations.
Hyperlinks embedded in Twitter as a proxy for total external inlinks to international university websites
Venue: arXiv cs.DL 2015
Year: 2015

This article analyzes Twitter as a potential alternative source of external links for use in webometric analysis because of its capacity to embed hyperlinks in different tweets. Given the limitations on searching Twitter's public API, we decided to use the Topsy search engine as a source for compiling tweets. To this end, we took a global sample of 200 universities and compiled all the tweets with hyperlinks to any of these institutions. Further link data was obtained from alternative sources (MajesticSEO and OpenSiteExplorer) in order to compare the results. Thereafter, various statistical tests were performed to determine the correlation between the indicators and the ability to predict external links from the collected tweets. The results indicate a high volume of tweets, although they are skewed by the presence and performance of specific universities and countries. The data provided by Topsy correlated significantly with all link indicators, particularly with OpenSiteExplorer (r=0.769). Finally, prediction models do not provide optimum results because of high error rates, which fall slightly in nonlinear models applied to specific environments. We conclude that the use of Twitter (via Topsy) as a source of hyperlinks to universities produces promising results due to its high correlation with link indicators, though limited by policies and culture regarding use and presence in social networks.
The robustness of democratic consensus
Venue: arXiv cs.SY 2015
Year: 2015

In linear models of consensus dynamics, the state of the various agents converges to a value which is a convex combination of the agents' initial states. We call it democratic if in the large scale limit (number of agents going to infinity) the vector of convex weights converges to 0 uniformly. Democracy is a relevant property which naturally shows up when we deal with opinion dynamic models and cooperative algorithms such as consensus over a network: it says that each agent's measure/opinion is going to play a negligeable role in the asymptotic behavior of the global system. It can be seen as a relaxation of average consensus, where all agents have exactly the same weight in the final value, which becomes negligible for a large number of agents.
Constrained Nonlinear Model Predictive Control of an MMA Polymerization Process via Evolutionary Optimization
Venue: arXiv cs.SY 2015
Year: 2015

In this work, a nonlinear model predictive controller is developed for a batch polymerization process. The physical model of the process is parameterized along a desired trajectory resulting in a trajectory linearized piecewise model (a multiple linear model bank) and the parameters are identified for an experimental polymerization reactor. Then, a multiple model adaptive predictive controller is designed for thermal trajectory tracking of the MMA polymerization. The input control signal to the process is constrained by the maximum thermal power provided by the heaters. The constrained optimization in the model predictive controller is solved via genetic algorithms to minimize a DMC cost function in each sampling interval.
WIKI THANKS: Cultural Differences in Thanks Network of Different-Language Wikipedias
Venue: arXiv cs.SI 2015
Year: 2015

Wikipedia introduced a new social function "wiki-thanks". "Wiki-thanks" enable editors to send thanks to other editors' contributions. In this paper, we aim to investigate this new social tool from different cultural perspectives. To achieve this goal, we analyze "wiki-thanks" log events and compared the English, German, Spanish, Chinese, Japanese, Korean, and Finish language Wikipedias.
Interface Transformation from Ruling to Obedience
Venue: arXiv cs.HC 2015
Year: 2015

This article is about one feature which was partly introduced 30 years ago with the development of multi windows operating systems. It is about the movability of screen objects not according to some predetermined algorithm but by the direct user action. Many years ago it was introduced on a very limited basis and nothing was improved since then. Smartphones and tablets give direct access to screen elements but on a very limited set of commands (scroll and zoom). There is an easy to use algorithm which turns any screen object into movable / resizable. This algorithm uses only mouse to turn screens of normal PCs into touchscreens, but this simple change means a revolution in our work with computers.
Two-Stage Document Length Normalization for Information Retrieval
Venue: arXiv cs.IR 2015
Year: 2015

The standard approach for term frequency normalization is based only on the document length. However, it does not distinguish the verbosity from the scope, these being the two main factors determining the document length. Because the verbosity and scope have largely different effects on the increase in term frequency, the standard approach can easily suffer from insufficient or excessive penalization depending on the specific type of long document. To overcome these problems, this paper proposes two-stage normalization by performing verbosity and scope normalization separately, and by employing different penalization functions. In verbosity normalization, each document is pre-normalized by dividing the term frequency by the verbosity of the document. In scope normalization, an existing retrieval model is applied in a straightforward manner to the pre-normalized document, finally leading us to formulate our proposed verbosity normalized (VN) retrieval model. Experimental results carried out on standard TREC collections demonstrate that the VN model leads to marginal but statistically significant improvements over standard retrieval models.
Optimal Cell Clustering and Activation for Energy Saving in Load-Coupled Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

Optimizing activation and deactivation of base station transmissions provides an instrument for improving energy efficiency in cellular networks. In this paper, we study optimal cell clustering and scheduling of activation duration for each cluster, with the objective of minimizing the sum energy, subject to a time constraint of delivering the users' traffic demand. The cells within a cluster are simultaneously in transmission and napping modes, with cluster activation and deactivation, respectively. Our optimization framework accounts for the coupling relation among cells due to the mutual interference. Thus, the users' achievable rates in a cell depend on the cluster composition. On the theoretical side, we provide mathematical formulation and structural characterization for the energy-efficient cell clustering and scheduling optimization problem, and prove its NP hardness. On the algorithmic side, we first show how column generation facilitates problem solving, and then present our notion of local enumeration as a flexible and effective means for dealing with the trade-off between optimality and the combinatorial nature of cluster formation, as well as for the purpose of gauging the deviation from optimality. Numerical results demonstrate that our solutions achieve more than 60% energy saving over existing schemes, and that the solutions we obtain are within a few percent of deviation from global optimum.
Locally Optimal Load Balancing
Venue: arXiv cs.DC 2015
Year: 2015

This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree $Δ$, and each node has up to $L$ units of load. The task is to distribute the load more evenly so that the loads of adjacent nodes differ by at most $1$. If the graph is a path ($Δ= 2$), it is easy to solve the fractional version of the problem in $O(L)$ communication rounds, independently of the number of nodes. We show that this is tight, and we show that it is possible to solve also the discrete version of the problem in $O(L)$ rounds in paths. For the general case ($Δ> 2$), we show that fractional load balancing can be solved in $\operatorname{poly}(L,Δ)$ rounds and discrete load balancing in $f(L,Δ)$ rounds for some function $f$, independently of the number of nodes.
Maximal Independent Sets in Generalised Caterpillar Graphs
Venue: arXiv cs.DS 2015
Year: 2015

A caterpillar graph is a tree which on removal of all its pendant vertices leaves a chordless path. The chordless path is called the backbone of the graph. The edges from the backbone to the pendant vertices are called the hairs of the caterpillar graph. Ortiz and Villanueva (C.Ortiz and M.Villanueva, Discrete Applied Mathematics, 160(3): 259-266, 2012) describe an algorithm, linear in the size of the output, for finding a family of maximal independent sets in a caterpillar graph. In this paper, we propose an algorithm, again linear in the output size, for a generalised caterpillar graph, where at each vertex of the backbone, there can be any number of hairs of length one and at most one hair of length two.
Image Specificity
Venue: arXiv cs.CV 2015
Year: 2015

For some images, descriptions written by multiple people are consistent with each other. But for other images, descriptions across people vary considerably. In other words, some images are specific $-$ they elicit consistent descriptions from different people $-$ while other images are ambiguous. Applications involving images and text can benefit from an understanding of which images are specific and which ones are ambiguous. For instance, consider text-based image retrieval. If a query description is moderately similar to the caption (or reference description) of an ambiguous image, that query may be considered a decent match to the image. But if the image is very specific, a moderate similarity between the query and the reference description may not be sufficient to retrieve the image. In this paper, we introduce the notion of image specificity. We present two mechanisms to measure specificity given multiple descriptions of an image: an automated measure and a measure that relies on human judgement. We analyze image specificity with respect to image content and properties to better understand what makes an image specific. We then train models to automatically predict the specificity of an image from image features alone without requiring textual descriptions of the image. Finally, we show that modeling image specificity leads to improvements in a text-based image retrieval application.