OpenRaiser/Intern-Atlas huggingface dataset:
Chasing the k-colorability threshold
Venue: arXiv cs.DM 2014
Year: 2014

Over the past decade, physicists have developed deep but non-rigorous techniques for studying phase transitions in discrete structures. Recently, their ideas have been harnessed to obtain improved rigorous results on the phase transitions in binary problems such as random $k$-SAT or $k$-NAESAT (e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous arguments, typically centered around the second moment method, do not extend easily to problems where there are more than two possible values per variable. The single most intensely studied example of such a problem is random graph $k$-coloring. Here we develop a novel approach to the second moment method in this problem. This new method, inspired by physics conjectures on the geometry of the set of $k$-colorings, allows us to establish a substantially improved lower bound on the $k$-colorability threshold. The new lower bound is within an additive $2\ln 2+o_k(1)\approx 1.39$ of a simple first-moment upper bound and within $2\ln 2-1+o_k(1)\approx 0.39$ of the physics conjecture. By comparison, the best previous lower bound left a gap of about $2+\ln k$, unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004].
Balancing parallel assembly lines with disabled workers
Venue: arXiv cs.DM 2014
Year: 2014

We study an assembly line balancing problem that occurs in sheltered worker centers for the disabled, where workers with very different characteristics are present. We are interested in the situation in which parallel assembly lines are allowed and name the resulting problem as parallel assembly line worker assignment and balancing problem. We present a linear mixed-integer formulation and a four-stage heuristic algorithm. Computational results with a large set of instances recently proposed in the literature show the advantages of allowing alternative line layouts.
The complexity of interior point methods for solving discounted turn-based stochastic games
Venue: arXiv cs.GT 2014
Year: 2014

We study the problem of solving discounted, two player, turn based, stochastic games (2TBSGs). Jurdzinski and Savani showed that 2TBSGs with deterministic transitions can be reduced to solving $P$-matrix linear complementarity problems (LCPs). We show that the same reduction works for general 2TBSGs. This implies that a number of interior point methods for solving $P$-matrix LCPs can be used to solve 2TBSGs. We consider two such algorithms. First, we consider the unified interior point method of Kojima, Megiddo, Noma, and Yoshise, which runs in time $O((1+κ)n^{3.5}L)$, where $κ$ is a parameter that depends on the $n \times n$ matrix $M$ defining the LCP, and $L$ is the number of bits in the representation of $M$. Second, we consider the interior point potential reduction algorithm of Kojima, Megiddo, and Ye, which runs in time $O(\frac{-δ}θn^4\log ε^{-1})$, where $δ$ and $θ$ are parameters that depend on $M$, and $ε$ describes the quality of the solution. For 2TBSGs with $n$ states and discount factor $γ$ we prove that in the worst case $κ= Θ(n/(1-γ)^2)$, $-δ= Θ(\sqrt{n}/(1-γ))$, and $1/θ= Θ(n/(1-γ)^2)$. The lower bounds for $κ$, $-δ$, and $1/θ$ are obtained using the same family of deterministic games.
Learning Coverage Functions and Private Release of Marginals
Venue: arXiv cs.LG 2014
Year: 2014

We study the problem of approximating and learning coverage functions. A function $c: 2^{[n]} \rightarrow \mathbf{R}^{+}$ is a coverage function, if there exists a universe $U$ with non-negative weights $w(u)$ for each $u \in U$ and subsets $A_1, A_2, \ldots, A_n$ of $U$ such that $c(S) = \sum_{u \in \cup_{i \in S} A_i} w(u)$. Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any $γ,δ>0$, given random and uniform examples of an unknown coverage function $c$, finds a function $h$ that approximates $c$ within factor $1+γ$ on all but $δ$-fraction of the points in time $poly(n,1/γ,1/δ)$. This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess $\ell_1$-error $ε$ over all product and symmetric distributions in time $n^{\log(1/ε)}$. In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time $2^{\tilde{O}(n^{1/3})}$ (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low average error. In particular, for any $k \leq n$, we obtain private release of $k$-way marginals with average error $\barα$ in time $n^{O(\log(1/\barα))}$.
Throughput Optimal Scheduling Policies in Networks of Interacting Queues
Venue: arXiv cs.PF 2014
Year: 2014

This report considers a fairly general model of constrained queuing networks that allows us to represent both MMBP (Markov Modulated Bernoulli Processes) arrivals and time-varying service constraints. We derive a set of sufficient conditions for throughput optimality of scheduling policies that encompass and generalize all the previously obtained results in the field. This leads to the definition of new classes of (non diagonal) throughput optimal scheduling policies. We prove the stability of queues by extending the traditional Lyapunov drift criteria methodology.
On the Relation between Context-Free Grammars and Parsing Expression Grammars
Venue: arXiv cs.FL 2014
Year: 2014

Context-Free Grammars (CFGs) and Parsing Expression Grammars (PEGs) have several similarities and a few differences in both their syntax and semantics, but they are usually presented through formalisms that hinder a proper comparison. In this paper we present a new formalism for CFGs that highlights the similarities and differences between them. The new formalism borrows from PEGs the use of parsing expressions and the recognition-based semantics. We show how one way of removing non-determinism from this formalism yields a formalism with the semantics of PEGs. We also prove, based on these new formalisms, how LL(1) grammars define the same language whether interpreted as CFGs or as PEGs, and also show how strong-LL(k), right-linear, and LL-regular grammars have simple language-preserving translations from CFGs to PEGs.
Decidability of Weak Simulation on One-counter Nets
Venue: arXiv cs.FL 2014
Year: 2014

One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with only a weak test for zero. We show that weak simulation preorder is decidable for OCN and that weak simulation approximants do not converge at level omega, but only at omega^2. In contrast, other semantic relations like weak bisimulation are undecidable for OCN, and so are weak (and strong) trace inclusion.
Quality of Real-Time Streaming in Wireless Cellular Networks - Stochastic Modeling and Analysis
Venue: arXiv cs.NI 2014
Year: 2014

We present a new stochastic service model with capacity sharing and interruptions, appropriate for the evaluation of the quality of real-time streaming (RTS), like e.g. mobile TV, in wireless cellular networks. The general model takes into account multi-class Markovian process of call arrivals, (to capture different radio channel conditions, requested streaming bit-rates and durations) and allows for a general resource allocation policy saying which users are temporarily denied the requested fixed streaming bit-rates (put in outage) due to resource constraints. We give expressions for several important performance characteristics of the model, including mean time spent in outage and mean number of outage incidents for a typical user of a given class. These expressions involve only stationary probabilities of the (free) traffic demand process, which is a vector of independent Poisson random variables describing the number of users of different classes. In order to analyze RTS in 3GPP Long Term Evolution (LTE) cellular networks, we specify our general model assuming orthogonal user channels with the peak bit-rates close to the theoretical Shannon's bound in the additive white Gaussian noise (AWGN) channel, which leads to the resource constraints in a multi-rate linear form. In this setting we consider a natural class of least-effort-served-first resource allocation policies, for which the characteristics of the model can be further evaluated using Fourier analysis of Poisson variables. Within this class we identify and evaluate an optimal and a fair policy, the latter being suggested by LTE implementations. We also propose some intermediate policies, which allow to solve the optimality/fairness tradeoff caused by unequal user radio-channel conditions. Our results can be used for the evaluation of the quality of RTS in LTE networks and dimensioning of these networks.
Assignment Games with Conflicts: Price of Total Anarchy and Convergence Results via Semi-Smoothness
Venue: arXiv cs.GT 2014
Year: 2014

We study assignment games in which jobs select machines, and in which certain pairs of jobs may conflict, which is to say they may incur an additional cost when they are both assigned to the same machine, beyond that associated with the increase in load. Questions regarding such interactions apply beyond allocating jobs to machines: when people in a social network choose to align themselves with a group or party, they typically do so based upon not only the inherent quality of that group, but also who amongst their friends (or enemies) choose that group as well. We show how semi-smoothness, a recently introduced generalization of smoothness, is necessary to find tight or near-tight bounds on the price of total anarchy, and thus on the quality of correlated and Nash equilibria, for several natural job-assignment games with interacting jobs. For most cases, our bounds on the price of total anarchy are either exactly 2 or approach 2. We also prove new convergence results implied by semi-smoothness for our games. Finally we consider coalitional deviations, and prove results about the existence and quality of Strong equilibrium.
Complexity Classifications for logic-based Argumentation
Venue: arXiv cs.CC 2014
Year: 2014

We consider logic-based argumentation in which an argument is a pair (Fi,al), where the support Fi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by De) that entails the claim al (a formula). We study the complexity of three central problems in argumentation: the existence of a support Fi ss De, the validity of a support and the relevance problem (given psi is there a support Fi such that psi ss Fi?). When arguments are given in the full language of propositional logic these problems are computationally costly tasks, the validity problem is DP-complete, the others are SigP2-complete. We study these problems in Schaefer's famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints build upon a fixed finite set of Boolean relations Ga (the constraint language). We show that according to the properties of this language Ga, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or SigP2-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or SigP2-complete. These last two classifications are obtained by means of algebraic tools.
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
Venue: arXiv cs.CC 2014
Year: 2014

The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs: Input instance: four lists of positive integers: a_1, ...., a_n ; b_1,...., b_n ; c_1,....,c_m ; d_1, ...., d_m ; where each of the integers is represented in binary. Problem 1 (equality testing): Decide whether a_1^{b_1} a_2^{b_2} .... a_n^{b_n} = c_1^{d_1} c_2^{d_2} .... c_m^{d_m} . Problem 2 (inequality testing): Decide whether a_1^{b_1} a_2^{b_2} ... a_n^{b_n} >= c_1^{d_1} c_2^{d_2} .... c_m^{d_m} . Problem 1 is easily decidable in polynomial time using a simple iterative algorithm. Problem 2 is much harder. We observe that the complexity of Problem 2 is intimately connected to deep conjectures and results in number theory. In particular, if a refined form of the ABC conjecture formulated by Baker in 1998 holds, or if the older Lang-Waldschmidt conjecture (formulated in 1978) on linear forms in logarithms holds, then Problem 2 is decidable in P-time (in the standard Turing model of computation). Moreover, it follows from the best available quantitative bounds on linear forms in logarithms, e.g., by Baker and Wüstholz (1993) or Matveev (2000), that if m and n are fixed universal constants then Problem 2 is decidable in P-time (without relying on any conjectures). This latter fact was observed earlier by Shub (1993). We describe one application: P-time maximum probability parsing for arbitrary stochastic context-free grammars (where ε-rules are allowed).
Classical information storage in an $n$-level quantum system
Venue: arXiv cs.IT 2014
Year: 2014

A game is played by a team of two --- say Alice and Bob --- in which the value of a random variable $x$ is revealed to Alice only, who cannot freely communicate with Bob. Instead, she is given a quantum $n$-level system, respectively a classical $n$-state system, which she can put in possession of Bob in any state she wishes. We evaluate how successfully they managed to store and recover the value of $x$ in the used system by requiring Bob to specify a value $z$ and giving a reward of value $ f(x,z)$ to the team. We show that whatever the probability distribution of $x$ and the reward function $f$ are, when using a quantum $n$-level system, the maximum expected reward obtainable with the best possible team strategy is equal to that obtainable with the use of a classical $n$-state system. The proof relies on mixed discriminants of positive matrices and --- perhaps surprisingly --- an application of the Supply--Demand Theorem for bipartite graphs. As a corollary, we get an infinite set of new, dimension dependent inequalities regarding positive operator valued measures and density operators on complex $n$-space. As a further corollary, we see that the greatest value, with respect to a given distribution of $x$, of the mutual information $I(x;z)$ that is obtainable using an $n$-level quantum system equals the analogous maximum for a classical $n$-state system.
Continuum armed bandit problem of few variables in high dimensions
Venue: arXiv cs.LG 2014
Year: 2014

We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d -> R are assumed to intrinsically depend on at most k coordinate variables implying r(x_1,..,x_d) = g(x_{i_1},..,x_{i_k}) for distinct and unknown i_1,..,i_k from {1,..,d} and some locally Holder continuous g:[0,1]^k -> R with exponent 0 < alpha <= 1. Firstly, assuming (i_1,..,i_k) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of {1,..,d} into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i_1,...,i_k) can change over time and derive regret bounds for the same.
Satisfiability of the Two-Variable Fragment of First-Order Logic over Trees
Venue: arXiv cs.LO 2014
Year: 2014

We consider the satisfiability problem for the two-variable fragment of first-order logic over finite unranked trees. We work with signatures consisting of some unary predicates and the binary navigational predicates child, right sibling, and their respective transitive closures. We prove that the satisfiability problem for the logic containing all these predicates is EXPSPACE-complete. Further, we consider the restriction of the class of structures to singular trees, i.e., we assume that at every node precisely one unary predicate holds. We observe that the full logic and even for unordered trees remain EXPSPACE-complete over finite singular trees, but the complexity decreases for some weaker logics. Namely, the logic with one binary predicate, descendant is NEXPTIME-complete, and its guarded version is PSPACE-complete over finite singular trees, even though both these logics are EXPSPACE-complete over arbitrary finite trees.
Optimized Backhaul Compression for Uplink Cloud Radio Access Network
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the uplink of a cloud radio access network (C-RAN) where the cell sites are connected to a cloud-computing-based central processor (CP) with noiseless backhaul links with finite capacities. We employ a simple compress-and-forward scheme in which the base-stations(BSs) quantize the received signals and send the quantized signals to the CP using either distributed Wyner-Ziv coding or single-user compression. The CP decodes the quantization codewords first, then decodes the user messages as if the remote users and the cloud center form a virtual multiple-access channel (VMAC). This paper formulates the problem of optimizing the quantization noise levels for weighted sum rate maximization under a sum backhaul capacity constraint. We propose an alternating convex optimization approach to find a local optimum solution to the problem efficiently, and more importantly, establish that setting the quantization noise levels to be proportional to the background noise levels is near optimal for sum-rate maximization when the signal-to-quantization-noise ratio (SQNR) is high. In addition, with Wyner-Ziv coding, the approximate quantization noise level is shown to achieve the sum-capacity of the uplink C-RAN model to within a constant gap. With single-user compression, a similar constant-gap result is obtained under a diagonal dominant channel condition. These results lead to an efficient algorithm for allocating the backhaul capacities in C-RAN. The performance of the proposed scheme is evaluated for practical multicell and heterogeneous networks. It is shown that multicell processing with optimized quantization noise levels across the BSs can significantly improve the performance of wireless cellular networks.
Compressive parameter estimation in AWGN
Venue: arXiv cs.IT 2014
Year: 2014

Compressed sensing is by now well-established as an effective tool for extracting sparsely distributed information, where sparsity is a discrete concept, referring to the number of dominant nonzero signal components in some basis for the signal space. In this paper, we establish a framework for estimation of continuous-valued parameters based on compressive measurements on a signal corrupted by additive white Gaussian noise (AWGN). While standard compressed sensing based on naive discretization has been shown to suffer from performance loss due to basis mismatch, we demonstrate that this is not an inherent property of compressive measurements. Our contributions are summarized as follows: (a) We identify the isometries required to preserve fundamental estimation-theoretic quantities such as the Ziv-Zakai bound (ZZB) and the Cramer-Rao bound (CRB). Under such isometries, compressive projections can be interpreted simply as a reduction in "effective SNR." (b) We show that the threshold behavior of the ZZB provides a criterion for determining the minimum number of measurements for "accurate" parameter estimation. (c) We provide detailed computations of the number of measurements needed for the isometries in (a) to hold for the problem of frequency estimation in a mixture of sinusoids. We show via simulations that the design criterion in (b) is accurate for estimating the frequency of a single sinusoid.
Usage History of Scientific Literature: Nature Metrics and Metrics of Nature Publications
Venue: arXiv cs.DL 2014
Year: 2014

In this study, we analyze the dynamic usage history of Nature publications over time using Nature metrics data. We conduct analysis from two perspectives. On the one hand, we examine how long it takes before the articles' downloads reach 50%/80% of the total; on the other hand, we compare the percentage of total downloads in 7 days, 30 days, and 100 days after publication. In general, papers are downloaded most frequently within a short time period right after their publication. And we find that compared with Non-Open Access papers, readers' attention on Open Access publications are more enduring. Based on the usage data of a newly published paper, regression analysis could predict the future expected total usage counts.
Throughput Maximization in Wireless Powered Communication Networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the newly emerging wireless powered communication network (WPCN) in which one hybrid access point (H-AP) with constant power supply coordinates the wireless energy/information transmissions to/from distributed users that do not have energy sources. A "harvest-then-transmit" protocol is proposed where all users first harvest the wireless energy broadcast by the H-AP in the downlink (DL) and then send their independent information to the H-AP in the uplink (UL) by time-division-multiple-access (TDMA). First, we study the sum-throughput maximization of all users by jointly optimizing the time allocation for the DL wireless power transfer versus the users' UL information transmissions given a total time constraint based on the users' DL and UL channels as well as their average harvested energy values. By applying convex optimization techniques, we obtain the closed-form expressions for the optimal time allocations to maximize the sum-throughput. Our solution reveals "doubly near-far" phenomenon due to both the DL and UL distance-dependent signal attenuation, where a far user from the H-AP, which receives less wireless energy than a nearer user in the DL, has to transmit with more power in the UL for reliable information transmission. Consequently, the maximum sum-throughput is achieved by allocating substantially more time to the near users than the far users, thus resulting in unfair rate allocation among different users. To overcome this problem, we furthermore propose a new performance metric so-called common-throughput with the additional constraint that all users should be allocated with an equal rate regardless of their distances to the H-AP. We present an efficient algorithm to solve the common-throughput maximization problem. Simulation results demonstrate the effectiveness of the common-throughput approach for solving the new doubly near-far problem in WPCNs.