OpenRaiser/Intern-Atlas huggingface dataset:
Computing Minimal Sets on Propositional Formulae I: Problems & Reductions
Venue: arXiv cs.LO 2014
Year: 2014

Boolean Satisfiability (SAT) is arguably the archetypical NP-complete decision problem. Progress in SAT solving algorithms has motivated an ever increasing number of practical applications in recent years. However, many practical uses of SAT involve solving function as opposed to decision problems. Concrete examples include computing minimal unsatisfiable subsets, minimal correction subsets, prime implicates and implicants, minimal models, backbone literals, and autarkies, among several others. In most cases, solving a function problem requires a number of adaptive or non-adaptive calls to a SAT solver. Given the computational complexity of SAT, it is therefore important to develop algorithms that either require the smallest possible number of calls to the SAT solver, or that involve simpler instances. This paper addresses a number of representative function problems defined on Boolean formulas, and shows that all these function problems can be reduced to a generic problem of computing a minimal set subject to a monotone predicate. This problem is referred to as the Minimal Set over Monotone Predicate (MSMP) problem. This exercise provides new ways for solving well-known function problems, including prime implicates, minimal correction subsets, backbone literals, independent variables and autarkies, among several others. Moreover, this exercise motivates the development of more efficient algorithms for the MSMP problem. Finally the paper outlines a number of areas of future research related with extensions of the MSMP problem.
Event Structure of Transitive Verb: A MARVS perspective
Venue: arXiv cs.CL 2014
Year: 2014

Module-Attribute Representation of Verbal Semantics (MARVS) is a theory of the representation of verbal semantics that is based on Mandarin Chinese data (Huang et al. 2000). In the MARVS theory, there are two different types of modules: Event Structure Modules and Role Modules. There are also two sets of attributes: Event-Internal Attributes and Role-Internal Attributes, which are linked to the Event Structure Module and the Role Module, respectively. In this study, we focus on four transitive verbs as chi1(eat), wan2(play), huan4(change) and shao1(burn) and explore their event structures by the MARVS theory.
Squeezing bottlenecks: exploring the limits of autoencoder semantic representation capabilities
Venue: arXiv cs.IR 2014
Year: 2014

We present a comprehensive study on the use of autoencoders for modelling text data, in which (differently from previous studies) we focus our attention on the following issues: i) we explore the suitability of two different models bDA and rsDA for constructing deep autoencoders for text data at the sentence level; ii) we propose and evaluate two novel metrics for better assessing the text-reconstruction capabilities of autoencoders; and iii) we propose an automatic method to find the critical bottleneck dimensionality for text language representations (below which structural information is lost).
Weak $ω$-Regular Trace Languages
Venue: arXiv cs.FL 2014
Year: 2014

Mazurkiewicz traces describe concurrent behaviors of distributed systems. Trace-closed word languages, which are "linearizations" of trace languages, constitute a weaker notion of concurrency but still give us tools to investigate the latter. In this vein, our contribution is twofold. Firstly, we develop definitions that allow classification of $ω$-regular trace languages in terms of the corresponding trace-closed $ω$-regular word languages, capturing E-recognizable (reachability) and (deterministically) Büchi recognizable languages. Secondly, we demonstrate the first automata-theoretic result that shows the equivalence of $ω$-regular trace-closed word languages and Boolean combinations of deterministically $I$-diamond Büchi recognizable trace-closed languages.
Proceedings of the 1st Workshop on Robotics Challenges and Vision (RCV2013)
Venue: arXiv cs.RO 2014
Year: 2014

Proceedings of the 1st Workshop on Robotics Challenges and Vision (RCV2013)
Market-Based Power Allocation for a Differentially Priced FDMA System
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the problem of differential pricing and QoS assignment by a broadband data provider. In our model, the broadband data provider decides on the power allocated to an end-user not only based on parameters of the transmission medium, but also based on the price the user is willing to pay. In addition, end-users bid the price that they are willing to pay to the BTS based on their channel condition, the throughput they require, and their belief about other users' parameters. We will characterize the optimum power allocation by the BTS which turns out to be a modification of the solution to the well-known water-filling problem. We also characterize the optimum bidding strategy of end-users using the belief of each user about the cell condition.
Real-Time Notification for Resource Synchronization
Venue: arXiv cs.DC 2014
Year: 2014

Web applications frequently leverage resources made available by remote web servers. As resources are created, updated, deleted, or moved, these applications face challenges to remain in lockstep with the server's change dynamics. Several approaches exist to help meet this challenge for use cases where "good enough" synchronization is acceptable. But when strict resource coverage or low synchronization latency is required, commonly accepted Web-based solutions remain elusive. This paper details characteristics of an approach that aims at decreasing synchronization latency while maintaining desired levels of accuracy. The approach builds on pushing change notifications and pulling changed resources and it is explored with an experiment based on a DBpedia Live instance.
Constant Rank Bimatrix Games are PPAD-hard
Venue: arXiv cs.GT 2014
Year: 2014

The rank of a bimatrix game (A,B) is defined as rank(A+B). Computing a Nash equilibrium (NE) of a rank-$0$, i.e., zero-sum game is equivalent to linear programming (von Neumann'28, Dantzig'51). In 2005, Kannan and Theobald gave an FPTAS for constant rank games, and asked if there exists a polynomial time algorithm to compute an exact NE. Adsul et al. (2011) answered this question affirmatively for rank-$1$ games, leaving rank-2 and beyond unresolved. In this paper we show that NE computation in games with rank $\ge 3$, is PPAD-hard, settling a decade long open problem. Interestingly, this is the first instance that a problem with an FPTAS turns out to be PPAD-hard. Our reduction bypasses graphical games and game gadgets, and provides a simpler proof of PPAD-hardness for NE computation in bimatrix games. In addition, we get: * An equivalence between 2D-Linear-FIXP and PPAD, improving a result by Etessami and Yannakakis (2007) on equivalence between Linear-FIXP and PPAD. * NE computation in a bimatrix game with convex set of Nash equilibria is as hard as solving a simple stochastic game. * Computing a symmetric NE of a symmetric bimatrix game with rank $\ge 6$ is PPAD-hard. * Computing a (1/poly(n))-approximate fixed-point of a (Linear-FIXP) piecewise-linear function is PPAD-hard. The status of rank-$2$ games remains unresolved.
Interleaved entropy coders
Venue: arXiv cs.IT 2014
Year: 2014

The ANS family of arithmetic coders developed by Jarek Duda has the unique property that encoder and decoder are completely symmetric in the sense that a decoder reading bits will be in the exact same state that the encoder was in when writing those bits---all "buffering" of information is explicitly part of the coder state and identical between encoder and decoder. As a consequence, the output from multiple ABS/ANS coders can be interleaved into the same bitstream without any additional metadata. This allows for very efficient encoding and decoding on CPUs supporting superscalar execution or SIMD instructions, as well as GPU implementations. We also show how interleaving without additional metadata can be implemented for any entropy coder, at some increase in encoder complexity.
Designing an Ontology for the Data Documentation Initiative
Venue: arXiv cs.IR 2014
Year: 2014

An ontology of the DDI 3 data model will be designed by following the ontology engineering methodology to be evolved based on state-of-the-art methodologies. Hence DDI 3 data and metadata can be represented in form of a standard web interchange format RDF and processed by highly available RDF tools. As a consequence the DDI community has the possibility to publish and link LOD data sets to become part of the LOD cloud.
Constructing (Bi)Similar Finite State Abstractions using Asynchronous $l$-Complete Approximations
Venue: arXiv cs.SY 2014
Year: 2014

This paper constructs a finite state abstraction of a possibly continuous-time and infinite state model in two steps. First, a finite external signal space is added, generating a so called $Φ$-dynamical system. Secondly, the strongest asynchronous $l$-complete approximation of the external dynamics is constructed. As our main results, we show that (i) the abstraction simulates the original system, and (ii) bisimilarity between the original system and its abstraction holds, if and only if the original system is $l$-complete and its state space satisfies an additional property.
Improving Streaming Video Segmentation with Early and Mid-Level Visual Processing
Venue: arXiv cs.CV 2014
Year: 2014

Despite recent advances in video segmentation, many opportunities remain to improve it using a variety of low and mid-level visual cues. We propose improvements to the leading streaming graph-based hierarchical video segmentation (streamGBH) method based on early and mid level visual processing. The extensive experimental analysis of our approach validates the improvement of hierarchical supervoxel representation by incorporating motion and color with effective filtering. We also pose and illuminate some open questions towards intermediate level video analysis as further extension to streamGBH. We exploit the supervoxels as an initialization towards estimation of dominant affine motion regions, followed by merging of such motion regions in order to hierarchically segment a video in a novel motion-segmentation framework which aims at subsequent applications such as foreground recognition.
Privately Solving Linear Programs
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we initiate the systematic study of solving linear programs under differential privacy. The first step is simply to define the problem: to this end, we introduce several natural classes of private linear programs that capture different ways sensitive data can be incorporated into a linear program. For each class of linear programs we give an efficient, differentially private solver based on the multiplicative weights framework, or we give an impossibility result.
Simulating urban expansion in the parcel level for all Chinese cities
Venue: arXiv cs.MA 2014
Year: 2014

Large-scale models are generally associated with big modelling units in space, like counties or super grids (several to dozens km2). Few applied urban models can pursue large-scale extent with fine-level units simultaneously due to data availability and computation load. The framework of automatic identification and characterization parcels developed by Long and Liu (2013) makes such an ideal model possible by establishing existing urban parcels using road networks and points of interest for a super large area (like a country or a continent). In this study, a mega-vector-parcels cellular automata model (MVP-CA) is developed for simulating urban expansion in the parcel level for all 654 Chinese cities. Existing urban parcels in 2012, for initiating MVP-CA, are generated using multi-levelled road networks and ubiquitous points of interest, followed by simulating parcel-based urban expansion of all cities during 2012-2017. Reflecting national spatial development strategies discussed extensively by academics and decision makers, the baseline scenario and other two simulated urban expansion scenarios have been tested and compared horizontally. As the first fine-scale urban expansion model from the national scope, its academic contributions, practical applications, and potential biases are discussed in this paper as well.
Turing degrees of limit sets of cellular automata
Venue: arXiv cs.FL 2014
Year: 2014

Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of preimages. It is well known that these always contain a computable point and that any non-trivial property on them is undecidable. We go one step further in this article by giving a full characterization of the sets of Turing degrees of cellular automata: they are the same as the sets of Turing degrees of effectively closed sets containing a computable point.
Toward Resilient Algorithms and Applications
Venue: arXiv cs.MS 2014
Year: 2014

Over the past decade, the high performance computing community has become increasingly concerned that preserving the reliable, digital machine model will become too costly or infeasible. In this paper we discuss four approaches for developing new algorithms that are resilient to hard and soft failures.
FTVd is beyond Fast Total Variation regularized Deconvolution
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we revisit the "FTVd" algorithm for Fast Total Variation Regularized Deconvolution, which has been widely used in the past few years. Both its original version implemented in the MATLAB software FTVd 3.0 and its related variant implemented in the latter version FTVd 4.0 are considered \cite{Wang08FTVdsoftware}. We propose that the intermediate results during the iterations are the solutions of a series of combined Tikhonov and total variation regularized image deconvolution models and therefore some of them often have even better image quality than the final solution, which is corresponding to the pure total variation regularized model.
A GRASS GIS parallel module for radio-propagation predictions
Venue: arXiv cs.DC 2014
Year: 2014

Geographical information systems are ideal candidates for the application of parallel programming techniques, mainly because they usually handle large data sets. To help us deal with complex calculations over such data sets, we investigated the performance constraints of a classic master-worker parallel paradigm over a message-passing communication model. To this end, we present a new approach that employs an external database in order to improve the calculation/communication overlap, thus reducing the idle times for the worker processes. The presented approach is implemented as part of a parallel radio-coverage prediction tool for the GRASS environment. The prediction calculation employs digital elevation models and land-usage data in order to analyze the radio coverage of a geographical area. We provide an extended analysis of the experimental results, which are based on real data from an LTE network currently deployed in Slovenia. Based on the results of the experiments, which were performed on a computer cluster, the new approach exhibits better scalability than the traditional master-worker approach. We successfully tackled real-world data sets, while greatly reducing the processing time and saturating the hardware utilization.
The Short-term Memory (D.C. Response) of the Memristor Demonstrates the Causes of the Memristor Frequency Effect
Venue: arXiv cs.ET 2014
Year: 2014

A memristor is often identified by showing its distinctive pinched hysteresis curve and testing for the effect of frequency. The hysteresis size should relate to frequency and shrink to zero as the frequency approaches infinity. Although mathematically understood, the material causes for this are not well known. The d.c. response of the memristor is a decaying curve with its own timescale. We show via mathematical reasoning that this decaying curve when transformed to a.c. leads to the frequency effect by considering a descretized curve. We then demonstrate the validity of this approach with experimental data from two different types of memristors.
First steps to Virtual Mammography: Simulating external compressions of the breast with the Surface Evolver
Venue: arXiv cs.CE 2014
Year: 2014

In this paper we introduce a computational modelling that reproduces the breast compression processes used to obtain the mammogram. The main result is a programme in which one can track the first steps of virtual mammography. On the one hand, our modelling enables addition of structures that represent different tissues, muscles and glands in the breast. On the other hand, we shall validate and implement it by means of laboratory tests with phantoms. To the best of our knowledge, these two characteristics do confer originality to our research. This is because their interrelation seems not to be properly established elsewhere yet. We conclude that our model reproduces the same shapes and measurements really taken from the volunteer's breasts.
Morphological filtering on hypergraphs
Venue: arXiv cs.DM 2014
Year: 2014

The focus of this article is to develop computationally efficient mathematical morphology operators on hypergraphs. To this aim we consider lattice structures on hypergraphs on which we build morphological operators. We develop a pair of dual adjunctions between the vertex set and the hyper edge set of a hypergraph H, by defining a vertex-hyperedge correspondence. This allows us to recover the classical notion of a dilation/erosion of a subset of vertices and to extend it to subhypergraphs of H. Afterward, we propose several new openings, closings, granulometries and alternate sequential filters acting (i) on the subsets of the vertex and hyperedge set of H and (ii) on the subhypergraphs of a hypergraph.
A note on groups of a family of hyperbolic tessellations
Venue: arXiv cs.FL 2014
Year: 2014

In this paper we study the word problem of groups corresponding to tessellations of the hyperbolic plane. In particular using the Fibonacci technology developed by the second author we show that groups corresponding to the pentagrid or the heptagrid are not automatic.
A Novel Approach for Canvas Accessibility Problem in HTML5
Venue: arXiv cs.HC 2014
Year: 2014

Canvas is a pixel-based inherently inaccessible element in HTML5.Therefore web users with vision disabilities cannot benefit from Canvas and its desired semantics and functionality. Regarding to the Canvas application in designing interactive graphical user interface, vision-impaired users may miss important information on web sites. This paper utilizes the content-based image retrieval (CBIR) technique as well as code mapping embedded in a Firefox extension to present a novel approach in order to make Canvas interactive user interface accessible. This extension replaces Canvas with an accessible equivalent HTML environment. Unlike previously done works on Canvas accessibility, the proposed approach does not impose any rules on developers and designers during Canvas design.
Towards Ultra Rapid Restarts
Venue: arXiv cs.AI 2014
Year: 2014

We observe a trend regarding restart strategies used in SAT solvers. A few years ago, most state-of-the-art solvers restarted on average after a few thousands of backtracks. Currently, restarting after a dozen backtracks results in much better performance. The main reason for this trend is that heuristics and data structures have become more restart-friendly. We expect further continuation of this trend, so future SAT solvers will restart even more rapidly. Additionally, we present experimental results to support our observations.
Privacy-Preserving Public Information for Sequential Games
Venue: arXiv cs.GT 2014
Year: 2014

In settings with incomplete information, players can find it difficult to coordinate to find states with good social welfare. For example, in financial settings, if a collection of financial firms have limited information about each other's strategies, some large number of them may choose the same high-risk investment in hopes of high returns. While this might be acceptable in some cases, the economy can be hurt badly if many firms make investments in the same risky market segment and it fails. One reason why many firms might end up choosing the same segment is that they do not have information about other firms' investments (imperfect information may lead to `bad' game states). Directly reporting all players' investments, however, raises confidentiality concerns for both individuals and institutions. In this paper, we explore whether information about the game-state can be publicly announced in a manner that maintains the privacy of the actions of the players, and still suffices to deter players from reaching bad game-states. We show that in many games of interest, it is possible for players to avoid these bad states with the help of privacy-preserving, publicly-announced information. We model behavior of players in this imperfect information setting in two ways -- greedy and undominated strategic behaviours, and we prove guarantees on social welfare that certain kinds of privacy-preserving information can help attain. Furthermore, we design a counter with improved privacy guarantees under continual observation.
Off-Policy General Value Functions to Represent Dynamic Role Assignments in RoboCup 3D Soccer Simulation
Venue: arXiv cs.AI 2014
Year: 2014

Collecting and maintaining accurate world knowledge in a dynamic, complex, adversarial, and stochastic environment such as the RoboCup 3D Soccer Simulation is a challenging task. Knowledge should be learned in real-time with time constraints. We use recently introduced Off-Policy Gradient Descent algorithms within Reinforcement Learning that illustrate learnable knowledge representations for dynamic role assignments. The results show that the agents have learned competitive policies against the top teams from the RoboCup 2012 competitions for three vs three, five vs five, and seven vs seven agents. We have explicitly used subsets of agents to identify the dynamics and the semantics for which the agents learn to maximize their performance measures, and to gather knowledge about different objectives, so that all agents participate effectively and efficiently within the group.
Sampling and Representation Complexity of Revenue Maximization
Venue: arXiv cs.GT 2014
Year: 2014

We consider (approximate) revenue maximization in auctions where the distribution on input valuations is given via "black box" access to samples from the distribution. We observe that the number of samples required -- the sample complexity -- is tightly related to the representation complexity of an approximately revenue-maximizing auction. Our main results are upper bounds and an exponential lower bound on these complexities.
Spatial Mixing of Coloring Random Graphs
Venue: arXiv cs.DS 2014
Year: 2014

We study the strong spatial mixing (decay of correlation) property of proper $q$-colorings of random graph $G(n, d/n)$ with a fixed $d$. The strong spatial mixing of coloring and related models have been extensively studied on graphs with bounded maximum degree. However, for typical classes of graphs with bounded average degree, such as $G(n, d/n)$, an easy counterexample shows that colorings do not exhibit strong spatial mixing with high probability. Nevertheless, we show that for $q\geαd+β$ with $α>2$ and sufficiently large $β=O(1)$, with high probability proper $q$-colorings of random graph $G(n, d/n)$ exhibit strong spatial mixing with respect to an arbitrarily fixed vertex. This is the first strong spatial mixing result for colorings of graphs with unbounded maximum degree. Our analysis of strong spatial mixing establishes a block-wise correlation decay instead of the standard point-wise decay, which may be of interest by itself, especially for graphs with unbounded degree.