OpenRaiser/Intern-Atlas huggingface dataset:
Relational Division in Rank-Aware Databases
Venue: arXiv cs.DB 2015
Year: 2015

We present a survey of existing approaches to relational division in rank-aware databases, discuss issues of the present approaches, and outline generalizations of several types of classic division-like operations. We work in a model which generalizes the Codd model of data by considering tuples in relations annotated by ranks, indicating degrees to which tuples in relations match queries. The approach utilizes complete residuated lattices as the basic structures of degrees. We argue that unlike the classic model, relational divisions are fundamental operations which cannot in general be expressed by means of other operations. In addition, we compare the existing and proposed operations and identify those which are faithful counterparts of universally quantified queries formulated in relational calculi. We introduce Pseudo Tuple Calculus in the ranked model which is further used to show mutual definability of the various forms of divisions presented in the paper.
A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries
Venue: arXiv cs.DB 2015
Year: 2015

Several research thrusts in the area of data management have focused on understanding how changes in the data affect the output of a view or standing query. Example applications are explaining query results, propagating updates through views, and anonymizing datasets. These applications usually rely on understanding how interventions in a database impact the output of a query. An important aspect of this analysis is the problem of deleting a minimum number of tuples from the input tables to make a given Boolean query false. We refer to this problem as "the resilience of a query" and show its connections to the well-studied problems of deletion propagation and causal responsibility. In this paper, we study the complexity of resilience for self-join-free conjunctive queries, and also make several contributions to previous known results for the problems of deletion propagation with source side-effects and causal responsibility: (1) We define the notion of resilience and provide a complete dichotomy for the class of self-join-free conjunctive queries with arbitrary functional dependencies; this dichotomy also extends and generalizes previous tractability results on deletion propagation with source side-effects. (2) We formalize the connection between resilience and causal responsibility, and show that resilience has a larger class of tractable queries than responsibility. (3) We identify a mistake in a previous dichotomy for the problem of causal responsibility and offer a revised characterization based on new, simpler, and more intuitive notions. (4) Finally, we extend the dichotomy for causal responsibility in two ways: (a) we treat cases where the input tables contain functional dependencies, and (b) we compute responsibility for a set of tuples specified via wildcards.
SINR and Throughput Scaling in Ultradense Urban Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

We consider a dense urban cellular network where the base stations (BSs) are stacked vertically as well as extending infinitely in the horizontal plane, resulting in a greater than two dimensional (2D) deployment. Using a dual-slope path loss model that is well supported empirically, we extend recent 2D coverage probability and potential throughput results to 3 dimensions. We prove that the "critical close-in path loss exponent" $α_0$ where SINR eventually decays to zero is equal to the dimensionality $d$, i.e. $α_0 \leq 3$ results in an eventual SINR of 0 in a 3D network. We also show that the potential (i.e. best case) aggregate throughput decays to zero for $α_0 < d/2$. Both of these scaling results also hold for the more realistic case that we term ${3\rm{D}^{+}}$, where there are no BSs below the user, as in a dense urban network with the user on or near the ground.
Approximate Deadline-Scheduling with Precedence Constraints
Venue: arXiv cs.DS 2015
Year: 2015

We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an O(log k)-approximation algorithm for instances with k distinct job deadlines.
Improving package recommendations through query relaxation
Venue: arXiv cs.DB 2015
Year: 2015

Recommendation systems aim to identify items that are likely to be of interest to users. In many cases, users are interested in package recommendations as collections of items. For example, a dietitian may wish to derive a dietary plan as a collection of recipes that is nutritionally balanced, and a travel agent may want to produce a vacation package as a coordinated collection of travel and hotel reservations. Recent work has explored extending recommendation systems to support packages of items. These systems need to solve complex combinatorial problems, enforcing various properties and constraints defined on sets of items. Introducing constraints on packages makes recommendation queries harder to evaluate, but also harder to express: Queries that are under-specified produce too many answers, whereas queries that are over-specified frequently miss interesting solutions. In this paper, we study query relaxation techniques that target package recommendation systems. Our work offers three key insights: First, even when the original query result is not empty, relaxing constraints can produce preferable solutions. Second, a solution due to relaxation can only be preferred if it improves some property specified by the query. Third, relaxation should not treat all constraints as equals: some constraints are more important to the users than others. Our contributions are threefold: (a) we define the problem of deriving package recommendations through query relaxation, (b) we design and experimentally evaluate heuristics that relax query constraints to derive interesting packages, and (c) we present a crowd study that evaluates the sensitivity of real users to different kinds of constraints and demonstrates that query relaxation is a powerful tool in diversifying package recommendations.
Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we propose the approach for constructing partitionings of hard variants of the Boolean satisfiability problem (SAT). Such partitionings can be used for solving corresponding SAT instances in parallel. For the same SAT instance one can construct different partitionings, each of them is a set of simplified versions of the original SAT instance. The effectiveness of an arbitrary partitioning is determined by the total time of solving of all SAT instances from it. We suggest the approach, based on the Monte Carlo method, for estimating time of processing of an arbitrary partitioning. With each partitioning we associate a point in the special finite search space. The estimation of effectiveness of the particular partitioning is the value of predictive function in the corresponding point of this space. The problem of search for an effective partitioning can be formulated as a problem of optimization of the predictive function. We use metaheuristic algorithms (simulated annealing and tabu search) to move from point to point in the search space. In our computational experiments we found partitionings for SAT instances encoding problems of inversion of some cryptographic functions. Several of these SAT instances with realistic predicted solving time were successfully solved on a computing cluster and in the volunteer computing project SAT@home. The solving time agrees well with estimations obtained by the proposed method.
Global clustering coefficient in scale-free weighted and unweighted networks
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we present a detailed analysis of the global clustering coefficient in scale-free graphs. Many observed real-world networks of diverse nature have a power-law degree distribution. Moreover, the observed degree distribution usually has an infinite variance. Therefore, we are especially interested in such degree distributions. In addition, we analyze the clustering coefficient for both weighted and unweighted graphs. There are two well-known definitions of the clustering coefficient of a graph: the global and the average local clustering coefficients. There are several models proposed in the literature for which the average local clustering coefficient tends to a positive constant as a graph grows. On the other hand, there are no models of scale-free networks with an infinite variance of the degree distribution and with an asymptotically constant global clustering coefficient. Models with constant global clustering and finite variance were also proposed. Therefore, in this paper we focus only on the most interesting case: we analyze the global clustering coefficient for graphs with an infinite variance of the degree distribution. For unweighted graphs, we prove that the global clustering coefficient tends to zero with high probability and we also estimate the largest possible clustering coefficient for such graphs. On the contrary, for weighted graphs, the constant global clustering coefficient can be obtained even for the case of an infinite variance of the degree distribution.
Evolution of as-a-Service Era in Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Today, a paradigm shift is being observed in science, where the focus is gradually shifting toward the cloud environments to obtain appropriate, robust and affordable services to deal with Big Data challenges (Sharma et al. 2014, 2015a, 2015b). Cloud computing avoids any need to locally maintain the overly scaled computing infrastructure that include not only dedicated space, but the expensive hardware and software also. In this paper, we study the evolution of as-a-Service modalities, stimulated by cloud computing, and explore the most complete inventory of new members beyond traditional cloud computing stack.
A Note on Monitors and Büchi automata
Venue: arXiv cs.FL 2015
Year: 2015

When a property needs to be checked against an unknown or very complex system, classical exploration techniques like model-checking are not applicable anymore. Sometimes a~monitor can be used, that checks a given property on the underlying system at runtime. A monitor for a property $L$ is a deterministic finite automaton $M_L$ that after each finite execution tells whether (1) every possible extension of the execution is in $L$, or (2) every possible extension is in the complement of $L$, or neither (1) nor (2) holds. Moreover, $L$ being monitorable means that it is always possible that in some future the monitor reaches (1) or (2). Classical examples for monitorable properties are safety and cosafety properties. On the other hand, deterministic liveness properties like "infinitely many $a$'s" are not monitorable. We discuss various monitor constructions with a focus on deterministic omega-regular languages. We locate a proper subclass of of deterministic omega-regular languages but also strictly large than the subclass of languages which are deterministic and codeterministic, and for this subclass there exists a canonical monitor which also accepts the language itself. We also address the problem to decide monitorability in comparison with deciding liveness. The state of the art is as follows. Given a Büchi automaton, it is PSPACE-complete to decide liveness or monitorability. Given an LTL formula, deciding liveness becomes EXPSPACE-complete, but the complexity to decide monitorability remains open.
Value and Policy Iteration in Optimal Control and Adaptive Dynamic Programming
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we consider discrete-time infinite horizon problems of optimal control to a terminal set of states. These are the problems that are often taken as the starting point for adaptive dynamic programming. Under very general assumptions, we establish the uniqueness of solution of Bellman's equation, and we provide convergence results for value and policy iteration.
Forgetting complex propositions
Venue: arXiv cs.LO 2015
Year: 2015

This paper uses possible-world semantics to model the changes that may occur in an agent's knowledge as she loses information. This builds on previous work in which the agent may forget the truth-value of an atomic proposition, to a more general case where she may forget the truth-value of a propositional formula. The generalization poses some challenges, since in order to forget whether a complex proposition $π$ is the case, the agent must also lose information about the propositional atoms that appear in it, and there is no unambiguous way to go about this. We resolve this situation by considering expressions of the form $[\boldsymbol{\ddagger} π]φ$, which quantify over all possible (but minimal) ways of forgetting whether $π$. Propositional atoms are modified non-deterministically, although uniformly, in all possible worlds. We then represent this within action model logic in order to give a sound and complete axiomatization for a logic with knowledge and forgetting. Finally, some variants are discussed, such as when an agent forgets $π$ (rather than forgets whether $π$) and when the modification of atomic facts is done non-uniformly throughout the model.
Prophet Secretary
Venue: arXiv cs.GT 2015
Year: 2015

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e. In this paper, we introduce Prophet Secretary, a natural combination of the prophet inequality and the secretary problems. An example motivation for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision whether to sell the item at the offered price. We address the question of finding a strategy for selling the item at a high price. We show that by using a uniform threshold one cannot break the 0.5 barrier. However, we show that i) using n distinct non-adaptive thresholds one can obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly.
When Can Limited Randomness Be Used in Repeated Games?
Venue: arXiv cs.GT 2015
Year: 2015

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the $n$-stage repeated version of the game exist if and only if both players have $Ω(n)$ random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the $n$-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on "random-like" sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators \emph{do not} exist, then $Ω(n)$ random bits remain necessary for equilibria to exist.
Explicit Expanding Expanders
Venue: arXiv cs.DS 2015
Year: 2015

Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are "close" to each other. We study the following question: Construct an an infinite sequence of expanders $G_0,G_1,\dots$, such that for every two consecutive graphs $G_i$ and $G_{i+1}$, $G_{i+1}$ can be obtained from $G_i$ by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from $G_i$ to $G_{i+1}$. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of $d$-regular expanders with expansion cost at most $5d/2$, for any $d\geq 6$. Our construction leverages the notion of a "2-lift" of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to "interpolate" between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the "self-healing" model.
Computers Can't Give Credit: How Automatic Attribution Falls Short in an Online Remixing Community
Venue: arXiv cs.HC 2015
Year: 2015

In this paper, we explore the role that attribution plays in shaping user reactions to content reuse, or remixing, in a large user-generated content community. We present two studies using data from the Scratch online community -- a social media platform where hundreds of thousands of young people share and remix animations and video games. First, we present a quantitative analysis that examines the effects of a technological design intervention introducing automated attribution of remixes on users' reactions to being remixed. We compare this analysis to a parallel examination of "manual" credit-giving. Second, we present a qualitative analysis of twelve in-depth, semi-structured, interviews with Scratch participants on the subject of remixing and attribution. Results from both studies suggest that automatic attribution done by technological systems (i.e., the listing of names of contributors) plays a role that is distinct from, and less valuable than, credit which may superficially involve identical information but takes on new meaning when it is given by a human remixer. We discuss the implications of these findings for the designers of online communities and social media platforms.
The Cost of Collaboration for Code and Art: Evidence from a Remixing Community
Venue: arXiv cs.CY 2015
Year: 2015

In this paper, we use evidence from a remixing community to evaluate two pieces of common wisdom about collaboration. First, we test the theory that jointly produced works tend to be of higher quality than individually authored products. Second, we test the theory that collaboration improves the quality of functional works like code, but that it works less well for artistic works like images and sounds. We use data from Scratch, a large online community where hundreds of thousands of young users share and remix millions of animations and interactive games. Using peer-ratings as a measure of quality, we estimate a series of fitted regression models and find that collaborative Scratch projects tend to receive ratings that are lower than individually authored works. We also find that code-intensive collaborations are rated higher than media-intensive efforts. We conclude by discussing the limitations and implications of these findings.
Eventful: Crowdsourcing Local News Reporting
Venue: arXiv cs.HC 2015
Year: 2015

We present Eventful, a system for producing news reports of local events using remote and locative crowd workers. The system recruits and guides novice crowd workers as they perform the roles of field reporter, curator, or writer. Field reporters attend the events in person, and use Eventful's mobile web app to get a personalized mission, submit content, and receive feedback. Missions include tasks such as taking a photo, and asking a question to an attendee. In parallel, remote curators approve, reject, and give real-time feedback on the content collected by field reporters. Finally, writers put together a report by mashing up and tweaking the content approved by the curators. We used Eventful to produce a news report for each of the six local events we decided to cover as we piloted the system. The process was typically completed under an hour and costing under $150 USD.
Mixsourcing: a remix framework as a form of crowdsourcing
Venue: arXiv cs.HC 2015
Year: 2015

In this paper, we introduce the concept of mixsourcing as a modality of crowdsourcing focused on using remixing as a framework to get people to perform creative tasks. We explore this idea through the design of a system that helped us identify the promises and challenges of this peer-production modality.
TiD -- Documentation of TOBI Interface D
Venue: arXiv cs.NI 2015
Year: 2015

This document contains the documentation of TOBI (Tools for BCI) Interface D (TiD). TiD tries to establish a standardized interface for event transmission in neuroscience experiments. It is designed in a client-server architecture. Clients are connecting to a single server and events are delivered in a "bus-like" manner. TiD events are based on XML messages. So TiD messages can also get custom extended. A cross platform C++ library is available and provides all TiD functionality. To avoid jitter effect, hampering event processing, TiD was optimized towards performance. The documentation provides further performance tweaks to decrease TiD message processing latency and also decrease event timing jitter.