DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.2

Stochastic Caching via Subset Entropy

Authors: Ravi Kumar, Roie Levin, Joseph (Seffi) Naor, and Debmalya Panigrahi

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of such stochastic analyses is that, by the min-max principle, performance on worst-case distributions mirrors that of randomized algorithms on worst-case inputs. In other words, the same shortcoming of worst-case analysis - its inability to distinguish between "easy" and "hard" instances - reappears as an inability to distinguish between "easy" and "hard" distributions. This raises a natural question: Can we characterize "easy" input distributions with useful beyond worst-case bounds? A canonical example is the stochastic caching problem (Aho, Denning, and Ullman, 1971). When the page requests are drawn i.i.d. from the uniform distribution, the best achievable competitive ratio is O(log k), matching the performance of the best randomized algorithm on worst-case instances (Fiat, Karp, Luby, McGeoch, Sleator, and Young, 1991). However, when the input distribution has less entropy, intuition suggests that we should be able to do better by exploiting the information provided by the distribution. In this paper, we formalize this intuition by defining a new information-theoretic parameter of probability distributions called subset entropy. We then use this parameter to give a fine-grained characterization of the competitive ratio of stochastic caching, including a new analysis for the well-known LRU algorithm on stochastic inputs. While our technical results are for the caching problem, we believe the broader principle - parameterizing algorithmic performance by an entropy measure of the input - is of independent interest and might apply to other online and stochastic optimization problems. Indeed, for many other fundamental problems such as (comparison-based) sorting, online matching, online load balancing, etc., the hardest stochastic instances involve high-entropy distributions. We hope our work is a step toward a broader theory of fine-grained algorithmic performance for this class of problems.

Cite as

Ravi Kumar, Roie Levin, Joseph (Seffi) Naor, and Debmalya Panigrahi. Stochastic Caching via Subset Entropy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.APPROX/RANDOM.2026.2,
  author =	{Kumar, Ravi and Levin, Roie and Naor, Joseph (Seffi) and Panigrahi, Debmalya},
  title =	{{Stochastic Caching via Subset Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.2},
  URN =		{urn:nbn:de:0030-drops-277194},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.2},
  annote =	{Keywords: Online Algorithms, Beyond Worst-Case Analysis, Caching, Paging, Entropy}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.17

Competitive Bundle Trading

Authors: Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Allocating a set of resources to an online sequence of customers is a fundamental problem in online algorithms with an extensive history. However, the natural extension where the algorithm is also allowed to purchase inventory from suppliers, who also arrive online, is essentially unexplored. We study this general trading problem under the objective of profit maximization, which is the difference between revenue from sales and cost of purchases. Maximizing the difference between two competing quantities is significantly more challenging than the sell-only case. We show a logarithmic competitive ratio relative to the optimal offline solution. Our algorithm is an exponential-weight–update dynamic pricing scheme, and our analysis dual-fits the algorithm’s profit with respect to a linear programming relaxation that upper bounds the optimal offline profit; we also prove (nearly) matching lower bounds. Finally, we extend our results by designing an incentive-compatible mechanism for the setting in which customers are strategic and may misreport their true valuations.

Cite as

Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Competitive Bundle Trading. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2026.17,
  author =	{Azar, Yossi and Buchbinder, Niv and Levin, Roie and Vardi, Or},
  title =	{{Competitive Bundle Trading}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.17},
  URN =		{urn:nbn:de:0030-drops-264066},
  doi =		{10.4230/LIPIcs.ICALP.2026.17},
  annote =	{Keywords: Online algorithms, competitive analysis, algorithmic game theory, mechanism design, dynamic pricing, resource allocation}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2020.84

Finding Skewed Subcubes Under a Distribution

Authors: Parikshit Gopalan, Roie Levin, and Udi Wieder

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract

Say that we are given samples from a distribution ψ over an n-dimensional space. We expect or desire ψ to behave like a product distribution (or a k-wise independent distribution over its marginals for small k). We propose the problem of enumerating/list-decoding all large subcubes where the distribution ψ deviates markedly from what we expect; we refer to such subcubes as skewed subcubes. Skewed subcubes are certificates of dependencies between small subsets of variables in ψ. We motivate this problem by showing that it arises naturally in the context of algorithmic fairness and anomaly detection. In this work we focus on the special but important case where the space is the Boolean hypercube, and the expected marginals are uniform. We show that the obvious definition of skewed subcubes can lead to intractable list sizes, and propose a better definition of a minimal skewed subcube, which are subcubes whose skew cannot be attributed to a larger subcube that contains it. Our main technical contribution is a list-size bound for this definition and an algorithm to efficiently find all such subcubes. Both the bound and the algorithm rely on Fourier-analytic techniques, especially the powerful hypercontractive inequality. On the lower bounds side, we show that finding skewed subcubes is as hard as the sparse noisy parity problem, and hence our algorithms cannot be improved on substantially without a breakthrough on this problem which is believed to be intractable. Motivated by this, we study alternate models allowing query access to ψ where finding skewed subcubes might be easier.

Cite as

Parikshit Gopalan, Roie Levin, and Udi Wieder. Finding Skewed Subcubes Under a Distribution. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 84:1-84:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gopalan_et_al:LIPIcs.ITCS.2020.84,
  author =	{Gopalan, Parikshit and Levin, Roie and Wieder, Udi},
  title =	{{Finding Skewed Subcubes Under a Distribution}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{84:1--84:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.84},
  URN =		{urn:nbn:de:0030-drops-117691},
  doi =		{10.4230/LIPIcs.ITCS.2020.84},
  annote =	{Keywords: Fourier Analysis, Anomaly Detection, Algorithmic Fairness, Probability, Unsupervised Learning}
}

Search Results

Documents authored by Levin, Roie

Stochastic Caching via Subset Entropy

Abstract

Cite as

Competitive Bundle Trading

Abstract

Cite as

Finding Skewed Subcubes Under a Distribution

Abstract

Cite as

Thanks for your feedback!

Could not send message