ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 7 Issue 1, December 2014

Advice Lower Bounds for the Dense Model Theorem
Thomas Watson
Article No.: 1
DOI: 10.1145/2676659

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every...

Limitations of Local Filters of Lipschitz and Monotone Functions
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova
Article No.: 2
DOI: 10.1145/2692372.2692373

We study local filters for two properties of functions of the form f : {0,1}d → R: the Lipschitz property and monotonicity. A local filter with additive error a is a randomized algorithm that is given black-box access to a...

The Complexity of the Nucleolus in Compact Games
Gianluigi Greco, Enrico Malizia, Luigi Palopoli, Francesco Scarcello
Article No.: 3
DOI: 10.1145/2692372.2692374

The nucleolus is a well-known solution concept for coalitional games to fairly distribute the total available worth among the players. The nucleolus is known to be NP-hard to compute over compact coalitional games, that is, over games whose...

Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs
Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman
Article No.: 4
DOI: 10.1145/2691321

This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example prior to this work excludes polynomial kernelizations for the so-called Ramsey problem of finding an independent set or...