Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 5, October 2017

Section: Decision Theory

Near-Optimal Regret Bounds for Thompson Sampling
Shipra Agrawal, Navin Goyal
Article No.: 30
DOI: 10.1145/3088510

Thompson Sampling (TS) is one of the oldest heuristics for multiarmed bandit problems. It is a randomized algorithm based on Bayesian ideas and has recently generated significant interest after several studies demonstrated that it has favorable...

Section: Automata Theory

Streaming Tree Transducers
Rajeev Alur, Loris D'antoni
Article No.: 31
DOI: 10.1145/3092842

The theory of tree transducers provides a foundation for understanding expressiveness and complexity of analysis problems for specification languages for transforming hierarchically structured data such as XML documents. We introduce streaming...

Section: Computational Complexity

Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Article No.: 32
DOI: 10.1145/3106234

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2k bits...

Section: Graphic Games

Qualitative Determinacy and Decidability of Stochastic Games with Signals
Nathalie Bertrand, Blaise Genest, Hugo Gimbert
Article No.: 33
DOI: 10.1145/3107926

We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the...

Section: Formal Languages and Automata Theory

The Complexity of Mean-Payoff Pushdown Games
Krishnendu Chatterjee, Yaron Velner
Article No.: 34
DOI: 10.1145/3121408

Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model...

Section: Invited Articles

Invited Articles Foreword
Eva Tardos
Article No.: 35e
DOI: 10.1145/3140539

Section: Circuit Complexity

An Average-Case Depth Hierarchy Theorem for Boolean Circuits
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
Article No.: 35
DOI: 10.1145/3095799

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f,...

Section: Database Systems and Theory

Parallel-Correctness and Transferability for Conjunctive Queries
Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick
Article No.: 36
DOI: 10.1145/3106412

A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data are first reshuffled over many...