Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 5 Issue 2, July 2013

Economical Caching
Matthias Englert, Heiko Röglin, Jacob Spönemann, Berthold Vöcking
Article No.: 4
DOI: 10.1145/2493246.2493247

We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is...

Hard Functions for Low-Degree Polynomials over Prime Fields
Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka
Article No.: 5
DOI: 10.1145/2493246.2493248

In this article, we present a new hardness amplification for low-degree polynomials over prime fields, namely, we prove that if some function is mildly hard to approximate by any low-degree polynomials then the sum of independent copies of...

Alternation-Trading Proofs, Linear Programming, and Lower Bounds
Ryan Williams
Article No.: 6
DOI: 10.1145/2493246.2493249

A fertile area of recent research has demonstrated concrete polynomial-time lower bounds for natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, MOD6-SAT,...

On Approximating the Number of Relevant Variables in a Function
Dana Ron, Gilad Tsur
Article No.: 7
DOI: 10.1145/2493246.2493250

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of...