5 papers · 1 filter
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 Two-Stage Submodular Maximization
Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis +1
Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective sel…
Data-Driven Solution Portfolios
Marina Drygala, Silvio Lattanzi, Andreas Maggiori +3
In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select potenti…
Graph Connectivity with Noisy Queries
Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis +2
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its op…