More Like this

1. Randomized Cup Game Algorithms Against Strong Adversaries

   https://doi.org/https://doi.org/10.1145/3313276.3316342  

   Bender, M ; Kuszmaul, W. ( January 2021 , Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   In each step of the cup game on n cups, a filler distributes up to 1" water among the cups, and then an emptier removes 1 unit of water from a single cup. The emptier’s goal is to minimize the height of the fullest cup, also known as the backlog. The cup emptying game has found extensive applications to processor scheduling, network- switch buffer management, quality of service guarantees, and data- structure deamortization. The greedy emptying algorithm (i.e., always remove from the fullest cup) is known to achieve backlog O(log n) and to be the optimal deterministic algorithm. Randomized algorithms can do significantly better, achieving backlog O(log log n) with high probability, as long as " is not too small. In order to achieve these improvements, the known randomized algorithms require that the filler is an oblivious adversary, unaware of which cups the emptier chooses to empty out of at each step. Such randomized guarantees are known to be impossible against fully adaptive fillers. We show that, even when the filler is just slightly non- adaptive, randomized emptying algorithms can still guarantee a backlog of O(log log n). In particular, we give randomized ran- domized algorithms against an elevated adaptive filler, which is an adaptive filler that can see the precise fills of every cup containing more than 3 units of water, but not of the cups containing less than 3 units. 

   more » « less
2. Auditory cognition and perception of action video game players

   https://doi.org/10.1038/s41598-020-71235-z  

   Stewart, Hannah J. ; Martinez, Jasmin L. ; Perdew, Audrey ; Green, C. Shawn ; Moore, David R. ( September 2020 , Scientific Reports)

   A training method to improve speech hearing in noise has proven elusive, with most methods failing to transfer to untrained tasks. One common approach to identify potentially viable training paradigms is to make use of cross-sectional designs. For instance, the consistent finding that people who chose to avidly engage with action video games as part of their normal life also show enhanced performance on non-game visual tasks has been used as a foundation to test the causal impact of such game play via true experiments (e.g., in more translational designs). However, little work has examined the association between action video game play and untrained auditory tasks, which would speak to the possible utility of using such games to improve speech hearing in noise. To examine this possibility, 80 participants with mixed action video game experience were tested on a visual reaction time task that has reliably shown superior performance in action video game players (AVGPs) compared to non-players (≤ 5 h/week across game categories) and multi-genre video game players (> 5 h/week across game categories). Auditory cognition and perception were tested using auditory reaction time and two speech-in-noise tasks. Performance of AVGPs on the visual task replicated previous positive findings. However, no significant benefit of action video game play was found on the auditory tasks. We suggest that, while AVGPs interact meaningfully with a rich visual environment during play, they may not interact with the games’ auditory environment. These results suggest that far transfer learning during action video game play is modality-specific and that an acoustically relevant auditory environment may be needed to improve auditory probabilistic thinking.

    

   more » « less
3. Compressed Counting with Spiking Neurons (Extended Abstract)

   Hitron, Yael ; Parter, Merav ( January 2019 , 7th Workshop on Biological Distributed Algorithms (BDA))

   We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired spiking neurons. In the model of spiking neural networks, network evolves in discrete rounds, where in each round, neurons fire in pulses in response to a sufficiently high membrane potential. This potential is induced by spikes from neighboring neurons that fired in the previous round, which can have either an excitatory or inhibitory effect. Discovering the underlying mechanisms by which the brain perceives the duration of time is one of the largest open enigma in computational neuroscience. To gain a better algorithmic understanding onto these processes, we introduce the neural timer problem. In this problem, one is given a time parameter t, an input neuron x, and an output neuron y. It is then required to design a minimum sized neural network (measured by the number of auxiliary neurons) in which every spike from x in a given round i, makes the output y fire for the subsequent t consecutive rounds.We first consider a deterministic implementation of a neural timer and show that Θ(logt)(deterministic) threshold gates are both sufficient and necessary. This raised the question of whether randomness can be leveraged to reduce the number of neurons. We answer this question in the affirmative by considering neural timers with spiking neurons where the neuron y is required to fire for t consecutive rounds with probability at least 1−δ, and should stop firing after at most 2 t rounds with probability 1−δ for some input parameter δ∈(0,1). Our key result is a construction of a neural timer with O(log log 1/δ) spiking neurons. Interestingly, this construction uses only one spiking neuron, while the remaining neurons can be deterministic threshold gates. We complement this construction with a matching lower bound of Ω(min{log log 1/δ,logt}) neurons. This provides the first separation between deterministic and randomized constructions in the setting of spiking neural networks.Finally, we demonstrate the usefulness of compressed counting networks for synchronizing neural networks. In the spirit of distributed synchronizers [Awerbuch-Peleg, FOCS’90], we provide a general transformation (or simulation) that can take any synchronized network solution and simulate it in an asynchronous setting (where edges have arbitrary response latencies) while incurring a small overhead w.r.t the number of neurons and computation time. 

   more » « less
4. Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

   Farina, G. ; Celli, A. ; Marchesi, A. ; Gatti, N. ( January 2021 , ArXivorg)

   null (Ed.)

   The existence of simple uncoupled no-regret learning dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than its counterpart in normal-form games, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to the classical notion of correlated equilibrium in normal-form games. Compared to the latter, the constraints that define the set of EFCEs are significantly more complex, as the correlation device must keep into account the evolution of beliefs of each player as they make observations throughout the game. Due to that significant added complexity, the existence of uncoupled learning dynamics leading to an EFCE has remained a challenging open research question for a long time. In this article, we settle that question by giving the first uncoupled no-regret dynamics that converge to the set of EFCEs in n-player general-sum extensive-form games with perfect recall. We show that each iterate can be computed in time polynomial in the size of the game tree, and that, when all players play repeatedly according to our learning dynamics, the empirical frequency of play is proven to be a O(T^-0.5)-approximate EFCE with high probability after T game repetitions, and an EFCE almost surely in the limit. 

   more » « less
5. Hardness amplification for entangled games via anchoring

   https://doi.org/10.1145/3055399.3055433  

   Bavarian, Mohammad ; Vidick, Thomas ; Yuen, Henry ( June 2017 , Proceedings of the annual ACM Symposium on Theory of Computing)

   We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. 

   more » « less