6 citations · 22 across the 11 of their papers we have counts for
3 papers · 1 filter
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Christos Papadimitriou, Tristan Pollner, Amin Saberi +1
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" w…
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
Nima Anari, Constantinos Daskalakis, Wolfgang Maass +3
We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our…
On Satisfiability Problems with a Linear Structure
Serge Gaspers, Christos Papadimitriou, Sigve Hortemo Saether +1
It was recently shown \cite{STV} that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite gra…