Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 62 Issue 2, May 2015

Section: Algorithmic Economics

Truthful Mechanisms with Implicit Payment Computation
Moshe Babaioff, Robert D. Kleinberg, Aleksandrs Slivkins
Article No.: 10
DOI: 10.1145/2724705

It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating a randomized truthful mechanism is essentially as easy as a...

Section: Algorithmic Economics

Recursive Markov Decision Processes and Recursive Stochastic Games
Kousha Etessami, Mihalis Yannakakis
Article No.: 11
DOI: 10.1145/2699431

We introduce Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs), which are classes of (finitely presented) countable-state MDPs and zero-sum turn-based (perfect information) stochastic games. They extend...

Section: Algorithmic Economics

Document Spanners: A Formal Approach to Information Extraction
Ronald Fagin, Benny Kimelfeld, Frederick Reiss, Stijn Vansummeren
Article No.: 12
DOI: 10.1145/2699442

An intrinsic part of information extraction is the creation and manipulation of relations extracted from text. In this article, we develop a foundational framework where the central construct is what we call a document spanner (or just...

Section: Algorithmic Economics

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
Gregory Valiant
Article No.: 13
DOI: 10.1145/2728167

Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson correlation coefficient ρ (Hamming distance dċ...

Section: Algorithmic Economics

Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems
Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'angelo, Haohan Li, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster, Leen Stougie
Article No.: 14
DOI: 10.1145/2699435

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the...

Section: Algorithmic Economics

Monitoring Metric First-Order Temporal Properties
David Basin, Felix Klaedtke, Samuel Müller, Eugen Zălinescu
Article No.: 15
DOI: 10.1145/2699444

Runtime monitoring is a general approach to verifying system properties at runtime by comparing system events against a specification formalizing which event sequences are allowed. We present a runtime monitoring algorithm for a safety fragment of...

Section: Algorithmic Economics

Invited Article Foreword
Victor Vianu
Article No.: 16
DOI: 10.1145/2754309

Section: Algorithmic Economics

Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald De Wolf
Article No.: 17
DOI: 10.1145/2716307

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we...