OpenRaiser/Intern-Atlas huggingface dataset:
An optimal representation for the trace zero subgroup
Venue: arXiv cs.CR 2016
Year: 2016

We give an optimal-size representation for the elements of the trace zero subgroup of the Picard group of an elliptic or hyperelliptic curve of any genus, with respect to a field extension of any prime degree. The representation is via the coefficients of a rational function, and it is compatible with scalar multiplication of points. We provide efficient compression and decompression algorithms, and complement them with implementation results. We discuss in detail the practically relevant cases of small genus and extension degree, and compare with the other known compression methods.
Weak topologies for Linear Logic
Venue: arXiv cs.LO 2016
Year: 2016

We construct a denotational model of linear logic, whose objects are all the locally convex and separated topological vector spaces endowed with their weak topology. The negation is interpreted as the dual, linear proofs are interpreted as continuous linear functions, and non-linear proofs as sequences of monomials. We do not complete our constructions by a double-orthogonality operation. This yields an interpretation of the polarity of the connectives in terms of topology.
Exact Solutions for M/M/c/Setup Queues
Venue: arXiv cs.PF 2016
Year: 2016

Recently multiserver queues with setup times have been extensively studied because they have applications in power-saving data centers. The most challenging model is the M/M/$c$/Setup queue where a server is turned off when it is idle and is turned on if there are some waiting jobs. Recently, Gandhi et al.~(SIGMETRICS 2013, QUESTA 2014) present the recursive renewal reward approach as a new mathematical tool to analyze the model. In this paper, we derive exact solutions for the same model using two alternative methodologies: generating function approach and matrix analytic method. The former yields several theoretical insights into the systems while the latter provides an exact recursive algorithm to calculate the joint stationary distribution and then some performance measures so as to give new application insights.
Universal Compressed Sensing
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the problem of developing universal algorithms for compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then a minimum entropy pursuit (MEP) optimization approach is proposed, and it is proven that it can reliably recover any stationary process satisfying some mixing constraints from sufficient number of randomized linear measurements, without having any prior information about the distribution of the process. It is proved that a Lagrangian-type approximation of the MEP optimization problem, referred to as Lagrangian-MEP problem, is identical to a heuristic implementable algorithm proposed by Baron et al. It is shown that for the right choice of parameters the Lagrangian-MEP algorithm, in addition to having the same asymptotic performance as MEP optimization, is also robust to the measurement noise. For memoryless sources with a discrete-continuous mixture distribution, the fundamental limits of the minimum number of required measurements by a non-universal compressed sensing decoder is characterized by Wu et al. For such sources, it is proved that there is no loss in universal coding, and both the MEP and the Lagrangian-MEP asymptotically achieve the optimal performance.
Computing the flip distance between triangulations
Venue: arXiv cs.DS 2016
Year: 2016

Let ${\cal T}$ be a triangulation of a set ${\cal P}$ of $n$ points in the plane, and let $e$ be an edge shared by two triangles in ${\cal T}$ such that the quadrilateral $Q$ formed by these two triangles is convex. A {\em flip} of $e$ is the operation of replacing $e$ by the other diagonal of $Q$ to obtain a new triangulation of ${\cal P}$ from ${\cal T}$. The {\em flip distance} between two triangulations of ${\cal P}$ is the minimum number of flips needed to transform one triangulation into the other. The Flip Distance problem asks if the flip distance between two given triangulations of ${\cal P}$ is at most $k$, for some given $k \in N$. It is a fundamental and a challenging problem. We present an algorithm for the {\sc Flip Distance} problem that runs in time $O(n + k \cdot c^{k})$, for a constant $c \leq 2 \cdot 14^{11}$, which implies that the problem is fixed-parameter tractable. We extend our results to triangulations of polygonal regions with holes, and to labeled triangulated graphs.
Sum-of-squares hierarchy lower bounds for symmetric formulations
Venue: arXiv cs.DS 2016
Year: 2016

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of "well-behaved" univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the Min-Knapsack linear program strengthened with cover inequalities.
Balanced Allocation on Graphs: A Random Walk Approach
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we propose algorithms for allocating $n$ sequential balls into $n$ bins that are interconnected as a $d$-regular $n$-vertex graph $G$, where $d\ge3$ can be any integer.Let $l$ be a given positive integer. In each round $t$, $1\le t\le n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node.Then it allocates itself on one of the visited nodes with minimum load (ties are broken uniformly at random). Suppose that $G$ has a sufficiently large girth and $d=ω(\log n)$. Then we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm, called {\it maximum load}, in terms of $l$ with high probability. We also show that the upper bound is at most an $O(\log\log n)$ factor above the lower bound that is proved for the algorithm. In particular, we show that if we set $l=\lfloor(\log n)^{\frac{1+ε}{2}}\rfloor$, for every constant $ε\in (0, 1)$, and $G$ has girth at least $ω(l)$, then the maximum load attained by the algorithm is bounded by $O(1/ε)$ with high probability.Finally, we slightly modify the algorithm to have similar results for balanced allocation on $d$-regular graph with $d\in[3, O(\log n)]$ and sufficiently large girth.
Optimizing Performance of Continuous-Time Stochastic Systems using Timeout Synthesis
Venue: arXiv cs.PF 2016
Year: 2016

We consider parametric version of fixed-delay continuous-time Markov chains (or equivalently deterministic and stochastic Petri nets, DSPN) where fixed-delay transitions are specified by parameters, rather than concrete values. Our goal is to synthesize values of these parameters that, for a given cost function, minimise expected total cost incurred before reaching a given set of target states. We show that under mild assumptions, optimal values of parameters can be effectively approximated using translation to a Markov decision process (MDP) whose actions correspond to discretized values of these parameters.
M$^2$I: Channel Modeling for Metamaterial-Enhanced Magnetic Induction Communications
Venue: arXiv cs.OH 2016
Year: 2016

Magnetic Induction (MI) communication technique has shown great potentials in complex and RF-challenging environments, such as underground and underwater, due to its advantage over EM wave-based techniques in penetrating lossy medium. However, the transmission distance of MI techniques is limited since magnetic field attenuates very fast in the near field. To this end, this paper proposes Metamaterial-enhanced Magnetic Induction (M$^2$I) communication mechanism, where a MI coil antenna is enclosed by a metamaterial shell that can enhance the magnetic fields around the MI transceivers. As a result, the M$^2$I communication system can achieve tens of meters communication range by using pocket-sized antennas. In this paper, an analytical channel model is developed to explore the fundamentals of the M$^2$I mechanism, in the aspects of communication range and channel capacity, and the susceptibility to various hostile and complex environments. The theoretical model is validated through the finite element simulation software, Comsol Multiphysics. Proof-of-concept experiments are also conducted to validate the feasibility of M$^2$I.
Partition-Symmetrical Entropy Functions
Venue: arXiv cs.IT 2016
Year: 2016

Let $\cal{N}=\{1,\cdots,n\}$. The entropy function $\bf h$ of a set of $n$ discrete random variables $\{X_i:i\in\cal N\}$ is a $2^n$-dimensional vector whose entries are ${\bf{h}}({\cal{A}})\triangleq H(X_{\cal{A}}),\cal{A}\subset{\cal N} $, the (joint) entropies of the subsets of the set of $n$ random variables with $H(X_\emptyset)=0$ by convention. The set of all entropy functions for $n$ discrete random variables, denoted by $Γ^*_n$, is called the entropy function region for $n$. Characterization of $Γ^*_n$ and its closure $\overline{Γ^*_n}$ are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider \emph{partition-symmetrical entropy functions}. Let $p=\{\cal{N}_1,\cdots, \cal{N}_t\}$ be a $t$-partition of $\cal N$. An entropy function $\bf h$ is called $p$-symmetrical if for all ${\cal A},{\cal B} \subset {\cal N}$, $\bf{h}({\cal A}) = \bf{h}({\cal B})$ whenever $|{\cal A} \cap {\cal N}_i| = |{\cal B} \cap {\cal N}_i|$, $i = 1, \cdots,t$. The set of all the $p$-symmetrical entropy functions, denoted by $Ψ^*_p$, is called $p$-symmetrical entropy function region. We prove that $\overline{Ψ^*_p}$, the closure of $Ψ^*_p$, is completely characterized by Shannon-type information inequalities if and only if $p$ is the $1$-partition or a $2$-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems. Keywords: entropy, entropy function, information inequality, polymatroid.
Population fluctuation promotes cooperation in networks
Venue: arXiv cs.GT 2016
Year: 2016

We consider the problem of explaining the emergence and evolution of cooperation in dynamic network-structured populations. Building on seminal work by Poncela et al, which shows how cooperation (in one-shot prisoner's dilemma) is supported in growing populations by an evolutionary preferential attachment (EPA) model, we investigate the effect of fluctuations in the population size. We find that the fluctuating model is more robust than Poncela et al's in that cooperation flourishes for a wide variety of initial conditions. In terms of both the temptation to defect, and the types of strategies present in the founder network, the fluctuating population is found to lead more securely to cooperation. Further, we find that this model will also support the emergence of cooperation from pre-existing non-cooperative random networks. This model, like Poncela et al's, does not require agents to have memory, recognition of other agents, or other cognitive abilities, and so may suggest a more general explanation of the emergence of cooperation in early evolutionary transitions, than mechanisms such as kin selection, direct and indirect reciprocity.
Justified Representation in Approval-Based Committee Voting
Venue: arXiv cs.MA 2016
Year: 2016

We consider approval-based committee voting, i.e. the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. However, it turns out that several prominent approval-based voting rules may fail to output such a committee. In particular, while Proportional Approval Voting (PAV) always outputs a committee that provides JR, Reweighted Approval Voting (RAV), a tractable approximation to PAV, does not have this property. We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules we consider do not; indeed, EJR can be used to characterize PAV within the class of weighted PAV rules. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and core stability, and the complexity of the associated algorithmic problems.
On optimal approximability results for computing the strong metric dimension
Venue: arXiv cs.CC 2016
Year: 2016

The strong metric dimension of a graph was first introduced by Sebö and Tannier (Mathematics of Operations Research, 29(2), 383-393, 2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 549-559, 1975) and by Harary and Melter (Ars Combinatoria, 2, 191-195, 1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP-complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of $n$ nodes admits a polynomial-time $2$-approximation, admits a $O^\ast\big(2^{\,0.287\,n}\big)$-time exact computation algorithm, admits a $O\big(1.2738^k+n\,k\big)$-time exact computation algorithm if the strong metric dimension is at most $k$, does not admit a polynomial time $(2-\varepsilon)$-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time $(10\sqrt{5}-21-\varepsilon)$-approximation algorithm assuming P$\neq$NP, does not admit a $O^\ast\big(2^{o(n)}\big)$-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a $O^\ast\big(n^{o(k)}\big)$-time exact computation algorithm if the strong metric dimension is at most $k$ assuming the exponential time hypothesis is true.
On the Information Loss of the Max-Log Approximation in BICM Systems
Venue: arXiv cs.IT 2016
Year: 2016

We present a comprehensive study of the information rate loss of the max-log approximation for $M$-ary pulse-amplitude modulation (PAM) in a bit-interleaved coded modulation (BICM) system. It is widely assumed that the calculation of L-values using the max-log approximation leads to an information loss. We prove that this assumption is correct for all $M$-PAM constellations and labelings with the exception of a symmetric 4-PAM constellation labeled with a Gray code. We also show that for max-log L-values, the BICM generalized mutual information (GMI), which is an achievable rate for a standard BICM decoder, is too pessimistic. In particular, it is proved that the so-called "harmonized" GMI, which can be seen as the sum of bit-level GMIs, is achievable without any modifications to the decoder. We then study how bit-level channel symmetrization and mixing affect the mutual information (MI) and the GMI for max-log L-values. Our results show that these operations, which are often used when analyzing BICM systems, preserve the GMI. However, this is not necessarily the case when the MI is considered. Necessary and sufficient conditions under which these operations preserve the MI are provided.
Robust Adaptive Routing Under Uncertainty
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of finding an optimal history-dependent routing strategy on a directed graph weighted by stochastic arc costs when the objective is to minimize the risk of spending more than a prescribed budget. To help mitigate the impact of the lack of information on the arc cost probability distributions, we introduce a robust counterpart where the distributions are only known through confidence intervals on some statistics such as the mean, the mean absolute deviation, and any quantile. Leveraging recent results in distributionally robust optimization, we develop a general-purpose algorithm to compute an approximate optimal strategy. To illustrate the benefits of the robust approach, we run numerical experiments with field data from the Singapore road network.
The Likelihood Encoder for Lossy Compression
Venue: arXiv cs.IT 2016
Year: 2016

A likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on the soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma yields simple achievability proofs for classical source coding problems. The cases of the point-to-point rate-distortion function, the rate-distortion function with side information at the decoder (i.e. the Wyner-Ziv problem), and the multi-terminal source coding inner bound (i.e. the Berger-Tung problem) are examined in this paper. Furthermore, a non-asymptotic analysis is used for the point-to-point case to examine the upper bound on the excess distortion provided by this method. The likelihood encoder is also related to a recent alternative technique using properties of random binning.
Fragility of the Commons under Prospect-Theoretic Risk Attitudes
Venue: arXiv cs.GT 2016
Year: 2016

We study a common-pool resource game where the resource experiences failure with a probability that grows with the aggregate investment in the resource. To capture decision making under such uncertainty, we model each player's risk preference according to the value function from prospect theory. We show the existence and uniqueness of a pure Nash equilibrium when the players have heterogeneous risk preferences and under certain assumptions on the rate of return and failure probability of the resource. Greater competition, vis-a-vis the number of players, increases the failure probability at the Nash equilibrium; we quantify this effect by obtaining bounds on the ratio of the failure probability at the Nash equilibrium to the failure probability under investment by a single user. We further show that heterogeneity in attitudes towards loss aversion leads to higher failure probability of the resource at the equilibrium.
Text Line Identification in Tagore's Manuscript
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a text line identification method is proposed. The text lines of printed document are easy to segment due to uniform straightness of the lines and sufficient gap between the lines. But in handwritten documents, the line is non-uniform and interline gaps are variable. We take Rabindranath Tagore's manuscript as it is one of the most difficult manuscripts that contain doodles. Our method consists of a pre-processing stage to clean the document image. Then we separate doodles from the manuscript to get the textual region. After that we identify the text lines on the manuscript. For text line identification, we use window examination, black run-length smearing, horizontal histogram and connected component analysis.
Computational complexity of solving polynomial differential equations over unbounded domains
Venue: arXiv cs.CC 2016
Year: 2016

In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) $y^{\prime}=p(y)$ over \emph{unbounded time domains}, where $p$ is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the "intuition" that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute. We present algorithms which numerically solve these ODEs over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time $t$ and error bound $\varepsilon$ as input, they will output a value $\tilde{y}$ which satisfies $\|y(t)-\tilde{y}\|\leq\varepsilon$. We analyze the complexity of these algorithms and show that they compute $\tilde{y}$ in time polynomial in several quantities including the time $t$, the accuracy of the output $\varepsilon$ and the length of the curve $y$ from $0$ to $t$, assuming it exists until time $t$. We consider both algebraic complexity and bit complexity.
Combinatorial Algorithm for Restricted Max-Min Fair Allocation
Venue: arXiv cs.DS 2016
Year: 2016

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of $4 + ε$. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee. In this paper we significantly narrow this gap by giving a $13$-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [Hax95] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [AFS12]. For our local search procedure to terminate in polynomial time, we introduce several new ideas such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis.
Observationally-induced algebras in Domain Theory
Venue: arXiv cs.LO 2016
Year: 2016

In this paper we revise and simplify the notion of observationally induced algebra introduced by Simpson and Schroeder for the purpose of modelling computational effects in the particular case where the ambient category is given by classical domain theory. As examples of the general framework we consider the various powerdomains. For the particular case of the Plotkin powerdomain the general recipe leads to a somewhat unexpected result which, however, makes sense from a Computer Science perspective. We analyze this "deviation" and show how to reobtain the original Plotkin powerdomain by imposing further conditions previously considered by R.~Heckmann and J.~Goubault-Larrecq.