Search ACM DL

Search Issue

enter search term and/or author name

**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...

**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...

**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...

**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...

**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...

**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...

**Invited Article Foreword**

Victor Vianu

Article No.: 24

DOI: 10.1145/2786600

**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*(*n*^{2+ε}), for any ε > 0, on the maximum number of...