OpenRaiser/Intern-Atlas huggingface dataset:
Information Theoretic cutting of a cake
Venue: arXiv cs.IT 2016
Year: 2016

Cutting a cake is a metaphor for the problem of dividing a resource (cake) among several agents. The problem becomes non-trivial when the agents have different valuations for different parts of the cake (i.e. one agent may like chocolate while the other may like cream). A fair division of the cake is one that takes into account the individual valuations of agents and partitions the cake based on some fairness criterion. Fair division may be accomplished in a distributed or centralized way. Due to its natural and practical appeal, it has been a subject of study in economics. To best of our knowledge the role of partial information in fair division has not been studied so far from an information theoretic perspective. In this paper we study two important algorithms in fair division, namely "divide and choose" and "adjusted winner" for the case of two agents. We quantify the benefit of negotiation in the divide and choose algorithm, and its use in tricking the adjusted winner algorithm. Also we analyze the role of implicit information transmission through actions for the repeated divide and choose problem by finding a trembling hand perfect equilibrium for an specific setup. Lastly we consider a centralized algorithm for maximizing the overall welfare of the agents under the Nash collective utility function (CUF). This corresponds to a clustering problem of the type traditionally studied in data mining and machine learning. Drawing a conceptual link between this problem and the portfolio selection problem in stock markets, we prove an upper bound on the increase of the Nash CUF for a clustering refinement.
Cryptanalyzing image encryption using chaotic logistic map
Venue: arXiv cs.CR 2016
Year: 2016

Chaotic behavior arises from very simple non-linear dynamical equation of logistic map which makes it was used often in designing chaotic image encryption schemes. However, some properties of chaotic maps can also facilitate cryptanalysis especially when they are implemented in digital domain. Utilizing stable distribution of the chaotic states generated by iterating the logistic map, this paper presents a typical example to show insecurity of an image encryption scheme using chaotic logistic map. This work will push encryption and chaos be combined in a more effective way.
A Polynomial Time Algorithm for Finding Area-Universal Rectangular Layouts
Venue: arXiv cs.CG 2016
Year: 2016

A rectangular layout $\mathcal{L}$ is a rectangle partitioned into disjoint smaller rectangles so that no four smaller rectangles meet at the same point. Rectangular layouts were originally used as floorplans in VLSI design to represent VLSI chip layouts. More recently, they are used in graph drawing as rectangular cartograms. In these applications, an area $a(r)$ is assigned to each rectangle $r$, and the actual area of $r$ in $\mathcal{L}$ is required to be $a(r)$. Moreover, some applications require that we use combinatorially equivalent rectangular layouts to represent multiple area assignment functions. $\mathcal{L}$ is called {\em area-universal} if any area assignment to its rectangles can be realized by a layout that is combinatorially equivalent to $\mathcal{L}$. A basic question in this area is to determine if a given plane graph $G$ has an area-universal rectangular layout or not. A fixed-parameter-tractable algorithm for solving this problem was obtained in \cite{EMSV12}. Their algorithm takes $O(2^{O(K^2)}n^{O(1)})$ time (where $K$ is the maximum number of degree 4 vertices in any minimal separation component), which is exponential time in general case. It is an open problem to find a true polynomial time algorithm for solving this problem. In this paper, we describe such a polynomial time algorithm. This paper has been revised for many versions. For previous versions, referrers who are familiar with area-universal rectangular layouts always have the same doubt for the correctness of our algorithm. They doubt that our algorithm will give a wrong output which combine two \emph{conflicting} REL together. In the current version, we realize this critical issue for the previous algorithm and we will provide two subsections 5.3 and 5.4 to solve this issue. (A backtracking algorithm to detect wrong outputs.)
Generalized Measures for the Evaluation of Community Detection Methods
Venue: arXiv cs.SI 2016
Year: 2016

Community detection can be considered as a variant of cluster analysis applied to complex networks. For this reason, all existing studies have been using tools derived from this field when evaluating community detection algorithms. However, those are not completely relevant in the context of network analysis, because they ignore an essential part of the available information: the network structure. Therefore, they can lead to incorrect interpretations. In this article, we review these measures, and illustrate this limitation. We propose a modification to solve this problem, and apply it to the three most widespread measures: purity, Rand index and normalized mutual information (NMI). We then perform an experimental evaluation on artificially generated networks with realistic community structure. We assess the relevance of the modified measures by comparison with their traditional counterparts, and also relatively to the topological properties of the community structures. On these data, the modified NMI turns out to provide the most relevant results.
Matrix Inversion Is As Easy As Exponentiation
Venue: arXiv cs.DS 2016
Year: 2016

We prove that the inverse of a positive-definite matrix can be approximated by a weighted-sum of a small number of matrix exponentials. Combining this with a previous result [OSV12], we establish an equivalence between matrix inversion and exponentiation up to polylogarithmic factors. In particular, this connection justifies the use of Laplacian solvers for designing fast semi-definite programming based algorithms for certain graph problems. The proof relies on the Euler-Maclaurin formula and certain bounds derived from the Riemann zeta function.
Representation and duality of the untyped lambda-calculus in nominal lattice and topological semantics, with a proof of topological completeness
Venue: arXiv cs.LO 2016
Year: 2016

We give a semantics for the lambda-calculus based on a topological duality theorem in nominal sets. A novel interpretation of lambda is given in terms of adjoints, and lambda-terms are interpreted absolutely as sets (no valuation is necessary).
Polynomial Bounds for the Grid-Minor Theorem
Venue: arXiv cs.DS 2016
Year: 2016

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every grid $H$, every graph whose treewidth is large enough relative to $|V(H)|$ contains $H$ as a minor. This theorem has found many applications in graph theory and algorithms. Let $f(k)$ denote the largest value such that every graph of treewidth $k$ contains a grid minor of size $(f(k)\times f(k))$. The best previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that $f(k)=Ω(\sqrt{\log k/\log \log k})$. In contrast, the best known upper bound implies that $f(k) = O(\sqrt{k/\log k})$. In this paper we obtain the first polynomial relationship between treewidth and grid minor size by showing that $f(k)=Ω(k^δ)$ for some fixed constant $δ> 0$, and describe a randomized algorithm, whose running time is polynomial in $|V(G)|$ and $k$, that with high probability finds a model of such a grid minor in $G$.
A Distributed Algorithm for Solving Positive Definite Linear Equations over Networks with Membership Dynamics
Venue: arXiv cs.SY 2016
Year: 2016

This paper considers the problem of solving a symmetric positive definite system of linear equations over a network of agents with arbitrary asynchronous interactions and membership dynamics. The latter implies that each agent is allowed to join and leave the network at any time, for infinitely many times, and lose all its memory upon leaving. We develop Subset Equalizing (SE), a distributed asynchronous algorithm for solving such a problem. To design and analyze SE, we introduce a novel time-varying Lyapunov-like function, defined on a state space with changing dimension, and a generalized concept of network connectivity, capable of handling such interactions and membership dynamics. Based on them, we establish the boundedness, asymptotic convergence, and exponential convergence of SE, along with a bound on its convergence rate. Finally, through extensive simulation, we show that SE is effective in a volatile agent network and that a special case of SE, termed Groupwise Equalizing, is significantly more bandwidth/energy efficient than two existing algorithms in multi-hop wireless networks.
MathGR: a tensor and GR computation package to keep it simple
Venue: arXiv cs.MS 2016
Year: 2016

We introduce the MathGR package, written in Mathematica. The package can manipulate tensor and GR calculations with either abstract or explicit indices, simplify tensors with permutational symmetries, decompose tensors from abstract indices to partially or completely explicit indices and convert partial derivatives into total derivatives. Frequently used GR tensors and a model of FRW universe with ADM type perturbations are predefined. The package is built around the philosophy to "keep it simple", and makes use of latest tensor technologies of Mathematica.
One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries
Venue: arXiv cs.CC 2016
Year: 2016

We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes, which is a preorder, and completely describe the resulting hierarchy given by this relation. This relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free first-order reduction. In doing so, we obtain a significantly refined complexity classification of homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.
Linear Time Computation of the Maximal Linear and Circular Sums of Multiple Independent Insertions into a Sequence
Venue: arXiv cs.DS 2016
Year: 2016

The maximal sum of a sequence "A" of "n" real numbers is the greatest sum of all elements of any strictly contiguous and possibly empty subsequence of "A", and it can be computed in "O(n)" time by means of Kadane's algorithm. Letting "A^(x -> p)" denote the sequence which results from inserting a real number "x" between elements "A[p-1]" and "A[p]", we show how the maximal sum of "A^(x -> p)" can be computed in "O(1)" worst-case time for any given "x" and "p", provided that an "O(n)" time preprocessing step has already been executed on "A". In particular, this implies that, given "m" pairs "(x_0, p_0), ..., (x_{m-1}, p_{m-1})", we can compute the maximal sums of sequences "A^(x_0 -> p_0), ..., A^(x_{m-1} -> p_{m-1})" in "O(n+m)" time, which matches the lower bound imposed by the problem input size, and also improves on the straightforward strategy of applying Kadane's algorithm to each sequence "A^(x_i -> p_i)", which takes a total of "Theta(n.m)" time. Our main contribution, however, is to obtain the same time bound for the more complicated problem of computing the greatest sum of all elements of any strictly or circularly contiguous and possibly empty subsequence of "A^(x -> p)". Our algorithms are easy to implement in practice, and they were motivated by and find application in a buffer minimization problem on wireless mesh networks.
Cooperative Relaying in Wireless Networks under Spatially and Temporally Correlated Interference
Venue: arXiv cs.IT 2016
Year: 2016

We analyze the performance of an interference-limited, decode-and-forward, cooperative relaying system that comprises a source, a destination, and $N$ relays, placed arbitrarily on the plane and suffering from interference by a set of interferers placed according to a spatial Poisson process. In each transmission attempt, first the transmitter sends a packet; subsequently, a single one of the relays that received the packet correctly, if such a relay exists, retransmits it. We consider both selection combining and maximal ratio combining at the destination, Rayleigh fading, and interferer mobility. We derive expressions for the probability that a single transmission attempt is successful, as well as for the distribution of the transmission attempts until a packet is transmitted successfully. Results provide design guidelines applicable to a wide range of systems. Overall, the temporal and spatial characteristics of the interference play a significant role in shaping the system performance. Maximal ratio combining is only helpful when relays are close to the destination; in harsh environments, having many relays is especially helpful, and relay placement is critical; the performance improves when interferer mobility increases; and a tradeoff exists between energy efficiency and throughput.
Approximate Constraint Satisfaction Requires Large LP Relaxations
Venue: arXiv cs.CC 2016
Year: 2016

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.
How Relevant Are Chess Composition Conventions?
Venue: arXiv cs.AI 2016
Year: 2016

Composition conventions are guidelines used by human composers in composing chess problems. They are particularly significant in composition tournaments. Examples include, not having any check in the first move of the solution and not dressing up the board with unnecessary pieces. Conventions are often associated or even directly conflated with the overall aesthetics or beauty of a composition. Using an existing experimentally-validated computational aesthetics model for three-move mate problems, we analyzed sets of computer-generated compositions adhering to at least 2, 3 and 4 comparable conventions to test if simply conforming to more conventions had a positive effect on their aesthetics, as is generally believed by human composers. We found slight but statistically significant evidence that it does, but only to a point. We also analyzed human judge scores of 145 three-move mate problems composed by humans to see if they had any positive correlation with the computational aesthetic scores of those problems. We found that they did not. These seemingly conflicting findings suggest two main things. First, the right amount of adherence to composition conventions in a composition has a positive effect on its perceived aesthetics. Second, human judges either do not look at the same conventions related to aesthetics in the model used or emphasize others that have less to do with beauty as perceived by the majority of players, even though they may mistakenly consider their judgements beautiful in the traditional, non-esoteric sense. Human judges may also be relying significantly on personal tastes as we found no correlation between their individual scores either.
Abelian networks I. Foundations and examples
Venue: arXiv cs.FL 2016
Year: 2016

In Deepak Dhar's model of abelian distributed processors, automata occupy the vertices of a graph and communicate via the edges. We show that two simple axioms ensure that the final output does not depend on the order in which the automata process their inputs. A collection of automata obeying these axioms is called an "abelian network". We prove a least action principle for abelian networks. As an application, we show how abelian networks can solve certain linear and nonlinear integer programs asynchronously. In most previously studied abelian networks, the input alphabet of each automaton consists of a single letter; in contrast, we propose two non-unary examples of abelian networks: "oil and water" and "abelian mobile agents".
Superadditivity of Quantum Channel Coding Rate with Finite Blocklength Joint Measurements
Venue: arXiv cs.IT 2016
Year: 2016

The maximum rate at which classical information can be reliably transmitted per use of a quantum channel strictly increases in general with $N$, the number of channel outputs that are detected jointly by the quantum joint-detection receiver (JDR). This phenomenon is known as superadditivity of the maximum achievable information rate over a quantum channel. We study this phenomenon for a pure-state classical-quantum (cq) channel and provide a lower bound on $C_N/N$, the maximum information rate when the JDR is restricted to making joint measurements over no more than $N$ quantum channel outputs, while allowing arbitrary classical error correction. We also show the appearance of a superadditivity phenomenon---of mathematical resemblance to the aforesaid problem---in the channel capacity of a classical discrete memoryless channel (DMC) when a concatenated coding scheme is employed, and the inner decoder is forced to make hard decisions on $N$-length inner codewords. Using this correspondence, we develop a unifying framework for the above two notions of superadditivity, and show that for our lower bound to $C_N/N$ to be equal to a given fraction of the asymptotic capacity $C$ of the respective channel, $N$ must be proportional to $V/C^2$, where $V$ is the respective channel dispersion quantity.
Modelling Families of Business Process Variants: A Decomposition Driven Method
Venue: arXiv cs.SE 2016
Year: 2016

Business processes usually do not exist as singular entities that can be managed in isolation, but rather as families of business process variants. When modelling such families of variants, analysts are confronted with the choice between modelling each variant separately, or modelling multiple or all variants in a single model. Modelling each variant separately leads to a proliferation of models that share common parts, resulting in redundancies and inconsistencies. Meanwhile, modelling all variants together leads to less but more complex models, thus hindering on comprehensibility. This paper introduces a method for modelling families of process variants that addresses this trade-off. The key tenet of the method is to alternate between steps of decomposition (breaking down processes into sub-processes) and deciding which parts should be modelled together and which ones should be modelled separately. We have applied the method to two case studies: one concerning the consolidation of ex-isting process models, and another dealing with green-field process discovery. In both cases, the method produced fewer models with respect to the baseline and reduced duplicity by up to 50% without significant impact on complexity.
On optimal constacyclic codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we investigate the class of constacyclic codes, which is a natural generalization of the class of cyclic and negacyclic codes. This class of codes is interesting in the sense that it contains codes with good or even optimal parameters. In this light, we propose constructions of families of classical block and convolutional maximum-distance-separable (MDS) constacyclic codes, as well as families of asymmetric quantum MDS codes derived from (classical-block) constacyclic codes. These results are mainly derived from the investigation of suitable properties on cyclotomic cosets of these corresponding codes.
A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays
Venue: arXiv cs.DS 2016
Year: 2016

Given a $d$-dimensional array $A$, an update operation adds a given constant $C$ to each element within a continuous sub-array of $A$. A query operation computes the sum of all the elements within a continuous sub-array of $A$. The one-dimensional update and query handling problem has been studied intensively and is usually solved using segment trees with lazy propagation technique. In this paper, we present a new algorithm incorporating Binary Indexed Trees and Inclusion-Exclusion Principle to accomplish the same task. We extend the algorithm to update and query sub-matrices of matrices (two-dimensional array). Finally, we propose a general form of the algorithm for $d$-dimensions which achieves $\mathcal{O}(4^d*\log^{d}n)$ time complexity for both updates and queries. This is an improvement over the previously known algorithms which utilize hierarchical data structures like quadtrees and octrees and have a worst-case time complexity of $Ω(n^{d-1})$ per update/query.
Multiuser Random Coding Techniques for Mismatched Decoding
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth's achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth's achievable rate region is given, and the latter is shown to extend immediately to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters.
Robust Equilibria in Concurrent Games
Venue: arXiv cs.GT 2016
Year: 2016

We study the problem of finding robust equilibria in multiplayer concurrent games with mean payoff objectives. A $(k,t)$-robust equilibrium is a strategy profile such that no coalition of size $k$ can improve the payoff of one its member by deviating, and no coalition of size $t$ can decrease the payoff of other players. We are interested in pure equilibria, that is, solutions that can be implemented using non-randomized strategies. We suggest a general transformation from multiplayer games to two-player games such that pure equilibria in the first game correspond to winning strategies in the second one. We then devise from this transformation, an algorithm which computes equilibria in mean-payoff games. Robust equilibria in mean-payoff games reduce to winning strategies in multidimensional mean-payoff games for some threshold satisfying some constraints. We then show that the existence of such equilibria can be decided in polynomial space, and that the decision problem is PSPACE-complete.