Search ACM DL

Search Issue

enter search term and/or author name

**Limitations of Deterministic Auction Design for Correlated Bidders**

Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou

Article No.: 13

DOI: 10.1145/2934309

The seminal work of Myerson (Mathematics of OR ’81) characterizes incentive-compatible single-item auctions among bidders with independent valuations. In this setting, relatively simple deterministic auction mechanisms achieve revenue...

**Planarizing Gadgets for Perfect Matching Do Not Exist**

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

Article No.: 14

DOI: 10.1145/2934310

To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem...

**The Power of an Example**: Hidden Set Size Approximation Using Group Queries and Conditional Sampling

Dana Ron, Gilad Tsur

Article No.: 15

DOI: 10.1145/2930657

We study a basic problem of approximating the size of an unknown set *S* in a known universe *U*. We consider two versions of the problem. In both versions, the algorithm can specify subsets *T*⊆*U*. In the first version,...

**Space-Efficient Approximations for Subset Sum**

Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Article No.: 16

DOI: 10.1145/2894843

S*t* ∈ *Z*^{+} and a set *S* of *m* positive integers, output YES if and only if there is a subset...

**A Rank Lower Bound for Cutting Planes Proofs of Ramsey’s Theorem**

Massimo Lauria

Article No.: 17

DOI: 10.1145/2903266

Ramsey’s Theorem is a cornerstone of combinatorics and logic. In its simplest formulation it says that for every *k* > 0 and *s* > 0, there is a minimum number *r*(*k*, *s*) such that any simple graph with at...

**Quadratic Maps Are Hard to Sample**

Emanuele Viola

Article No.: 18

DOI: 10.1145/2934308

This note proves the existence of a quadratic GF(2) map *p*: {0, 1}^{n} → {0, 1} such that no constant-depth circuit of size poly(*n*) can sample the distribution (*u*,...