OpenRaiser/Intern-Atlas huggingface dataset:
Regulation of off-network pricing in a nonneutral network
Venue: arXiv cs.NI 2013
Year: 2013

Representatives of several Internet service providers (ISPs) have expressed their wish to see a substantial change in the pricing policies of the Internet. In particular, they would like to see content providers (CPs) pay for use of the network, given the large amount of resources they use. This would be in clear violation of the "network neutrality" principle that had characterized the development of the wireline Internet. Our first goal in this paper is to propose and study possible ways of implementing such payments and of regulating their amount. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and the monetary flow that involves the content users, the ISP and CP, and in particular, the CP's revenues from advertisements. We consider various game models and study the resulting equilibria; they are all combinations of a noncooperative game (in which the ISPs and CPs determine how much they will charge the users) with a "cooperative" one on how the CP and the ISP share the payments. We include in our model a possible asymmetric weighting parameter (that varies between zero to one). We also study equilibria that arise when one of the CPs colludes with the ISP. We also study two dynamic game models and study the convergence of prices to the equilibrium values.
Computation over Mismatched Channels
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of distributed computation of a target function over a multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the computation and communication tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint computation and communication designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of computation and communication is optimal.
Automated derivation of the adjoint of high-level transient finite element programs
Venue: arXiv cs.MS 2013
Year: 2013

In this paper we demonstrate a new technique for deriving discrete adjoint and tangent linear models of finite element models. The technique is significantly more efficient and automatic than standard algorithmic differentiation techniques. The approach relies on a high-level symbolic representation of the forward problem. In contrast to developing a model directly in Fortran or C++, high-level systems allow the developer to express the variational problems to be solved in near-mathematical notation. As such, these systems have a key advantage: since the mathematical structure of the problem is preserved, they are more amenable to automated analysis and manipulation. The framework introduced here is implemented in a freely available software package named dolfin-adjoint, based on the FEniCS Project. Our approach to automated adjoint derivation relies on run-time annotation of the temporal structure of the model, and employs the FEniCS finite element form compiler to automatically generate the low-level code for the derived models. The approach requires only trivial changes to a large class of forward models, including complicated time-dependent nonlinear models. The adjoint model automatically employs optimal checkpointing schemes to mitigate storage requirements for nonlinear models, without any user management or intervention. Furthermore, both the tangent linear and adjoint models naturally work in parallel, without any need to differentiate through calls to MPI or to parse OpenMP directives. The generality, applicability and efficiency of the approach are demonstrated with examples from a wide range of scientific applications.
A New Family of Low-Complexity STBCs for Four Transmit Antennas
Venue: arXiv cs.IT 2013
Year: 2013

Space-Time Block Codes (STBCs) suffer from a prohibitively high decoding complexity unless the low-complexity decodability property is taken into consideration in the STBC design. For this purpose, several families of STBCs that involve a reduced decoding complexity have been proposed, notably the multi-group decodable and the fast decodable (FD) codes. Recently, a new family of codes that combines both of these families namely the fast group decodable (FGD) codes was proposed. In this paper, we propose a new construction scheme for rate-1 FGD codes for 2^a transmit antennas. The proposed scheme is then applied to the case of four transmit antennas and we show that the new rate-1 FGD code has the lowest worst-case decoding complexity among existing comparable STBCs. The coding gain of the new rate-1 code is optimized through constellation stretching and proved to be constant irrespective of the underlying QAM constellation prior to normalization. Next, we propose a new rate-2 FD STBC by multiplexing two of our rate-1 codes by the means of a unitary matrix. Also a compromise between rate and complexity is obtained through puncturing our rate-2 FD code giving rise to a new rate-3/2 FD code. The proposed codes are compared to existing codes in the literature and simulation results show that our rate-3/2 code has a lower average decoding complexity while our rate-2 code maintains its lower average decoding complexity in the low SNR region. If a time-out sphere decoder is employed, our proposed codes outperform existing codes at high SNR region thanks to their lower worst-case decoding complexity.
Complex Networks from Simple Rewrite Systems
Venue: arXiv cs.SI 2013
Year: 2013

Complex networks are all around us, and they can be generated by simple mechanisms. Understanding what kinds of networks can be produced by following simple rules is therefore of great importance. We investigate this issue by studying the dynamics of extremely simple systems where are `writer' moves around a network, and modifies it in a way that depends upon the writer's surroundings. Each vertex in the network has three edges incident upon it, which are colored red, blue and green. This edge coloring is done to provide a way for the writer to orient its movement. We explore the dynamics of a space of 3888 of these `colored trinet automata' systems. We find a large variety of behaviour, ranging from the very simple to the very complex. We also discover simple rules that generate forms which are remarkably similar to a wide range of natural objects. We study our systems using simulations (with appropriate visualization techniques) and analyze selected rules mathematically. We arrive at an empirical classification scheme which reveals a lot about the kinds of dynamics and networks that can be generated by these systems.
Wireless Information and Power Transfer: Architecture Design and Rate-Energy Tradeoff
Venue: arXiv cs.IT 2013
Year: 2013

Simultaneous information and power transfer over the wireless channels potentially offers great convenience to mobile users. Yet practical receiver designs impose technical constraints on its hardware realization, as practical circuits for harvesting energy from radio signals are not yet able to decode the carried information directly. To make theoretical progress, we propose a general receiver operation, namely, dynamic power splitting (DPS), which splits the received signal with adjustable power ratio for energy harvesting and information decoding, separately. Three special cases of DPS, namely, time switching (TS), static power splitting (SPS) and on-off power splitting (OPS) are investigated. The TS and SPS schemes can be treated as special cases of OPS. Moreover, we propose two types of practical receiver architectures, namely, separated versus integrated information and energy receivers. The integrated receiver integrates the front-end components of the separated receiver, thus achieving a smaller form factor. The rate-energy tradeoff for the two architectures are characterized by a so-called rate-energy (R-E) region. The optimal transmission strategy is derived to achieve different rate-energy tradeoffs. With receiver circuit power consumption taken into account, it is shown that the OPS scheme is optimal for both receivers. For the ideal case when the receiver circuit does not consume power, the SPS scheme is optimal for both receivers. In addition, we study the performance for the two types of receivers under a realistic system setup that employs practical modulation. Our results provide useful insights to the optimal practical receiver design for simultaneous wireless information and power transfer (SWIPT).
Breaking the n^(log n) Barrier for Solvable-Group Isomorphism
Venue: arXiv cs.DS 2013
Year: 2013

We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G and H are isomorphic. The n^(log n) barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the n^(log n + O(1)) generator-enumeration algorithm. In this work, we present the first significant improvement over n^(log n) by showing that group isomorphism is n^((1 / 2) log_p n + O(1)) Turing reducible to composition-series isomorphism where p is the smallest prime dividing the order of the group. Combining our reduction with an n^(O(p / log p)) algorithm for p-group composition-series isomorphism, we obtain an n^((1 / 2) log n + O(1)) algorithm for p-group isomorphism. We then generalize our techniques from p-groups using Sylow bases to derive an n^((1 / 2) log n + O(log n / log log n)) algorithm for solvable-group isomorphism. Finally, we relate group isomorphism to the collision problem which allows us replace the 1 / 2 in the exponents with 1 / 4 using randomized algorithms and 1 / 6 using quantum algorithms.
On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
Venue: arXiv cs.CR 2013
Year: 2013

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li in 2010 using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this paper, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one, where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely-accepted complexity-theoretical assumption holds.
Controlled Sensing for Multihypothesis Testing
Venue: arXiv cs.IT 2013
Year: 2013

The problem of multiple hypothesis testing with observation control is considered in both fixed sample size and sequential settings. In the fixed sample size setting, for binary hypothesis testing, the optimal exponent for the maximal error probability corresponds to the maximum Chernoff information over the choice of controls, and a pure stationary open-loop control policy is asymptotically optimal within the larger class of all causal control policies. For multihypothesis testing in the fixed sample size setting, lower and upper bounds on the optimal error exponent are derived. It is also shown through an example with three hypotheses that the optimal causal control policy can be strictly better than the optimal open-loop control policy. In the sequential setting, a test based on earlier work by Chernoff for binary hypothesis testing, is shown to be first-order asymptotically optimal for multihypothesis testing in a strong sense, using the notion of decision making risk in place of the overall probability of error. Another test is also designed to meet hard risk constrains while retaining asymptotic optimality. The role of past information and randomization in designing optimal control policies is discussed.
Weak Models of Distributed Computing, with Connections to Modal Logic
Venue: arXiv cs.DC 2013
Year: 2013

This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering model, a node of degree d receives messages through d input ports and sends messages through d output ports, both numbered with 1,2,...,d. In this work, VVc is the class of all graph problems that can be solved in the standard port-numbering model. We study the following subclasses of VVc: VV: Input port i and output port i are not necessarily connected to the same neighbour. MV: Input ports are not numbered; algorithms receive a multiset of messages. SV: Input ports are not numbered; algorithms receive a set of messages. VB: Output ports are not numbered; algorithms send the same message to all output ports. MB: Combination of MV and VB. SB: Combination of SV and VB. Now we have many trivial containment relations, such as SB \subseteq MB \subseteq VB \subseteq VV \subseteq VVc, but it is not obvious if, for example, either of VB \subseteq SV or SV \subseteq VB should hold. Nevertheless, it turns out that we can identify a linear order on these classes. We prove that SB \subsetneq MB = VB \subsetneq SV = MV = VV \subsetneq VVc. The same holds for the constant-time versions of these classes. We also show that the constant-time variants of these classes can be characterised by a corresponding modal logic. Hence the linear order identified in this work has direct implications in the study of the expressibility of modal logic. Conversely, one can use tools from modal logic to study these classes.
A Smooth Transition from Powerlessness to Absolute Power
Venue: arXiv cs.GT 2013
Year: 2013

We study the phase transition of the coalitional manipulation problem for generalized scoring rules. Previously it has been shown that, under some conditions on the distribution of votes, if the number of manipulators is $o(\sqrt{n})$, where $n$ is the number of voters, then the probability that a random profile is manipulable by the coalition goes to zero as the number of voters goes to infinity, whereas if the number of manipulators is $ω(\sqrt{n})$, then the probability that a random profile is manipulable goes to one. Here we consider the critical window, where a coalition has size $c\sqrt{n}$, and we show that as $c$ goes from zero to infinity, the limiting probability that a random profile is manipulable goes from zero to one in a smooth fashion, i.e., there is a smooth phase transition between the two regimes. This result analytically validates recent empirical results, and suggests that deciding the coalitional manipulation problem may be of limited computational hardness in practice.
Isogeometric analysis: an overview and computer implementation aspects
Venue: arXiv cs.NA 2013
Year: 2013

Isogeometric analysis (IGA) represents a recently developed technology in computational mechanics that offers the possibility of integrating methods for analysis and Computer Aided Design (CAD) into a single, unified process. The implications to practical engineering design scenarios are profound, since the time taken from design to analysis is greatly reduced, leading to dramatic gains in efficiency. The tight coupling of CAD and analysis within IGA requires knowledge from both fields and it is one of the goals of the present paper to outline much of the commonly used notation. In this manuscript, through a clear and simple Matlab implementation, we present an introduction to IGA applied to the Finite Element (FE) method and related computer implementation aspects. Furthermore, implemen- tation of the extended IGA which incorporates enrichment functions through the partition of unity method (PUM) is also presented, where several examples for both two-dimensional and three-dimensional fracture are illustrated. The open source Matlab code which accompanies the present paper can be applied to one, two and three-dimensional problems for linear elasticity, linear elastic fracture mechanics, structural mechanics (beams/plates/shells including large displacements and rotations) and Poisson problems with or without enrichment. The Bezier extraction concept that allows FE analysis to be performed efficiently on T-spline geometries is also incorporated. The article includes a summary of recent trends and developments within the field of IGA.
Vertex elimination orderings for hereditary graph classes
Venue: arXiv cs.DM 2013
Year: 2013

We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vu\vsković. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.
Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search
Venue: arXiv cs.LG 2013
Year: 2013

Bayesian model-based reinforcement learning is a formally elegant approach to learning optimal behaviour under model uncertainty, trading off exploration and exploitation in an ideal way. Unfortunately, finding the resulting Bayes-optimal policies is notoriously taxing, since the search space becomes enormous. In this paper we introduce a tractable, sample-based method for approximate Bayes-optimal planning which exploits Monte-Carlo tree search. Our approach outperformed prior Bayesian model-based RL algorithms by a significant margin on several well-known benchmark problems -- because it avoids expensive applications of Bayes rule within the search tree by lazily sampling models from the current beliefs. We illustrate the advantages of our approach by showing it working in an infinite state space domain which is qualitatively out of reach of almost all previous work in Bayesian exploration.
Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
Venue: arXiv cs.IT 2013
Year: 2013

In this work the dynamic compressive sensing (CS) problem of recovering sparse, correlated, time-varying signals from sub-Nyquist, non-adaptive, linear measurements is explored from a Bayesian perspective. While there has been a handful of previously proposed Bayesian dynamic CS algorithms in the literature, the ability to perform inference on high-dimensional problems in a computationally efficient manner remains elusive. In response, we propose a probabilistic dynamic CS signal model that captures both amplitude and support correlation structure, and describe an approximate message passing algorithm that performs soft signal estimation and support detection with a computational complexity that is linear in all problem dimensions. The algorithm, DCS-AMP, can perform either causal filtering or non-causal smoothing, and is capable of learning model parameters adaptively from the data through an expectation-maximization learning procedure. We provide numerical evidence that DCS-AMP performs within 3 dB of oracle bounds on synthetic data under a variety of operating conditions. We further describe the result of applying DCS-AMP to two real dynamic CS datasets, as well as a frequency estimation task, to bolster our claim that DCS-AMP is capable of offering state-of-the-art performance and speed on real-world high-dimensional problems.
Off-Policy Actor-Critic
Venue: arXiv cs.LG 2013
Year: 2013

This paper presents the first actor-critic algorithm for off-policy reinforcement learning. Our algorithm is online and incremental, and its per-time-step complexity scales linearly with the number of learned weights. Previous work on actor-critic algorithms is limited to the on-policy setting and does not take advantage of the recent advances in off-policy gradient temporal-difference learning. Off-policy techniques, such as Greedy-GQ, enable a target policy to be learned while following and obtaining data from another (behavior) policy. For many problems, however, actor-critic methods are more practical than action value methods (like Greedy-GQ) because they explicitly represent the policy; consequently, the policy can be stochastic and utilize a large action space. In this paper, we illustrate how to practically combine the generality and learning potential of off-policy learning with the flexibility in action selection given by actor-critic methods. We derive an incremental, linear time and space complexity algorithm that includes eligibility traces, prove convergence under assumptions similar to previous off-policy algorithms, and empirically show better or comparable performance to existing algorithms on standard reinforcement-learning benchmark problems.
Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures
Venue: arXiv cs.CV 2013
Year: 2013

Transform Invariant Low-rank Textures (TILT) is a novel and powerful tool that can effectively rectify a rich class of low-rank textures in 3D scenes from 2D images despite significant deformation and corruption. The existing algorithm for solving TILT is based on the alternating direction method (ADM). It suffers from high computational cost and is not theoretically guaranteed to converge to a correct solution. In this paper, we propose a novel algorithm to speed up solving TILT, with guaranteed convergence. Our method is based on the recently proposed linearized alternating direction method with adaptive penalty (LADMAP). To further reduce computation, warm starts are also introduced to initialize the variables better and cut the cost on singular value decomposition. Extensive experimental results on both synthetic and real data demonstrate that this new algorithm works much more efficiently and robustly than the existing algorithm. It could be at least five times faster than the previous method.
Lattices generated by Chip Firing Game models: criteria and recognition algorithm
Venue: arXiv cs.DM 2013
Year: 2013

It is well-known that the class of lattices generated by Chip Firing games (CFGs) is strictly included in the class of upper locally distributive lattices (ULD). However a necessary and sufficient criterion for this class is still an open question. In this paper we settle this problem by giving such a criterion. This criterion provides a polynomial-time algorithm for constructing a CFG which generates a given lattice if such a CFG exists. Going further we solve the same problem on two other classes of lattices which are generated by CFGs on the classes of undirected graphs and directed acyclic graphs.