enter search term and/or author name
Polyhedral Clinching Auctions and the AdWords Polytope
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
Article No.: 18
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 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
Article No.: 20
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...
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...
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
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...
On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions
Article No.: 25
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...