enter search term and/or author name
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
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
Article No.: 6
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
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...