OpenRaiser/Intern-Atlas huggingface dataset:
Go-With-The-Winner: Client-Side Server Selection for Content Delivery
Venue: arXiv cs.NI 2016
Year: 2016

Content delivery networks deliver much of the web and video content in the world by deploying a large distributed network of servers. We model and analyze a simple paradigm for client-side server selection that is commonly used in practice where each user independently measures the performance of a set of candidate servers and selects the one that performs the best. For web (resp., video) delivery, we propose and analyze a simple algorithm where each user randomly chooses two or more candidate servers and selects the server that provided the best hit rate (resp., bit rate). We prove that the algorithm converges quickly to an optimal state where all users receive the best hit rate (resp., bit rate), with high probability. We also show that if each user chose just one random server instead of two, some users receive a hit rate (resp., bit rate) that tends to zero. We simulate our algorithm and evaluate its performance with varying choices of parameters, system load, and content popularity.
Unambiguous Buchi is weak
Venue: arXiv cs.FL 2016
Year: 2016

A non-deterministic automaton running on infinite trees is unambiguous if it has at most one accepting run on every tree. The class of languages recognisable by unambiguous tree automata is still not well-understood. In particular, decidability of the problem whether a given language is recognisable by some unambiguous automaton is open. Moreover, there are no known upper bounds on the descriptive complexity of unambiguous languages among all regular tree languages. In this paper we show the following complexity collapse: if a non-deterministic parity tree automaton $A$ is unambiguous and its priorities are between $i$ and $2n$ then the language recognised by $A$ is in the class $Comp(i+1,2n)$. A particular case of this theorem is for $i=n=1$: if $A$ is an unambiguous Buchi tree automaton then $L(A)$ is recognisable by a weak alternating automaton (or equivalently definable in weak MSO). The main motivation for this result is a theorem by Finkel and Simonnet stating that every unambiguous Buchi automaton recognises a Borel language. The assumptions of the presented theorem are syntactic (we require one automaton to be both unambiguous and of particular parity index). However, to the authors' best knowledge this is the first theorem showing a collapse of the parity index that exploits the fact that a given automaton is unambiguous.
Chasing diagrams in cryptography
Venue: arXiv cs.CR 2016
Year: 2016

Cryptography is a theory of secret functions. Category theory is a general theory of functions. Cryptography has reached a stage where its structures often take several pages to define, and its formulas sometimes run from page to page. Category theory has some complicated definitions as well, but one of its specialties is taming the flood of structure. Cryptography seems to be in need of high level methods, whereas category theory always needs concrete applications. So why is there no categorical cryptography? One reason may be that the foundations of modern cryptography are built from probabilistic polynomial-time Turing machines, and category theory does not have a good handle on such things. On the other hand, such foundational problems might be the very reason why cryptographic constructions often resemble low level machine programming. I present some preliminary explorations towards categorical cryptography. It turns out that some of the main security concepts are easily characterized through the categorical technique of *diagram chasing*, which was first used Lambek's seminal `Lecture Notes on Rings and Modules'.
Measuring and Understanding Throughput of Network Topologies
Venue: arXiv cs.NI 2016
Year: 2016

High throughput is of particular interest in data center and HPC networks. Although myriad network topologies have been proposed, a broad head-to-head comparison across topologies and across traffic patterns is absent, and the right way to compare worst-case throughput performance is a subtle problem. In this paper, we develop a framework to benchmark the throughput of network topologies, using a two-pronged approach. First, we study performance on a variety of synthetic and experimentally-measured traffic matrices (TMs). Second, we show how to measure worst-case throughput by generating a near-worst-case TM for any given topology. We apply the framework to study the performance of these TMs in a wide range of network topologies, revealing insights into the performance of topologies with scaling, robustness of performance across TMs, and the effect of scattered workload placement. Our evaluation code is freely available.
Partitioning Perfect Graphs into Stars
Venue: arXiv cs.DM 2016
Year: 2016

The partition of graphs into "nice" subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs.
Cooperation and Competition when Bidding for Complex Projects: Centralized and Decentralized Perspectives
Venue: arXiv cs.GT 2016
Year: 2016

To successfully complete a complex project, be it a construction of an airport or of a backbone IT system, agents (companies or individuals) must form a team having required competences and resources. A team can be formed either by the project issuer based on individual agents' offers (centralized formation); or by the agents themselves (decentralized formation) bidding for a project as a consortium---in that case many feasible teams compete for the contract. We investigate rational strategies of the agents (what salary should they ask? with whom should they team up?). We propose concepts to characterize the stability of the winning teams and study their computational complexity.
Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation
Venue: arXiv cs.GT 2016
Year: 2016

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of $K$ items that maximize the total derived utility of all the agents (i.e., in our example we are to pick $K$ movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.
Routing and Staffing when Servers are Strategic
Venue: arXiv cs.GT 2016
Year: 2016

Traditionally, research focusing on the design of routing and staffing policies for service systems has modeled servers as having fixed (possibly heterogeneous) service rates. However, service systems are generally staffed by people. Furthermore, people respond to workload incentives; that is, how hard a person works can depend both on how much work there is, and how the work is divided between the people responsible for it. In a service system, the routing and staffing policies control such workload incentives; and so the rate servers work will be impacted by the system's routing and staffing policies. This observation has consequences when modeling service system performance, and our objective is to investigate those consequences. We do this in the context of the M/M/N queue, which is the canonical model for large service systems. First, we present a model for "strategic" servers that choose their service rate in order to maximize a trade-off between an "effort cost", which captures the idea that servers exert more effort when working at a faster rate, and a "value of idleness", which assumes that servers value having idle time. Next, we characterize the symmetric Nash equilibrium service rate under any routing policy that routes based on the server idle time. We find that the system must operate in a quality-driven regime, in which servers have idle time, in order for an equilibrium to exist, which implies that the staffing must have a first-order term that strictly exceeds that of the common square-root staffing policy. Then, within the class of policies that admit an equilibrium, we (asymptotically) solve the problem of minimizing the total cost, when there are linear staffing costs and linear waiting costs. Finally, we end by exploring the question of whether routing policies that are based on the service rate, instead of the server idle time, can improve system performance.
On the Capacity of the 2-User Interference Channel with Transmitter Cooperation and Secrecy Constraints
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the value of limited rate cooperation between the transmitters for managing interference and simultaneously ensuring secrecy, in the 2-user Gaussian symmetric interference channel (GSIC). First, the problem is studied in the symmetric linear deterministic IC (SLDIC) setting, and achievable schemes are proposed, based on interference cancelation, relaying of the other user's data bits, and transmission of random bits. In the proposed achievable scheme, the limited rate cooperative link is used to share a combination of data bits and random bits depending on the model parameters. Outer bounds on the secrecy rate are also derived, using a novel partitioning of the encoded messages and outputs depending on the relative strength of the signal and the interference. The inner and outer bounds are derived under all possible parameter settings. It is found that, for some parameter settings, the inner and outer bounds match, yielding the capacity of the SLDIC under transmitter cooperation and secrecy constraints. In some other scenarios, the achievable rate matches with the capacity region of the 2-user SLDIC without secrecy constraints derived by Wang and Tse [1]; thus, the proposed scheme offers secrecy for free, in these cases. Inspired by the achievable schemes and outer bounds in the deterministic case, achievable schemes and outer bounds are derived in the Gaussian case. The proposed achievable scheme for the Gaussian case is based on Marton's coding scheme and stochastic encoding along with dummy message transmission. One of the key techniques used in the achievable scheme for both the models is interference cancelation, which simultaneously offers two seemingly conflicting benefits: it cancels interference and ensures secrecy. Many of the results derived in this paper extend to the asymmetric case also.
Godseed: Benevolent or Malevolent?
Venue: arXiv cs.AI 2016
Year: 2016

It is hypothesized by some thinkers that benign looking AI objectives may result in powerful AI drives that may pose an existential risk to human society. We analyze this scenario and find the underlying assumptions to be unlikely. We examine the alternative scenario of what happens when universal goals that are not human-centric are used for designing AI agents. We follow a design approach that tries to exclude malevolent motivations from AI agents, however, we see that objectives that seem benevolent may pose significant risk. We consider the following meta-rules: preserve and pervade life and culture, maximize the number of free minds, maximize intelligence, maximize wisdom, maximize energy production, behave like human, seek pleasure, accelerate evolution, survive, maximize control, and maximize capital. We also discuss various solution approaches for benevolent behavior including selfless goals, hybrid designs, Darwinism, universal constraints, semi-autonomy, and generalization of robot laws. A "prime directive" for AI may help in formulating an encompassing constraint for avoiding malicious behavior. We hypothesize that social instincts for autonomous robots may be effective such as attachment learning. We mention multiple beneficial scenarios for an advanced semi-autonomous AGI agent in the near future including space exploration, automation of industries, state functions, and cities. We conclude that a beneficial AI agent with intelligence beyond human-level is possible and has many practical use cases.
On the Symmetric $K$-user Interference Channels with Limited Feedback
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we develop achievability schemes for symmetric $K$-user interference channels with a rate-limited feedback from each receiver to the corresponding transmitter. We study this problem under two different channel models: the linear deterministic model, and the Gaussian model. For the deterministic model, the proposed scheme achieves a symmetric rate that is the minimum of the symmetric capacity with infinite feedback, and the sum of the symmetric capacity without feedback and the symmetric amount of feedback. For the Gaussian interference channel, we use lattice codes to propose a transmission strategy that incorporates the techniques of Han-Kobayashi message splitting, interference decoding, and decode and forward. This strategy achieves a symmetric rate which is within a constant number of bits to the minimum of the symmetric capacity with infinite feedback, and the sum of the symmetric capacity without feedback and the amount of symmetric feedback. This constant is obtained as a function of the number of users, $K$. The symmetric achievable rate is used to characterize the achievable generalized degrees of freedom which exhibits a gradual increase from no feedback to perfect feedback in the presence of feedback links with limited capacity.
Parameterized Complexity of the $k$-Arc Chinese Postman Problem
Venue: arXiv cs.DS 2016
Year: 2016

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges was known to be fixed-parameter tractable using a simple argument. Solving an open question of van Bevern et al., we prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. Our proof is more involved and, in particular, uses a well-known result of Marx, O'Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm.
S-Packing Colorings of Cubic Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Given a non-decreasing sequence $S=(s\_1,s\_2, \ldots, s\_k)$ of positive integers, an {\em $S$-packing coloring} of a graph $G$ is a mapping $c$ from $V(G)$ to $\{s\_1,s\_2, \ldots, s\_k\}$ such that any two vertices with color $s\_i$ are at mutual distance greater than $s\_i$, $1\le i\le k$. This paper studies $S$-packing colorings of (sub)cubic graphs. We prove that subcubic graphs are $(1,2,2,2,2,2,2)$-packing colorable and $(1,1,2,2,3)$-packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order $38$ which is not $(1,2,\ldots,12)$-packing colorable.
Maximizing Profit in Green Cellular Networks through Collaborative Games
Venue: arXiv cs.GT 2016
Year: 2016

In this paper, we deal with the problem of maximizing the profit of Network Operators (NOs) of green cellular networks in situations where Quality-of-Service (QoS) guarantees must be ensured to users, and Base Stations (BSs) can be shared among different operators. We show that if NOs cooperate among them, by mutually sharing their users and BSs, then each one of them can improve its net profit. By using a game-theoretic framework, we study the problem of forming stable coalitions among NOs. Furthermore, we propose a mathematical optimization model to allocate users to a set of BSs, in order to reduce costs and, at the same time, to meet user QoS for NOs inside the same coalition. Based on this, we propose an algorithm, based on cooperative game theory, that enables each operator to decide with whom to cooperate in order to maximize its profit. This algorithms adopts a distributed approach in which each NO autonomously makes its own decisions, and where the best solution arises without the need to synchronize them or to resort to a trusted third party. The effectiveness of the proposed algorithm is demonstrated through a thorough experimental evaluation considering real-world traffic traces, and a set of realistic scenarios. The results we obtain indicate that our algorithm allows a population of NOs to significantly improve their profits thanks to the combination of energy reduction and satisfaction of QoS requirements.
Geometric Random Edge
Venue: arXiv cs.DS 2016
Year: 2016

We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs $\max\{c^Tx \colon Ax\leq b\}$, whose constraint matrix $A$ satisfies a geometric property introduced by Brunsch and Röglin: The sine of the angle of a row of $A$ to a hyperplane spanned by $n-1$ other rows of $A$ is at least $δ$. This property is a geometric generalization of $A$ being integral and all sub-determinants of $A$ being bounded by $Δ$ in absolute value (since $δ\geq 1/(Δ^2 n)$). In particular, linear programs defined by totally unimodular matrices are captured in this famework ($δ\geq 1/ n$) for which Dyer and Frieze previously described a strongly polynomial-time randomized algorithm. The number of pivots of the simplex algorithm is polynomial in the dimension and $1/δ$ and independent of the number of constraints of the linear program. Our main result can be viewed as an algorithmic realization of the proof of small diameter for such polytopes by Bonifas et al., using the ideas of Dyer and Frieze.
Overview of the Heisenberg--Weyl Algebra and Subsets of Riordan Subgroups
Venue: arXiv cs.DM 2016
Year: 2016

In a first part, we are concerned with the relationships between polynomials in the two generators of the algebra of Heisenberg--Weyl, its Bargmann--Fock representation with differential operators and the associated one-parameter group.Upon this basis, the paper is then devoted to the groups of Riordan matrices associated to the related transformations of matrices (i.e. substitutions with prefunctions). Thereby, various properties are studied arising in Riordan arrays, in the Riordan group and, more specifically, in the `striped' Riordan subgroups; further, a striped quasigroup and a semigroup are also examined. A few applications to combinatorial structures are also briefly addressed in the Appendix.
Modeling Massive Amount of Experimental Data with Large Random Matrices in a Real-Time UWB-MIMO System
Venue: arXiv cs.IT 2016
Year: 2016

The aim of this paper is to study data modeling for massive datasets. Large random matrices are used to model the massive amount of data collected from our experimental testbed. This testbed was developed for a real-time ultra-wideband, multiple input multiple output (UWB-MIMO) system. Empirical spectral density is the relevant information we seek for. After we treat this UWB-MIMO system as a black box, we aim to model the output of the black box as a large statistical system, whose outputs can be described by (large) random matrices. This model is extremely general to allow for the study of non-linear and non-Gaussian phenomenon. The good agreements between the theoretical predictions and the empirical findings validate the correctness of the our suggested data model.
Topology of the immediate snapshot complexes
Venue: arXiv cs.DC 2016
Year: 2016

The immediate snapshot complexes were introduced as combinatorial models for the protocol complexes in the context of theoretical distributed computing. In the previous work we have developed a formal language of witness structures in order to define and to analyze these complexes. In this paper, we study topology of immediate snapshot complexes. It was known that these complexes are always pure and that they are pseudomanifolds. Here we prove two further independent topological properties. First, we show that immediate snapshot complexes are collapsible. Second, we show that these complexes are homeomorphic to closed balls. Specifically, given any immediate snapshot complex $P(\tr)$, we show that there exists a homeomorphism $φ:\da^{|\supp\tr|-1}\ra P(\tr)$, such that $φ(σ)$ is a subcomplex of $P(\tr)$, whenever $σ$ is a simplex in the simplicial complex $\da^{|\supp\tr|-1}$.
Nonparametric Detection of Anomalous Data Streams
Venue: arXiv cs.LG 2016
Year: 2016

A nonparametric anomalous hypothesis testing problem is investigated, in which there are totally n sequences with s anomalous sequences to be detected. Each typical sequence contains m independent and identically distributed (i.i.d.) samples drawn from a distribution p, whereas each anomalous sequence contains m i.i.d. samples drawn from a distribution q that is distinct from p. The distributions p and q are assumed to be unknown in advance. Distribution-free tests are constructed using maximum mean discrepancy as the metric, which is based on mean embeddings of distributions into a reproducing kernel Hilbert space. The probability of error is bounded as a function of the sample size m, the number s of anomalous sequences and the number n of sequences. It is then shown that with s known, the constructed test is exponentially consistent if m is greater than a constant factor of log n, for any p and q, whereas with s unknown, m should has an order strictly greater than log n. Furthermore, it is shown that no test can be consistent for arbitrary p and q if m is less than a constant factor of log n, thus the order-level optimality of the proposed test is established. Numerical results are provided to demonstrate that our tests outperform (or perform as well as) the tests based on other competitive approaches under various cases.
Online Edge Coloring of Paths and Trees with a Fixed Number of Colors
Venue: arXiv cs.DS 2016
Year: 2016

We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, $k$, of available colors. All of our results are with regard to competitive analysis. Previous attempts to identify optimal algorithms for this problem have failed, even for bipartite graphs. Thus, in this paper, we analyze even more restricted graph classes, paths and trees. For paths, we consider $k=2$, and for trees, we consider any $k \geq 2$. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms, on paths as well as trees. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. For trees, we prove that to obtain a better competitive ratio than First-Fit, the algorithm would have to be both randomized and unfair (i.e., reject edges that could have been colored), and even such algorithms cannot be much better than First-Fit.