OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of Online Voter Control in Sequential Elections
Venue: arXiv cs.GT 2016
Year: 2016

Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters' preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is PSPACE-complete, even if there are only two candidates. In addition, we obtain (by a new characterization of coNP in terms of weight-bounded alternating Turing machines) completeness for coNP in the deleting/adding cases with a bounded deletion/addition limit, and we obtain completeness for NP in the partition cases with an additional restriction. We also show that for plurality, online control by deleting or adding voters is in P, and for partitioning voters is coNP-hard.
Power Series Method applied to Inverse Analysis in Chemical Kinetics Problem
Venue: arXiv cs.NA 2016
Year: 2016

Power Series Solution Method has been traditionally used to solve Ordinary and Partial Linear Differential Equations. However, despite their usefulness the application of this method has been limited to this particular kind of equations. In this work we use the method of power series to solve nonlinear partial differential equations. The method is applied to solve three versions of nonlinear time-dependent Burgers-Type differential equations in order to demonstrate its scope and applicability.
Revolvable Indoor Panoramas Using a Rectified Azimuthal Projection
Venue: arXiv cs.CV 2016
Year: 2016

We present an algorithm for converting an indoor spherical panorama into a photograph with a simulated overhead view. The resulting image will have an extremely wide field of view covering up to 4π steradians of the spherical panorama. We argue that our method complements the stereographic projection commonly used in the "little planet" effect. The stereographic projection works well in creating little planets of outdoor scenes; whereas our method is a well-suited counterpart for indoor scenes. The main innovation of our method is the introduction of a novel azimuthal map projection that can smoothly blend between the stereographic projection and the Lambert azimuthal equal-area projection. Our projection has an adjustable parameter that allows one to control and compromise between distortions in shape and distortions in size within the projected panorama. This extra control parameter gives our projection the ability to produce superior results over the stereographic projection.
Faster Geometric Algorithms via Dynamic Determinant Computation
Venue: arXiv cs.CG 2016
Year: 2016

The computation of determinants or their signs is the core procedure in many important geometric algorithms, such as convex hull, volume and point location. As the dimension of the computation space grows, a higher percentage of the total computation time is consumed by these computations. In this paper we study the sequences of determinants that appear in geometric algorithms. The computation of a single determinant is accelerated by using the information from the previous computations in that sequence. We propose two dynamic determinant algorithms with quadratic arithmetic complexity when employed in convex hull and volume computations, and with linear arithmetic complexity when used in point location problems. We implement the proposed algorithms and perform an extensive experimental analysis. On one hand, our analysis serves as a performance study of state-of-the-art determinant algorithms and implementations. On the other hand, we demonstrate the supremacy of our methods over state-of-the-art implementations of determinant and geometric algorithms. Our experimental results include a 20 and 78 times speed-up in volume and point location computations in dimension 6 and 11 respectively.
Designing FPT algorithms for cut problems using randomized contractions
Venue: arXiv cs.DS 2016
Year: 2016

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for the Unique Label Cover problem and new FPT algorithms with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. More precisely, we show the following: - We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2^{O(k^2\log |Σ|)}n^4\log n deterministic time (even in the stronger, vertex-deletion variant) where k is the number of unsatisfied edges and |Σ| is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by O(\sqrt{\log n}) to optimality, which improves over the trivial O(1) upper bound. - We prove that the Steiner Cut problem can be solved in 2^{O(k^2\log k)}n^4\log n deterministic time and \tilde{O}(2^{O(k^2\log k)}n^2) randomized time where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup (FOCS'11). - We show how to combine considering `cut' and `uncut' constraints at the same time. More precisely, we define a robust problem Node Multiway Cut-Uncut that can serve as an abstraction of introducing uncut constraints, and show that it admits an algorithm running in 2^{O(k^2\log k)}n^4\log n deterministic time where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our technique is that, unlike important separators, it can handle real weights.
On the Sum Rate of a 2 x 2 Interference Network
Venue: arXiv cs.IT 2016
Year: 2016

In an M x N interference network, there are M transmitters and N receivers with each transmitter having independent messages for each of the 2^N -1 possible non-empty subsets of the receivers. We consider the 2 x 2 interference network with 6 possible messages, of which the 2 x 2 interference channel and X channel are special cases obtained by using only 2 and 4 messages respectively. Starting from an achievable rate region similar to the Han-Kobayashi region, we obtain an achievable sum rate. For the Gaussian interference network, we determine which of the 6 messages are sufficient for maximizing the sum rate within this rate region for the low, mixed, and strong interference conditions. It is observed that 2 messages are sufficient in several cases.
Degrees of freedom in vector interference channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper continues the Wu-Shamai-Verdu program [3] on characterizing the degrees of freedom (DoF) of interference channels (ICs) through Renyi information dimension. Specifically, we find a single-letter formula for the DoF of vector ICs, encompassing multiple-input multiple-output (MIMO) ICs, time- and/or frequency-selective ICs, and combinations thereof, as well as scalar ICs as considered in [3]. The DoF-formula we obtain lower-bounds the DoF of all channels--with respect to the choice of the channel matrix--and upper-bounds the DoF of almost all channels. It applies to a large class of noise distributions, and its proof is based on an extension of a result by Guionnet and Shlyakthenko [3] to the vector case in combination with the Ruzsa triangle inequality for differential entropy introduced by Kontoyiannis and Madiman [4]. As in scalar ICs, achieving full DoF requires the use of singular input distributions. Strikingly, in the vector case it suffices to enforce singularity on the joint distribution of each individual transmit vector. This can be realized through signaling in subspaces of the ambient signal space, which is in accordance with the idea of interference alignment, and, most importantly, allows the scalar entries of the transmit vectors to have non-singular distributions. The DoF-formula for vector ICs we obtain enables a unified treatment of "classical" interference alignment a la Cadambe and Jafar [5], and Maddah-Ali et al. [6], and the number-theoretic schemes proposed in [7], [8]. Moreover, it allows to calculate the DoF achieved by new signaling schemes for vector ICs. We furthermore recover the result by Cadambe and Jafar on the non-separability of parallel ICs [9] and we show that almost all parallel ICs are separable in terms of DoF. Finally, our results apply to complex vector ICs, thereby extending the main findings of [2] to the complex case.
The complexity of finite-valued CSPs
Venue: arXiv cs.CC 2016
Year: 2016

We study the computational complexity of exact minimisation of rational-valued discrete functions. Let $Γ$ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, $\operatorname{VCSP}(Γ)$, is the problem of minimising a function given as a sum of functions from $Γ$. We establish a dichotomy theorem with respect to exact solvability for all finite-valued constraint languages defined on domains of arbitrary finite size. We show that every constraint language $Γ$ either admits a binary symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of $\operatorname{VCSP}(Γ)$ exactly, or $Γ$ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to $\operatorname{VCSP}(Γ)$.
Multi-Target Regression via Input Space Expansion: Treating Targets as Inputs
Venue: arXiv cs.LG 2016
Year: 2016

In many practical applications of supervised learning the task involves the prediction of multiple target variables from a common set of input variables. When the prediction targets are binary the task is called multi-label classification, while when the targets are continuous the task is called multi-target regression. In both tasks, target variables often exhibit statistical dependencies and exploiting them in order to improve predictive accuracy is a core challenge. A family of multi-label classification methods address this challenge by building a separate model for each target on an expanded input space where other targets are treated as additional input variables. Despite the success of these methods in the multi-label classification domain, their applicability and effectiveness in multi-target regression has not been studied until now. In this paper, we introduce two new methods for multi-target regression, called Stacked Single-Target and Ensemble of Regressor Chains, by adapting two popular multi-label classification methods of this family. Furthermore, we highlight an inherent problem of these methods - a discrepancy of the values of the additional input variables between training and prediction - and develop extensions that use out-of-sample estimates of the target variables during training in order to tackle this problem. The results of an extensive experimental evaluation carried out on a large and diverse collection of datasets show that, when the discrepancy is appropriately mitigated, the proposed methods attain consistent improvements over the independent regressions baseline. Moreover, two versions of Ensemble of Regression Chains perform significantly better than four state-of-the-art methods including regularization-based multi-task learning methods and a multi-objective random forest approach.
TEI and LMF crosswalks
Venue: arXiv cs.CL 2016
Year: 2016

The present paper explores various arguments in favour of making the Text Encoding Initia-tive (TEI) guidelines an appropriate serialisation for ISO standard 24613:2008 (LMF, Lexi-cal Mark-up Framework) . It also identifies the issues that would have to be resolved in order to reach an appropriate implementation of these ideas, in particular in terms of infor-mational coverage. We show how the customisation facilities offered by the TEI guidelines can provide an adequate background, not only to cover missing components within the current Dictionary chapter of the TEI guidelines, but also to allow specific lexical projects to deal with local constraints. We expect this proposal to be a basis for a future ISO project in the context of the on going revision of LMF.
Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices
Venue: arXiv cs.IT 2016
Year: 2016

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed-points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed-points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy.
Testing Uniformity of Stationary Distribution
Venue: arXiv cs.DS 2016
Year: 2016

A random walk on a directed graph gives a Markov chain on the vertices of the graph. An important question that arises often in the context of Markov chain is whether the uniform distribution on the vertices of the graph is a stationary distribution of the Markov chain. Stationary distribution of a Markov chain is a global property of the graph. In this paper, we prove that for a regular directed graph whether the uniform distribution on the vertices of the graph is a stationary distribution, depends on a local property of the graph, namely if (u,v) is an directed edge then outdegree(u) is equal to indegree(v). This result also has an application to the problem of testing whether a given distribution is uniform or "far" from being uniform. This is a well studied problem in property testing and statistics. If the distribution is the stationary distribution of the lazy random walk on a directed graph and the graph is given as an input, then how many bits of the input graph do one need to query in order to decide whether the distribution is uniform or "far" from it? This is a problem of graph property testing and we consider this problem in the orientation model (introduced by Halevy et al.). We reduce this problem to test (in the orientation model) whether a directed graph is Eulerian. And using result of Fischer et al. on query complexity of testing (in the orientation model) whether a graph is Eulerian, we obtain bounds on the query complexity for testing whether the stationary distribution is uniform.
Sample Approximation-Based Deflation Approaches for Chance SINR Constrained Joint Power and Admission Control
Venue: arXiv cs.IT 2016
Year: 2016

Consider the joint power and admission control (JPAC) problem for a multi-user single-input single-output (SISO) interference channel. Most existing works on JPAC assume the perfect instantaneous channel state information (CSI). In this paper, we consider the JPAC problem with the imperfect CSI, that is, we assume that only the channel distribution information (CDI) is available. We formulate the JPAC problem into a chance (probabilistic) constrained program, where each link's SINR outage probability is enforced to be less than or equal to a specified tolerance. To circumvent the computational difficulty of the chance SINR constraints, we propose to use the sample (scenario) approximation scheme to convert them into finitely many simple linear constraints. Furthermore, we reformulate the sample approximation of the chance SINR constrained JPAC problem as a composite group sparse minimization problem and then approximate it by a second-order cone program (SOCP). The solution of the SOCP approximation can be used to check the simultaneous supportability of all links in the network and to guide an iterative link removal procedure (the deflation approach). We exploit the special structure of the SOCP approximation and custom-design an efficient algorithm for solving it. Finally, we illustrate the effectiveness and efficiency of the proposed sample approximation-based deflation approaches by simulations.
The VC-Dimension of Graphs with Respect to k-Connected Subgraphs
Venue: arXiv cs.DM 2016
Year: 2016

We study the VC-dimension of the set system on the vertex set of some graph which is induced by the family of its $k$-connected subgraphs. In particular, we give tight upper and lower bounds for the VC-dimension. Moreover, we show that computing the VC-dimension is $\mathsf{NP}$-complete and that it remains $\mathsf{NP}$-complete for split graphs and for some subclasses of planar bipartite graphs in the cases $k = 1$ and $k = 2$. On the positive side, we observe it can be decided in linear time for graphs of bounded clique-width.
On the Inefficiency of Standard Multi-Unit Auctions
Venue: arXiv cs.GT 2016
Year: 2016

We study two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Auction, which charges every winner his winning bids. The second is the Uniform Price Auction, which determines a uniform price to be paid per unit. Variants of both formats find applications ranging from the allocation of state bonds to investors, to online sales over the internet, facilitated by popular online brokers. For these formats, we consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is more popular in practice. In this work, we evaluate the economic inefficiency of both multi-unit auction formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure Nash equilibria and mixed Bayes-Nash equilibria. Our developments improve significantly upon bounds that have been obtained recently in [Markakis, Telelis, ToCS 2014] and [Syrgkanis, Tardos, STOC 2013] for submodular valuation functions. Moreover, we consider for the first time bidders with subadditive valuation functions for these auction formats. Our results signify that these auctions are nearly efficient, which provides further justification for their use in practice.
On the Complexity of the Orbit Problem
Venue: arXiv cs.CC 2016
Year: 2016

We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem---determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NP^{RP}.
Reliable Deniable Communication: Hiding Messages in Noise
Venue: arXiv cs.IT 2016
Year: 2016

A transmitter Alice may wish to reliably transmit a message to a receiver Bob over a binary symmetric channel (BSC), while simultaneously ensuring that her transmission is deniable from an eavesdropper Willie. That is, if Willie listening to Alice's transmissions over a "significantly noisier" BSC than the one to Bob, he should be unable to estimate even whether Alice is transmitting. We consider two scenarios. In our first scenario, we assume that the channel transition probability from Alice to Bob and Willie is perfectly known to all parties. Here, even when Alice's (potential) communication scheme is publicly known to Willie (with no common randomness between Alice and Bob), we prove that over 'n' channel uses Alice can transmit a message of length O(sqrt{n}) bits to Bob, deniably from Willie. We also prove information-theoretic order-optimality of this result. In our second scenario, we allow uncertainty in the knowledge of the channel transition probability parameters. In particular, we assume that the channel transition probabilities for both Bob and Willie are uniformly drawn from a known interval. Here, we show that, in contrast to the previous setting, Alice can communicate O(n) bits of message reliably and deniably (again, with no common randomness). We give both an achievability result and a matching converse for this setting. Our work builds upon the work of Bash et al on AWGN channels (but with common randomness) and differs from other recent works (by Wang et al and Bloch) in two important ways - firstly our deniability metric is variational distance (as opposed to Kullback-Leibler divergence), and secondly, our techniques are significantly different from these works.
Reduced Gröbner Bases and Macaulay-Buchberger Basis Theorem over Noetherian Rings
Venue: arXiv cs.SC 2016
Year: 2016

In this paper, we extend the characterization of $\mathbb{Z}[x]/\ < f \ >$, where $f \in \mathbb{Z}[x]$ to be a free $\mathbb{Z}$-module to multivariate polynomial rings over any commutative Noetherian ring, $A$. The characterization allows us to extend the Gröbner basis method of computing a $\Bbbk$-vector space basis of residue class polynomial rings over a field $\Bbbk$ (Macaulay-Buchberger Basis Theorem) to rings, i.e. $A[x_1,\ldots,x_n]/\mathfrak{a}$, where $\mathfrak{a} \subseteq A[x_1,\ldots,x_n]$ is an ideal. We give some insights into the characterization for two special cases, when $A = \mathbb{Z}$ and $A = \Bbbk[θ_1,\ldots,θ_m]$. As an application of this characterization, we show that the concept of border bases can be extended to rings when the corresponding residue class ring is a finitely generated, free $A$-module.
Semantics out of context: nominal absolute denotations for first-order logic and computation
Venue: arXiv cs.LO 2016
Year: 2016

Call a semantics for a language with variables absolute when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable a is a copy of itself in the denotation. We give a trio of lattice-based, sets-based, and algebraic absolute semantics to first-order logic. Possibly open predicates are directly interpreted as lattice elements / sets / algebra elements, subject to suitable interpretations of the connectives and quantifiers. In particular, universal quantification "forall a.phi" is interpreted using a new notion of "fresh-finite" limit and using a novel dual to substitution. The interest of this semantics is partly in the non-trivial and beautiful technical details, which also offer certain advantages over existing semantics---but also the fact that such semantics exist at all suggests a new way of looking at variables and the foundations of logic and computation, which may be well-suited to the demands of modern computer science.