Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 8 Issue 4, July 2016

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

SubsetSum is a well-known NP-complete problem: given tZ+ 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,...