29 citations · 29 across the 2 of their papers we have counts for
4 papers
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski
We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with…
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets
Noga Alon, Shakhar Smorodinsky
We prove a new Radon type theorem for unions of convex sets, settling an open problem posed by Kalai in the 1970s. We also define and study an extension of the notion of the VC-dim…
A Bicriterion Concentration Inequality and Prophet Inequalities for -Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner +4
We investigate prophet inequalities with competitive ratios approaching , seeking to generalize -uniform matroids. We first show that large girth does not suffice: for all $k…
Optimal Preprocessing for Answering On-Line Product Queries
Noga Alon, Baruch Schieber
We examine the amount of preprocessing needed for answering certain on-line queries as fast as possible. We start with the following basic problem. Suppose we are given a semigroup…