OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial solvability of $NP$-complete problems
Venue: arXiv cs.CC 2018
Year: 2018

${ NP}$-complete problem "Hamiltonian cycle"\ for graph $G=(V,E)$ is extended to the "Hamiltonian Complement of the Graph"\ problem of finding the minimal cardinality set $H$ containing additional edges so that graph $G=(V,E\cup H)$ is Hamiltonian. The solving of "Hamiltonian Complement of a Graph"\ problem is reduced to the linear programming problem {\bf P}, which has an optimal integer solution. The optimal integer solution of {\bf P} is found for any its optimal solution by solving the linear assignment problem {\bf L}. The existence of polynomial algorithms for problems {\bf P} and {\bf L} proves the polynomial solvability of ${ NP}$-complete problems.
Evaluation of Position-related Information in Multipath Components for Indoor Positioning
Venue: arXiv cs.IT 2018
Year: 2018

Location awareness is a key factor for a wealth of wireless indoor applications. Its provision requires the careful fusion of diverse information sources. For agents that use radio signals for localization, this information may either come from signal transmissions with respect to fixed anchors, from cooperative transmissions inbetween agents, or from radar-like monostatic transmissions. Using a-priori knowledge of a floor plan of the environment, specular multipath components can be exploited, based on a geometric-stochastic channel model. In this paper, a unified framework is presented for the quantification of this type of position-related information, using the concept of equivalent Fisher information. We derive analytical results for the Cramér-Rao lower bound of multipath-assisted positioning, considering bistatic transmissions between agents and fixed anchors, monostatic transmissions from agents, cooperative measurements inbetween agents, and combinations thereof, including the effect of clock offsets. Awareness of this information enables highly accurate and robust indoor positioning. Computational results show the applicability of the framework for the characterization of the localization capabilities of a given environment, quantifying the influence of different system setups, signal parameters, and the impact of path overlap.
An Epistemic Strategy Logic
Venue: arXiv cs.LO 2018
Year: 2018

This paper presents an extension of temporal epistemic logic with operators that quantify over agent strategies. Unlike previous work on alternating temporal epistemic logic, the semantics works with systems whose states explicitly encode the strategy being used by each of the agents. This provides a natural way to express what agents would know were they to be aware of some of the strategies being used by other agents. A number of examples that rely upon the ability to express an agent's knowledge about the strategies being used by other agents are presented to motivate the framework, including reasoning about game theoretic equilibria, knowledge-based programs, and information theoretic computer security policies. Relationships to several variants of alternating temporal epistemic logic are discussed. The computational complexity of model checking the logic and several of its fragments are also characterized.
Construction of Capacity-Achieving Lattice Codes: Polar Lattices
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a new class of lattices constructed from polar codes, namely polar lattices, to achieve the capacity $\frac{1}{2}\log(1+\SNR)$ of the additive white Gaussian-noise (AWGN) channel. Our construction follows the multilevel approach of Forney \textit{et al.}, where we construct a capacity-achieving polar code on each level. The component polar codes are shown to be naturally nested, thereby fulfilling the requirement of the multilevel lattice construction. We prove that polar lattices are \emph{AWGN-good}. Furthermore, using the technique of source polarization, we propose discrete Gaussian shaping over the polar lattice to satisfy the power constraint. Both the construction and shaping are explicit, and the overall complexity of encoding and decoding is $O(N\log N)$ for any fixed target error probability.
Nearly Linear-Time Packing and Covering LP Solvers
Venue: arXiv cs.DS 2018
Year: 2018

Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization. In 1993, Luby and Nisan constructed an iterative algorithm for approximately solving PC-LPs in nearly linear time, where the time complexity scales nearly linearly in $N$, the number of nonzero entries of the matrix, and polynomially in $\varepsilon$, the (multiplicative) approximation error. Unfortunately, all existing nearly linear-time algorithms for solving PC-LPs require time at least proportional to $\varepsilon^{-2}$. In this paper, we break this longstanding barrier by designing a packing solver that runs in time $\tilde{O}(N \varepsilon^{-1})$ and covering LP solver that runs in time $\tilde{O}(N \varepsilon^{-1.5})$. Our packing solver can be extended to run in time $\tilde{O}(N \varepsilon^{-1})$ for a class of well-behaved covering programs. In a follow-up work, Wang et al. showed that all covering LPs can be converted into well-behaved ones by a reduction that blows up the problem size only logarithmically. At high level, these two algorithms can be described as linear couplings of several first-order descent steps. This is an application of our linear coupling technique to problems that are not amenable to blackbox applications known iterative algorithms in convex optimization.
Dynamics of Information Diffusion and Social Sensing
Venue: arXiv cs.SI 2018
Year: 2018

Statistical inference using social sensors is an area that has witnessed remarkable progress and is relevant in applications including localizing events for targeted advertising, marketing, localization of natural disasters and predicting sentiment of investors in financial markets. This chapter presents a tutorial description of four important aspects of sensing-based information diffusion in social networks from a communications/signal processing perspective. First, diffusion models for information exchange in large scale social networks together with social sensing via social media networks such as Twitter is considered. Second, Bayesian social learning models and risk averse social learning is considered with applications in finance and online reputation systems. Third, the principle of revealed preferences arising in micro-economics theory is used to parse datasets to determine if social sensors are utility maximizers and then determine their utility functions. Finally, the interaction of social sensors with YouTube channel owners is studied using time series analysis methods. All four topics are explained in the context of actual experimental datasets from health networks, social media and psychological experiments. Also, algorithms are given that exploit the above models to infer underlying events based on social sensing. The overview, insights, models and algorithms presented in this chapter stem from recent developments in network science, economics and signal processing. At a deeper level, this chapter considers mean field dynamics of networks, risk averse Bayesian social learning filtering and quickest change detection, data incest in decision making over a directed acyclic graph of social sensors, inverse optimization problems for utility function estimation (revealed preferences) and statistical modeling of interacting social sensors in YouTube social networks.
Algorithms for Scheduling Malleable Cloud Tasks
Venue: arXiv cs.DC 2018
Year: 2018

Due to the ubiquity of batch data processing in cloud computing, the related problem of scheduling malleable batch tasks and its extensions have received significant attention recently. In this paper, we consider a fundamental model where a set of n tasks is to be processed on C identical machines and each task is specified by a value, a workload, a deadline and a parallelism bound. Within the parallelism bound, the number of machines assigned to a task can vary over time without affecting its workload. For this model, we obtain two core results: a sufficient and necessary condition such that a set of tasks can be finished by their deadlines on C machines, and an algorithm to produce such a schedule. These core results provide a conceptual tool and an optimal scheduling algorithm that enable proposing new algorithmic analysis and design and improving existing algorithms under various objectives.
Reversibility of d-State Finite Cellular Automata
Venue: arXiv cs.FL 2018
Year: 2018

This paper investigates reversibility properties of 1-dimensional 3-neighborhood d-state finite cellular automata (CAs) of length n under periodic boundary condition. A tool named reachability tree has been developed from de Bruijn graph which represents all possible reachable configurations of an n-cell CA. This tool has been used to test reversibility of CAs. We have identified a large set of reversible CAs using this tool by following some greedy strategies.
Practically-Self-Stabilizing Virtual Synchrony
Venue: arXiv cs.DC 2018
Year: 2018

Virtual synchrony is an important abstraction that is proven to be extremely useful when implemented over asynchronous, typically large, message-passing distributed systems. Fault tolerant design is a key criterion for the success of such implementations. This is because large distributed systems can be highly available as long as they do not depend on the full operational status of every system participant. Namely, they employ redundancy in numbers to overcome non-optimal behavior of participants and to gain global robustness and high availability. Self-stabilizing systems can tolerate transient faults that drive the system to an arbitrary unpredicted configuration. Such systems automatically regain consistency from any such arbitrary configuration, and then produce the desired system behavior. Practically self-stabilizing systems ensure the desired system behavior for practically infinite number of successive steps e.g., $2^{64}$ steps. We present the first practically self-stabilizing virtual synchrony algorithm. The algorithm is a combination of several new techniques that may be of independent interest. In particular, we present a new counter algorithm that establishes an efficient practically unbounded counter, that in turn can be directly used to implement a self-stabilizing Multiple-Writer Multiple-Reader (MWMR) register emulation. Other components include self-stabilizing group membership, self-stabilizing multicast, and self-stabilizing emulation of replicated state machine. As we base the replicated state machine implementation on virtual synchrony, rather than consensus, the system progresses in more extreme asynchronous executions in relation to consensus-based replicated state machine.
Cost-Effective Conceptual Design Using Taxonomies
Venue: arXiv cs.DB 2018
Year: 2018

It is known that annotating named entities in unstructured and semi-structured data sets by their concepts improves the effectiveness of answering queries over these data sets. As every enterprise has a limited budget of time or computational resources, it has to annotate a subset of concepts in a given domain whose costs of annotation do not exceed the budget. We call such a subset of concepts a {\it conceptual design} for the annotated data set. We focus on finding a conceptual design that provides the most effective answers to queries over the annotated data set, i.e., a {\it cost-effective conceptual design}. Since, it is often less time-consuming and costly to annotate general concepts than specific concepts, we use information on superclass/subclass relationships between concepts in taxonomies to find a cost-effective conceptual design. We quantify the amount by which a conceptual design with concepts from a taxonomy improves the effectiveness of answering queries over an annotated data set. If the taxonomy is a tree, we prove that the problem is NP-hard and propose an efficient approximation and pseudo-polynomial time algorithms for the problem. We further prove that if the taxonomy is a directed acyclic graph, given some generally accepted hypothesis, it is not possible to find any approximation algorithm with reasonably small approximation ratio for the problem. Our empirical study using real-world data sets, taxonomies, and query workloads shows that our framework effectively quantifies the amount by which a conceptual design improves the effectiveness of answering queries. It also indicates that our algorithms are efficient for a design-time task with pseudo-polynomial algorithm being generally more effective than the approximation algorithm.
Equitable total coloring of corona of cubic graphs
Venue: arXiv cs.DM 2018
Year: 2018

The minimum number of total independent partition sets of $V \cup E$ of a graph $G=(V,E)$ is called the \emph{total chromatic number} of $G$, denoted by $χ''(G)$. If the difference between cardinalities of any two total independent sets is at most one, then the minimum number of total independent partition sets of $V \cup E$ is called the \emph{equitable total chromatic number}, and is denoted by $χ''_=(G)$. In this paper we consider equitable total coloring of coronas of cubic graphs, $G \circ H$. It turns out that, independly on the values of equitable total chromatic number of factors $G$ and $H$, equitable total chromatic number of corona $G \circ H$ is equal to $Δ(G \circ H) +1$. Thereby, we confirm Total Coloring Conjecture (TCC), posed by Behzad in 1964, and Equitable Total Coloring Conjecture (ETCC), posed by Wang in 2002, for coronas of cubic graphs. As a direct consequence we get that all coronas of cubic graphs are of Type 1.
Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning
Venue: arXiv cs.SY 2018
Year: 2018

We are interested in understanding stability (almost sure boundedness) of stochastic approximation algorithms (SAs) driven by a `controlled Markov' process. Analyzing this class of algorithms is important, since many reinforcement learning (RL) algorithms can be cast as SAs driven by a `controlled Markov' process. In this paper, we present easily verifiable sufficient conditions for stability and convergence of SAs driven by a `controlled Markov' process. Many RL applications involve continuous state spaces. While our analysis readily ensures stability for such continuous state applications, traditional analyses do not. As compared to literature, our analysis presents a two-fold generalization (a) the Markov process may evolve in a continuous state space and (b) the process need not be ergodic under any given stationary policy. Temporal difference learning (TD) is an important policy evaluation method in reinforcement learning. The theory developed herein, is used to analyze generalized $TD(0)$, an important variant of TD. Our theory is also used to analyze a TD formulation of supervised learning for forecasting problems.
High-Dimensional Continuous Control Using Generalized Advantage Estimation
Venue: arXiv cs.LG 2018
Year: 2018

Policy gradient methods are an appealing approach in reinforcement learning because they directly optimize the cumulative reward and can straightforwardly be used with nonlinear function approximators such as neural networks. The two main challenges are the large number of samples typically required, and the difficulty of obtaining stable and steady improvement despite the nonstationarity of the incoming data. We address the first challenge by using value functions to substantially reduce the variance of policy gradient estimates at the cost of some bias, with an exponentially-weighted estimator of the advantage function that is analogous to TD(lambda). We address the second challenge by using trust region optimization procedure for both the policy and the value function, which are represented by neural networks. Our approach yields strong empirical results on highly challenging 3D locomotion tasks, learning running gaits for bipedal and quadrupedal simulated robots, and learning a policy for getting the biped to stand up from starting out lying on the ground. In contrast to a body of prior work that uses hand-crafted policy representations, our neural network policies map directly from raw kinematics to joint torques. Our algorithm is fully model-free, and the amount of simulated experience required for the learning tasks on 3D bipeds corresponds to 1-2 weeks of real time.
The Peano software - parallel, automaton-based, dynamically adaptive grid traversals
Venue: arXiv cs.MS 2018
Year: 2018

We discuss the design decisions, design alternatives and rationale behind the third generation of Peano, a framework for dynamically adaptive Cartesian meshes derived from spacetrees. Peano ties the mesh traversal to the mesh storage and supports only one element-wise traversal order resulting from space-filling curves. The user is not free to choose a traversal order herself. The traversal can exploit regular grid subregions and shared memory as well as distributed memory systems with almost no modifications to a serial application code. We formalize the software design by means of two interacting automata---one automaton for the multiscale grid traversal and one for the application-specific algorithmic steps. This yields a callback-based programming paradigm. We further sketch the supported application types and the two data storage schemes realized, before we detail high-performance computing aspects and lessons learned. Special emphasis is put on observations regarding the used programming idioms and algorithmic concepts. This transforms our report from a "one way to implement things" code description into a generic discussion and summary of some alternatives, rationale and design decisions to be made for any tree-based adaptive mesh refinement software.
A zero-sum monetary system, interest rates, and implications
Venue: arXiv cs.CE 2018
Year: 2018

To the knowledge of the author, this is the first time it has been shown that interest rates that are extremely high by modern standards (100% and higher) are necessary within a zero-sum monetary system, and not just driven by greed. Extreme interest rates that appeared in various places and times reinforce the idea that hard money may have contributed to high rates of interest. Here a model is presented that examines the interest rate required to succeed as an investor in a zero-sum fixed quantity hard-money system. Even when the playing field is significantly tilted toward the investor, interest rates need to be much higher than expected. In a completely fair zero-sum system, an investor cannot break even without charging 100% interest. Even with a 5% advantage, an investor won't break even at 15% interest. From this it is concluded that what we consider usurious rates today are, within a hard-money system, driven by necessity. Cryptocurrency is a novel form of hard-currency. The inability to virtualize the money creates a system close to zero-sum because of the limited supply design. Therefore, within the bounds of a cryptocurrency system that limits money creation, interest rates must rise to levels that the modern world considers usury. It is impossible, therefore, that a cryptocurrency that is not expandable could take over a modern economy and replace modern fiat currency.
Pure Strategies in Imperfect Information Stochastic Games
Venue: arXiv cs.FL 2018
Year: 2018

We consider imperfect information stochastic games where we require the players to use pure (i.e. non randomised) strategies. We consider reachability, safety, Büchi and co-Büchi objectives, and investigate the existence of almost-sure/positively winning strategies for the first player when the second player is perfectly informed or more informed than the first player. We obtain decidability results for positive reachability and almost-sure Büchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if exists. We complete the picture by showing that positive safety is undecidable when restricting to pure strategies even if the second player is perfectly informed.
(Pure) transcendence bases in $ϕ$-deformed shuffle bialgebras
Venue: arXiv cs.SC 2018
Year: 2018

Computations with integro-differential operators are often carried out in an associative algebra with unit, and they are essentially non-commutative computations. By adjoining a cocommutative co-product, one can have those operators perform act on a bialgebra isomorphic to an enveloping algebra. That gives an adequate framework for a computer-algebra implementation via monoidal factorization, (pure) transcendence bases and Poincaré--Birkhoff--Witt bases. In this paper, we systematically study these deformations, obtaining necessary and sufficient conditions for the operators to exist, and we give the most general cocommutative deformations of the shuffle co-product and an effective construction of pairs of bases in duality. The paper ends by the combinatorial setting of local systems of coordinates on the group of group-like series.
An Iterative Receiver for OFDM With Sparsity-Based Parametric Channel Estimation
Venue: arXiv cs.IT 2018
Year: 2018

In this work we design a receiver that iteratively passes soft information between the channel estimation and data decoding stages. The receiver incorporates sparsity-based parametric channel estimation. State-of-the-art sparsity-based iterative receivers simplify the channel estimation problem by restricting the multipath delays to a grid. Our receiver does not impose such a restriction. As a result it does not suffer from the leakage effect, which destroys sparsity. Communication at near capacity rates in high SNR requires a large modulation order. Due to the close proximity of modulation symbols in such systems, the grid-based approximation is of insufficient accuracy. We show numerically that a state-of-the-art iterative receiver with grid-based sparse channel estimation exhibits a bit-error-rate floor in the high SNR regime. On the contrary, our receiver performs very close to the perfect channel state information bound for all SNR values. We also demonstrate both theoretically and numerically that parametric channel estimation works well in dense channels, i.e., when the number of multipath components is large and each individual component cannot be resolved.
Abstract Gringo
Venue: arXiv cs.PL 2018
Year: 2018

This paper defines the syntax and semantics of the input language of the ASP grounder GRINGO. The definition covers several constructs that were not discussed in earlier work on the semantics of that language, including intervals, pools, division of integers, aggregates with non-numeric values, and lparse-style aggregate expressions. The definition is abstract in the sense that it disregards some details related to representing programs by strings of ASCII characters. It serves as a specification for GRINGO from Version 4.5 on.