3 papers
cs.DS2021
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla +1
Babaioff et al. [BIK2007] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a c…
cs.GT2019
Asynchronous Majority Dynamics in Preferential Attachment Trees
Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan +1
We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better d…
math.CO2017
Split-Decomposition Trees with Prime Nodes: Enumeration and Random Generation of Cactus Graphs
Maryam Bahrani, Jérémie Lumbroso
In this paper, we build on recent results by Chauve et al. (2014) and Bahrani and Lumbroso (2017), which combined the split-decomposition, as exposed by Gioan and Paul, with analyt…