OpenRaiser/Intern-Atlas huggingface dataset:
Submodular problems - approximations and algorithms
Venue: arXiv cs.DM 2017
Year: 2017

We show that any submodular minimization (SM) problem defined on a linear constraint set with constraints having up to two variables per inequality, are 2-approximable in polynomial time. If the constraints are monotone (the two variables appear with opposite sign coefficients) then the problems of submodular minimization or supermodular maximization are polynomial time solvable. The key idea is to link these problems to a submodular s,t-cut problem defined here. This framework includes the problems: SM-vertex cover; SM-2SAT; SM-min satisfiability; SM-edge deletion for clique, SM-node deletion for biclique and others. We also introduce here the submodular closure problem and and show that it is solvable in polynomial time and equivalent to the submodular cut problem. All the results are extendible to multi-sets where each element of a set may appear with a multiplicity greater than 1. For all these NP-hard problems 2-approximations are the best possible in the sense that a better approximation factor cannot be achieved in polynomial time unless NP=P. The mechanism creates a relaxed "monotone" problem, solved as a submodular closure problem, the solution to which is mapped to a half integral super-optimal solution to the original problem. That half-integral solution has the persistency property meaning that integer valued variables retain their value in an optimal solution. This permits to delete the integer valued variables, and restrict the search of an optimal solution to the smaller set of remaining variables.
On the Capacity of the Noncausal Relay Channel
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the noncausal relay channel, also known as the relay channel with unlimited lookahead, introduced by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand--Pinsker coding scheme, the relay can take further advantage of the noncausally available information, which can achieve strictly higher rates than existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay that strictly improves upon the cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class.
A survey of paraconsistent logics
Venue: arXiv cs.LO 2017
Year: 2017

A survey of paraconsistent logics that are prominent representatives of the different approaches that have been followed to develop paraconsistent logics is provided. The paraconsistent logics that will be discussed are an enrichment of Priest's logic LP, the logic RM3 from the school of relevance logic, da Costa's logics Cn, Jaskowski's logic D2, and Subrahmanian's logics Ptau. A deontic logic based on the first of these logics will be discussed as well. Moreover, some proposed adaptations of the AGM theory of belief revision to paraconsistent logics will be mentioned.
Metastability of Logit Dynamics for Coordination Games
Venue: arXiv cs.GT 2017
Year: 2017

Logit Dynamics [Blume, Games and Economic Behavior, 1993] are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. It can happen that the chain is "metastable", i.e., on a time-scale shorter than the mixing time, it stays close to some probability distribution over the state space, while in a time-scale multiple of the mixing time it jumps from one distribution to another. In this paper we give a quantitative definition of "metastable probability distributions" for a Markov chain and we study the metastability of the logit dynamics for some classes of coordination games. We first consider a pure $n$-player coordination game that highlights the distinctive features of our metastability notion based on distributions. Then, we study coordination games on the clique without a risk-dominant strategy (which are equivalent to the well-known Glauber dynamics for the Curie-Weiss model) and coordination games on a ring (both with and without risk-dominant strategy).
Logic + control: On program construction and verification
Venue: arXiv cs.LO 2017
Year: 2017

This paper presents an example of formal reasoning about the semantics of a Prolog program of practical importance (the SAT solver of Howe and King). The program is treated as a definite clause logic program with added control. The logic program is constructed by means of stepwise refinement, hand in hand with its correctness and completeness proofs. The proofs are declarative - they do not refer to any operational semantics. Each step of the logic program construction follows a systematic approach to constructing programs which are provably correct and complete. We also prove that correctness and completeness of the logic program is preserved in the final Prolog program. Additionally, we prove termination, occur-check freedom and non-floundering. Our example shows how dealing with "logic" and with "control" can be separated. Most of the proofs can be done at the "logic" level, abstracting from any operational semantics. The example employs approximate specifications; they are crucial in simplifying reasoning about logic programs. It also shows that the paradigm of semantics-preserving program transformations may be not sufficient. We suggest considering transformations which preserve correctness and completeness with respect to an approximate specification.
A Logic of Interactive Proofs (Formal Theory of Knowledge Transfer)
Venue: arXiv cs.LO 2017
Year: 2017

We propose a logic of interactive proofs as a framework for an intuitionistic foundation for interactive computation, which we construct via an interactive analog of the Goedel-McKinsey-Tarski-Artemov definition of Intuitionistic Logic as embedded into a classical modal logic of proofs, and of the Curry-Howard isomorphism between intuitionistic proofs and typed programs. Our interactive proofs effectuate a persistent epistemic impact in their intended communities of peer reviewers that consists in the induction of the (propositional) knowledge of their proof goal by means of the (individual) knowledge of the proof with the interpreting reviewer. That is, interactive proofs effectuate a transfer of propositional knowledge (knowable facts) via the transmission of certain individual knowledge (knowable proofs) in multi-agent distributed systems. In other words, we as a community can have the formal common knowledge that a proof is that which if known to one of our peer members would induce the knowledge of its proof goal with that member. Last but not least, we prove non-trivial interactive computation as definable within our simply typed interactive Combinatory Logic to be nonetheless equipotent to non-interactive computation as defined by simply typed Combinatory Logic.
A Resource-Competitive Jamming Defense
Venue: arXiv cs.DC 2017
Year: 2017

Consider a scenario where Alice wishes to send a message $m$ to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmission of $m$ by jamming the communication channel. There is a per-slot cost of $1$ to send, receive or jam $m$ on the channel, and we are interested in how much Alice and Bob need to spend relative to Carol in order to guarantee communication. Our approach is to design an algorithm in the framework of resource-competitive analysis where the cost to correct network devices (i.e., Alice and Bob) is parameterized by the cost to faulty devices (i.e., Carol). We present an algorithm that guarantees the successful transmission of $m$ and has the following property: if Carol incurs a cost of $T$ to jam, then both Alice and Bob have a cost of $O(T^{φ- 1} + 1)=O(T^{.62}+1)$ in expectation, where $φ= (1+ \sqrt{5})/2$ is the golden ratio. In other words, it possible for Alice and Bob to communicate while incurring asymptotically less cost than Carol. We generalize to the case where Alice wishes to send $m$ to $n$ receivers, and we achieve a similar result. Our findings hold even if (1) $T$ is unknown to either party; (2) Carol knows the algorithms of both parties, but not their random bits; (3) Carol can jam using knowledge of past actions of both parties; and (4) Carol can jam reactively, so long as there is sufficient network traffic in addition to $m$.
Analysis of a Natural Gradient Algorithm on Monotonic Convex-Quadratic-Composite Functions
Venue: arXiv cs.AI 2017
Year: 2017

In this paper we investigate the convergence properties of a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Our study is based on the recent theoretical foundation that the pure rank-mu update CMA-ES performs the natural gradient descent on the parameter space of Gaussian distributions. We derive a novel variant of the natural gradient method where the parameters of the Gaussian distribution are updated along the natural gradient to improve a newly defined function on the parameter space. We study this algorithm on composites of a monotone function with a convex quadratic function. We prove that our algorithm adapts the covariance matrix so that it becomes proportional to the inverse of the Hessian of the original objective function. We also show the speed of covariance matrix adaptation and the speed of convergence of the parameters. We introduce a stochastic algorithm that approximates the natural gradient with finite samples and present some simulated results to evaluate how precisely the stochastic algorithm approximates the deterministic, ideal one under finite samples and to see how similarly our algorithm and the CMA-ES perform.
Improved visualisation of brain arteriovenous malformations using color intensity projections with hue cycling
Venue: arXiv cs.GR 2017
Year: 2017

Color intensity projections (CIP) have been shown to improve the visualisation of greyscale angiography images by combining greyscale images into a single color image. A key property of the combined CIP image is the encoding of the arrival time information from greyscale images into the hue of the color in the CIP image. A few minor improvements to the calculation of the CIP image are introduced that substantially improve the quality of the visualisation. One improvement is interpolating of the greyscale images in time before calculation of the CIP image. A second is the use of hue cycling - where the hue of the color is cycled through more than once in an image. The hue cycling allows the variation of the hue to be concentrated in structures of interest. If there is a zero time point hue cycling can be applied after zero time and before zero time can be indicated by greyscale. If there is an end time point hue cycling can be applied before the end time and pixels can be set to black after the end time. An angiogram of a brain is used to demonstrate the substantial improvements hue cycling brings to CIP images. A third improvement is the use of maximum intensity projection for 2D rendering of a 3D CIP image volume. A fourth improvement allowing interpreters to interactively adjust the phase of the hue via standard contrast - brightness controls using lookup tables. Other potential applications of CIP are also mentioned.
Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
Venue: arXiv cs.DS 2017
Year: 2017

We give the first linear kernels for the (Connected) Dominating Set problems on H-topological minor free graphs. We prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an H-topological-minor-free graph G' on O(k) vertices such that G has a (connected) dominating set of size k iff G' has one. Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for Dominating Set, a kernel of size kc(H), where c(H) is a constant depending on the size of H, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for Dominating Set on H-minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For Connected Dominating Set no polynomial kernel even on H-minor-free graphs was known prior to our work. On the negative side, it is known that Connected Dominating Set on 2-degenerated graphs does not admit a polynomial kernel unless coNP $\subseteq$ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; A novel notion of protrusions, different than the one defined in [FOCS 2009]; Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H-minor-free) of the problem, with treewidth $O(\sqrt{k})$. The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels.
Parameter Estimation of Switched Hammerstein Systems
Venue: arXiv cs.SY 2017
Year: 2017

This paper deals with the parameter estimation problem of the Single-Input-Single-Output (SISO) switched Hammerstein system. Suppose that the switching law is arbitrary but can be observed online. All subsystems are parameterized and the Recursive Least Squares (RLS) algorithm is applied to estimate their parameters. To overcome the difficulty caused by coupling of data from different subsystems, the concept "intrinsic switch" is introduced. Two cases are considered: i) The input is taken to be a sequence of independent identically distributed (i.i.d.) random variables when identification is the only purpose; ii) A diminishingly excited signal is superimposed on the control when the adaptive control law is given. The strong consistency of the estimates in both cases is established and a simulation example is given to verify the theoretical analysis.
Computational Aspects of Nearly Single-Peaked Electorates
Venue: arXiv cs.CC 2017
Year: 2017

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.
How many software engineering professionals hold this certificate?
Venue: arXiv cs.SE 2017
Year: 2017

Estimates of quantity of the certificates issued during 10 years of existence of the professionals certification program in the area of software engineering implemented by one of the leading professional associations are presented. The estimates have been obtained by way of processing certificate records openly accessible at the certification program web-site. Comparison of these estimates and the known facts about evolution of the certification program indicates that as of the present day this evolution has not led to a large scale issuance of these certificates. But the same estimates, possibly, indicate that the meaning of these certificates differs from what is usually highlighted, and their real value is much greater. Also these estimates can be viewed, besides everything else, as reflecting an outcome of a decade long experimental verification of the known idea about "software engineering as a mature engineering profession," and they possibly show that this idea deserves partial revision.
Game Theoretic Analysis of Production-Management Effort Distribution in Organizational Networks
Venue: arXiv cs.GT 2017
Year: 2017

Organizations consist of individuals connected by their responsibilities, incentives, and reporting structure. These connections are aptly represented by a network, hierarchical or other, which is often used to divide tasks. A primary goal of the organization as a whole is to maximize the net productive output. Individuals in these networks trade off between their productive and managing efforts to perform these tasks and the trade-off is influenced by their positions and share of rewards in the network. Efforts of the agents here are substitutable, e.g., the increase in the productive effort by an individual in effect reduces the same of some other individual in the network, who now puts their efforts into management. The management effort of an agent improves the productivity of certain other agents in the network. In this paper, we carry out a detailed game-theoretic analysis of individual's equilibrium split of efforts into multiple components when connected over a network. We provide a design recipe of the reward sharing scheme that maximizes the net productive output. Our results show that under the strategic behavior of the agents, it may not always be possible to achieve the optimal output using an idea from game theory called the price of anarchy.
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph $G$ embedded on a surface of genus $g$ and a designated face $f$ bounded by a simple cycle of length $k$, uncovers a set $F \subseteq E(G)$ of size polynomial in $g$ and $k$ that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of $f$. We apply this general theorem to prove that: * given an unweighted graph $G$ embedded on a surface of genus $g$ and a terminal set $S \subseteq V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal Steiner tree $T$ for $S$ and that has size polynomial in $g$ and $|E(T)|$; * an analogous result holds for an optimal Steiner forest for a set $S$ of terminal pairs; * given an unweighted planar graph $G$ and a terminal set $S \subseteq V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal (edge) multiway cut $C$ separating $S$ and that has size polynomial in $|C|$. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution.
Improved Submatrix Maximum Queries in Monge Matrices
Venue: arXiv cs.DS 2017
Year: 2017

We present efficient data structures for submatrix maximum queries in Monge matrices and Monge partial matrices. For $n\times n$ Monge matrices, we give a data structure that requires O(n) space and answers submatrix maximum queries in $O(\log n)$ time. The best previous data structure [Kaplan et al., SODA`12] required $O(n \log n)$ space and $O(\log^2 n)$ query time. We also give an alternative data structure with constant query-time and $ O(n^{1+\varepsilon})$ construction time and space for any fixed $\varepsilon<1$. For $n\times n$ {\em partial} Monge matrices we obtain a data structure with O(n) space and $O(\log n \cdot α(n))$ query time. The data structure of Kaplan et al. required $O(n \log n \cdot α(n))$ space and $O(\log^2 n)$ query time. Our improvements are enabled by a technique for exploiting the structure of the upper envelope of Monge matrices to efficiently report column maxima in skewed rectangular Monge matrices. We hope this technique can be useful in obtaining faster search algorithms in Monge partial matrices. In addition, we give a linear upper bound on the number of breakpoints in the upper envelope of a Monge partial matrix. This shows that the inverse Ackermann $α(n)$ term in the analysis of the data structure of Kaplan et. al is superfluous.
Control in the Presence of Manipulators: Cooperative and Competitive Cases
Venue: arXiv cs.GT 2017
Year: 2017

Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the "chair" who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet for a Borda-voting case we show that such clashes raise the complexity unless NP = coNP.
A semi-potential for finite and infinite sequential games
Venue: arXiv cs.GT 2017
Year: 2017

We consider a dynamical approach to game in extensive forms. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic (finite) time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite games in extensive form we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are $Δ^0_2$-sets.