24 citations · 86 across the 22 of their papers we have counts for
6 papers · 1 filter
On the Complexity of Dynamic Submodular Maximization
Xi Chen, Binghui Peng
We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of insertions and deletions. We show that any algorithm that maintains a…
Dynamic Influence Maximization
Binghui Peng
We initiate a systematic study on (DIM). In the DIM problem, one maintains a seed set of at most nodes in a…
Public Goods Games in Directed Networks
Christos Papadimitriou, Binghui Peng
Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range…
Computational Hardness of the Hylland-Zeckhauser Scheme
Thomas Chen, Xi Chen, Binghui Peng +1
We study the complexity of the classic Hylland-Zeckhauser scheme [HZ'79] for one-sided matching markets. We show that the problem of finding an -approximate equilibrium in the H…
Shuffle Private Stochastic Convex Optimization
Albert Cheu, Matthew Joseph, Jieming Mao +1
In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection…
Self-Attention Networks Can Process Bounded Hierarchical Languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou +1
Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as $\maths…