1 citations · 1 across the 5 of their papers we have counts for
5 papers
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…
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…
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 be…
Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, Radu Vintan +1
The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree can be edge colored (offline) using no more than colors (with being a tri…
Simple and Asymptotically Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We provide a simple online -edge-coloring algorithm for bipartite graphs of maximum degree under adversarial vertex arrivals on one side of the graph. Our…