enter search term and/or author name
From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem
Yijia Chen, Jörg Flum
Article No.: 17
Let C denote one of the complexity classes “polynomial time,” “logspace,” or “nondeterministic logspace.” We introduce a logic L(C)inv and show generalizations and variants of the equivalence...
The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting...
A Primal-Dual Randomized Algorithm for Weighted Paging
Nikhil Bansal, Niv Buchbinder, Joseph (Seffi) Naor
Article No.: 19
We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is...
Dynamic Indexability and the Optimality of B-Trees
Article No.: 21
One-dimensional range queries, as one of the most basic type of queries in databases, have been studied extensively in the literature. For large databases, the goal is to build an external index that is optimized for disk block accesses (or I/Os)....