ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 62 Issue 3, June 2015

Section: Algorithmic Economics

Polyhedral Clinching Auctions and the AdWords Polytope
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
Article No.: 18
DOI: 10.1145/2757277

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting...

Section: Computational Complexity, Logic, Algorithms, Constraint Satisfaction

Schaefer's Theorem for Graphs
Manuel Bodirsky, Michael Pinsker
Article No.: 19
DOI: 10.1145/2764899

Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in...

Section: Complexity Theory

New Strong Direct Product Results in Communication Complexity
Rahul Jain
Article No.: 20
DOI: 10.1145/2699432

We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ε > 0 be a constant. Let...

Section: Learning Theory

Learning without Concentration
Shahar Mendelson
Article No.: 21
DOI: 10.1145/2699439

We obtain sharp bounds on the estimation error of the Empirical Risk Minimization procedure, performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly...

Section: Logic in Computer Science

Guarded Negation
Vince Bárány, Balder Ten Cate, Luc Segoufin
Article No.: 22
DOI: 10.1145/2701414

We consider restrictions of first-order logic and of fixpoint logic in which all occurrences of negation are required to be guarded by an atomic predicate. In terms of expressive power, the logics in question, called GNFO and GNFP, extend the...

Section: Proof Complexity

A Framework for Space Complexity in Algebraic Proof Systems
Ilario Bonacina, Nicola Galesi
Article No.: 23
DOI: 10.1145/2699438

Algebraic proof systems, such as Polynomial Calculus (PC) and Polynomial Calculus with Resolution (PCR), refute contradictions using polynomials. Space complexity for such systems measures the number of distinct monomials to be kept in memory...

Section: Invited Articles Section

Invited Article Foreword
Victor Vianu
Article No.: 24
DOI: 10.1145/2786600

Section: Computational Geometry

On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions
Natan Rubin
Article No.: 25
DOI: 10.1145/2746228

Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O(n2+ε), for any ε > 0, on the maximum number of...