135,395 research outputs found
Nonzero-sum Stochastic Games
No full textThis paper treats of stochastic games. We focus on nonzero-sum games and provide a detailed survey of selected recent results. In Section 1, we consider stochastic Markov games. A correlation of strategies of the players, involving ``public signals'', is described, and a correlated equilibrium theorem proved recently by Nowak and Raghavan for discounted stochastic games with general state space is presented. We also report an extension of this result to a class of undiscounted stochastic games, satisfying some uniform ergodicity condition. Stopping games are related to stochastic Markov games. In Section 2, we describe a version of Dynkin's game related to observation of a Markov process with random assignment mechanism of states to the players. Some recent contributions of the second author in this area are reported. The paper also contains a brief overview of the theory of nonzero-sum stochastic games and stopping games which is very far from being complete.average payoff stochastic games, correlated stationary equilibria, nonzero-sum games, stopping time, stopping games
On the hardness of the sum of K mins problem
No full textThe sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices
Joshua Davis: Author of Spare Parts
No full textCitation: K-State First (2016). Joshua Davis: Author of Spare Parts [Flier]. Manhattan, Kansas: K-State First.Flyer advertising Joshua Davis's author talk at Kansas State University
An iterative method for faster sum-of-pairs multiple sequence alignment
No full textReinert K, Stoye J, Will T. An iterative method for faster sum-of-pairs multiple sequence alignment. Bioinformatics. 2000;16(9):808-814
Steven Johnson Author Talk Poster
No full textK-State Book NetworkA poster advertising an author talk by Steven Johnson at Kansas State University on September 3, 2014. Steven Johnson's book "The Ghost Map" was the 2014-2015 common book
A Hybrid Continuous Max-Sum Algorithm for Decentralised Coordination
No full textRecent advances in decentralised coordination of multiple agents have led to the proposal of the max-sum algorithm for solving distributed constraint optimisation problems (DCOPs). The max-sum algorithm is fully decentralised, converges to optimality for problems with acyclic constraint graphs and otherwise performs well in empirical studies. However, it requires agents to have discrete state spaces, which are of practical size to conduct repeated searches over. In contrast, there are decentralised non-linear optimisation methods that are capable of accurately finding local optima over multi-dimensional continuous state spaces, however these methods are not designed to navigate complex interactions between local constraints in order to find globally optimal solutions. Given this background, in this paper we tackle the problem of coordinating multiple decentralised agents with continuous state variables. Specifically we propose a hybrid approach, which combines the max-sum algorithm with continuous non-linear optimisation methods. We show that, for problems with acyclic factor graph representations, for suitable parameter choices, our proposed algorithm converges to a state with utility close to the global optimum. We empirically evaluate our approach for cyclic constraint graphs in a multi-sensor target classification problem, and compare its performance to the discrete max-sum algorithm, as well as a non-coordinated approach and the distributed stochastic algorithm (DSA). We show that our hybrid max-sum algorithm outperforms the non-coordinated algorithm, DSA and discrete max-sum considerably. Furthermore, the improvements in outcome over discrete max-sum come without significant increases in running time nor communication cost
Sum-Capacity of Massive MIMO Systems Using Vandermonde Matrices
No full textIn this paper, we use a series expansion to calculate the sum-capacity of a massive Multiple-Input MultipleOutput (MIMO) system under propagation environment
described by a dominant line-of-sight. The sum-capacity is
written as Taylor’s series where each term is a function
of the mean trace of k-th power of the channel matrix
W. We analytically derive the mean trace of first, second,
third, and fourth moments of W. Although the series is
infinite, our numerical results show that only a few terms
can tightly approximate the exact sum capacity. Numerical
results corroborate our analytical expressions
-SUM in the Sparse Regime
No full textIn the average-case -SUM problem, given integers chosen uniformly at random from , the objective is to find a solution set of numbers that sum to modulo . In the dense regime of , where solutions exist with high probability, the complexity of these problems is well understood. Much less is known in the sparse regime of , where solutions are unlikely to exist.
In this work, we initiate the study of the sparse regime for -SUM and its variant -XOR, especially their planted versions, where a random solution is planted in a randomly generated instance and has to be recovered. We provide evidence for the hardness of these problems and suggest new applications to cryptography. Our contributions are summarized below.
Complexity. First we study the complexity of these problems in the sparse regime and show:
- Conditional Lower Bounds. Assuming established conjectures about the hardness of average-case (non-planted) -SUM/-XOR when , we provide non-trivial lower bounds on the running time of algorithms for planted -SUM when .
- Hardness Amplification. We show that for any , if an algorithm running in time solves planted -SUM/-XOR with success probability , then there is an algorithm running in time that solves it with probability . This in particular implies hardness amplification for 3-SUM over the integers, which was not previously known. Technically, our approach departs significantly from existing approaches to hardness amplification, and relies on the locality of the solution together with the group structure inherent in the problem. Additionally, it enables us to assume only mild hardness of these problems for use in applications.
- New Reductions and Algorithms. We provide reductions for -SUM/-XOR from search to decision, as well as worst-case and average-case reductions to the Subset Sum problem from -SUM. Additionally, we present a new algorithm for average-case -XOR that is faster than known worst-case algorithms at low densities.
Cryptography. We show that by additionally assuming mild hardness of -XOR, we can construct Public Key Encryption (PKE) from a weaker variant of the Learning Parity with Noise (LPN) problem than was known before. In particular, such LPN hardness does not appear to imply PKE on its own -- this suggests that -XOR/-SUM can be used to bridge minicrypt and cryptomania in some cases, and may be applicable in other settings in cryptography
Effects of Public Policies on the Disposition of Pre-retirement Lump-Sum Distributions: Rational and Behavioral Influences
No full textA variety of public policies aim to influence workers’ disposition of preretirement lump-sum distributions (LSDs) from pensions. We use the implementation of several policy changes as natural experiments to test for rational and behavioral motives for saving behavior. Using data from the HRS and the CPS in the 1980s and 1990s, we find that higher tax rates on cash-outs increase rollovers. Controlling for the overall effective tax rate, structuring the tax as a “penalty” or adding withholding taxes on cashouts significantly increases rollovers. Allowing employers to unilaterally cash out balances for departing employees who do not make their own choice significantly reduces the effects of higher tax rates but boosts the impact of withholding taxes. These results suggest that both behavioral and rational factors influence workers’ choices, that policies relating to pre-retirement cash outs can interact in important ways, and that the government has several levers at its disposal to influence behavior beyond tax penalties.retirement;savings;behavioral;penalties;taxes
- …
