3 papers
cs.DS2026
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2
We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversari…
cs.DS2026
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
cs.DS2025
Online Edge Coloring: Sharp Thresholds
Joakim Blikstad, Ola Svensson, Radu Vintan +1
Vizing's theorem guarantees that every graph with maximum degree admits an edge coloring using colors. In online settings - where edges arrive one at a time and must b…