47 citations · 75 across the 6 of their papers we have counts for
6 papers
The FAST Algorithm for Submodular Maximization
Adam Breuer, Eric Balkanski, Yaron Singer
In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint whose ap…
Robust Attacks against Multiple Classifiers
Juan C. Perdomo, Yaron Singer
We address the challenge of designing optimal adversarial noise algorithms for settings where a learner has access to multiple classifiers. We demonstrate how this problem can be f…
The Importance of Communities for Learning to Influence
Eric Balkanski, Nicole Immorlica, Yaron Singer
We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts…
Robust Optimization for Non-Convex Objectives
Robert Chen, Brendan Lucier, Yaron Singer +1
We consider robust optimization problems, where the goal is to optimize in the worst case over a class of objective functions. We develop a reduction from robust improper optimizat…
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
Ashwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein +2
The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, an…
VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
Elchanan Mossel, Christos Papadimitriou, Michael Schapira +1
The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational m…